LEVAL, Circuit Judge:

This is an appeal by the State of New York from the grant by the United District Court for the Southern District of New York (Brieant, J.) of a petition for a writ of habeas corpus under 28 U.S.C. § 2254. The district court granted the writ vacating Anthony DiSimone’s criminal conviction, and as part of its judgment ordered that New York be precluded from re-arresting and re-prosecuting the petitioner. At the conclusion of oral argument we issued an order, which affirmed the district court’s judgment insofar as it vacated Di-Simone’s conviction and released him from custody, but vacated the judgment insofar as it barred the State from pursuing future arrest and re-prosecution. We now issue a further explanatory opinion.

BACKGROUND

We described the facts of this case in an earlier proceeding on this petition for ha-beas corpus. DiSimone v. Phillips, 461 F.3d 181, 186-87 (2d Cir.2006) (“DiSimone /”). In brief, the facts are as follows: On February 4, 1994, the bouncer at a bar in Yonkers, New York, of which DiSimone was an owner, refused to let one group of friends into the bar. The bouncer later refused to admit another group. Shortly thereafter a fight broke out in the street outside the bar. Louis Balancio died of stab wounds received during the brawl. The autopsy report revealed that Balancio had been stabbed thirteen times, including once in the lung and once in the heart.

DiSimone then became a fugitive. Five years later, he surrendered to local police and was arrested for Balancio’s murder. He was thereafter indicted on one count of intentional murder, one count of depraved indifference murder, and separate counts of tampering with physical evidence. A jury trial was held in October 2000. The jury acquitted DiSimone of intentional murder, but convicted him of depraved indifference murder and tampering with physical evidence. He was sentenced on January 26, 2001, to twenty-five years to life on the murder charge and one and one-third to four years on the tampering charge.

His conviction was affirmed on direct appeal, People v. DiSimone, 751 N.Y.S.2d 403, 298 A.D.2d 399 (2d Dep’t 2002), and leave to appeal to the New York Court of Appeals was denied, People v. DiSimone, 99 N.Y.2d 613, 757 N.Y.S.2d 824, 787 N.E.2d 1170 (2003). On April 23, 2004, DiSimone sought habeas corpus relief in federal district court pursuant to 28 U.S.C. § 2254. On November 30, 2005, in its first opinion, the district court granted habeas corpus relief on the ground that, according to recent New York case law elaborating the elements of depraved indifference murder, see People v. Payne, 3 N.Y.3d 266, 786 N.Y.S.2d 116, 819 N.E.2d 634 (2004), the evidence was insufficient to sustain a conviction of that crime, because depraved indifference murder cannot result from conduct that evinces an intent to kill. See DiSimone I, 461 F.3d at 185; DiSimone v. Phillips, No. 04 Civ. 3128, 2005 WL 5396451 (S.D.N.Y. Nov. 30, 2005).

*126 On the first appeal, this court reversed the judgment of the district court and remanded because, in the prior state court proceedings, DiSimone had failed to preserve the insufficiency-of-evidence ground that formed the basis of the district court’s grant of habeas relief. DiSimone I, 461 F.3d at 185. However, we remanded the case to the district court for further fact-finding regarding whether the State had violated its Brady obligations by failing to make timely disclosure of evidence that a person other than petitioner had admitted to stabbing Balando in the chest. Id. at 186,192,198.

On remand, New York conceded a Brady violation and withdrew its opposition to petitioner’s demand for habeas corpus relief vacating the conviction. DiSimone then demanded not only that his conviction be vacated, but also that New York be barred from re-trying him.

The district court entered judgment, not only vacating the conviction and ordering DiSimone’s release from custody, but also dismissing the indictment and barring New York from re-arresting and re-trying him for depraved indifference murder. The district court reasoned as follows:

For what purpose would the case be remanded for retrial? ... Were this Court to permit retrial on the Count of conviction being vacated, that is to say Depraved Indifference Murder, in light of Policano v. Herbert, 7 N.Y.3d 588, 825 N.Y.S.2d 678, 859 N.E.2d 484 (decided November 16, 2006), as well as People v. Feingold, 7 N.Y.3d 288, 819 N.Y.S.2d 691, 852 N.E.2d 1163 (2006), Mr. DiSimone could not be convicted on the evidence presently before the Court of Depraved Indifference Murder.

DiSimone v. Phillips, No. 04 Civ. 3128 (S.D.N.Y. Feb. 5, 2007). New York brought this appeal.

DISCUSSION

It is uncontested that petitioner is entitled to be released from further service of his sentence of conviction for depraved indifference murder. 1 As New York has conceded, because of the prosecution’s withholding of evidence during his trial, his conviction was obtained in violation of due process under Brady v. Maryland, 373 U.S. 83, 83 S.Ct. 1194, 10 L.Ed.2d 215 (1963). A function of § 2254 is to provide for a petitioner’s release from state custody where custody is premised on an illegal conviction. See Preiser v. Rodriguez, 411 U.S. 475, 484, 93 S.Ct. 1827, 36 L.Ed.2d 439 (1973). The district court therefore properly ordered that DiSimone’s unconstitutional conviction be vacated and that he be released from service of the sentence imposed on that conviction.

The district court, however, went further. In its further order barring retrial, the district court was correcting state errors which had not yet been made. As yet, no state court had even considered the question whether DiSimone could be retried.

In granting the writ so as to bar his retrial, the district court exceeded the authority conferred by § 2254. Paragraph (b)(1) of that statute prohibits grants of the writ “unless it appears that (A) the applicant has exhausted the remedies available in the courts of the State; or (B)(i) there is an absence of available State corrective process; or (ii) circumstances exist that render such process ineffective to protect the rights of the applicant.” 28 U.S.C. § 2254(b)(1). None of these condi *127 tions was satisfied. Not only had DiSimone not “exhausted the remedies available in the courts of the State” to bar retrial, he had not even presented to those courts a request for such a ruling.

The Supreme Court has explained that the exhaustion requirement is premised on the principles of federal-state comity. “Because ‘it would be unseemly in our dual system of government for a federal district court to upset a state court conviction without an opportunity to the state courts to correct a constitutional violation,’ federal courts apply the doctrine of comity....” Rose v. Lundy, 455 U.S. 509, 518, 102 S.Ct. 1198, 71 L.Ed.2d 379 (1982) (quoting Darr v. Burford, 339 U.S. 200, 204, 70 S.Ct. 587, 94 L.Ed. 761 (1950)). The exhaustion rule of § 2254(b)(1)(A) enforces these principles of comity. It bars the federal court from granting relief under § 2254 from a state court conviction until the petitioner has utilized every opportunity offered to him in state procedure to obtain the same relief from the state courts. This ensures that the federal government, “anxious though it may be to vindicate and protect federal rights and federal interests,” does so in a way that “will not unduly interfere with the legitimate activities of the States.” Younger v. Harris, 401 U.S. 37, 44, 91 S.Ct. 746, 27 L.Ed.2d 669 (1971).

The rule does not change the ultimate resolution, although it may impose some delay. It concerns itself with the relationship among sovereigns. It protects sovereign states from presumptuous correction of their constitutional errors until their courts have been given every opportunity permitted in their procedure to correct their own mistakes.

Here, the petitioner has not exhausted the remedies available in the New York State courts to bar retrial. In fact, he has yet to present to any state court the constitutional claims that formed the basis for the district court’s decision to bar retrial for depraved indifference murder. The question whether retrial is in fact improper under the constitutional principles of insufficiency of the evidence or double jeopardy must be determined in the first instance by the state courts, if and when the state chooses to retry the petitioner. At present, any determination of such questions by a federal court is premature.

It is true that in special circumstances federal courts may bar retrial of a successful habeas corpus petitioner without his having first sought protection from retrial in the state courts. In all but the most extreme circumstances, this would be appropriate only when the grant of habeas corpus is premised on a theory which inevitably precludes further trial. For instance, in Blackledge v. Perry, 417 U.S. 21, 94 S.Ct. 2098, 40 L.Ed.2d 628 (1974), the petitioner was granted habeas corpus relief, overturning his felony conviction and impliedly dismissing the indictment and barring retrial on the felony charge, on the ground that the state had violated due process by charging a felony. Id. at 28-29, 94 S.Ct. 2098. The Supreme Court noted that the Constitution “bars trial of [the petitioner] on the felony assault charges” because the petitioner “was denied due process ... by the very institution of the felony indictment against him.” Id. at 31 n. 8, 94 S.Ct. 2098 (In response to the dissent’s protest that “no penalty whatever will be imposed,” the court noted that the state was “wholly free to conduct a trial de novo ... on the original misdemeanor assault charge.” Id. (emphasis added)).

In this case, the grant of habeas corpus relief vacating DiSimone’s conviction was not predicated on a ground that inevitably precludes retrial. It was grounded on the State’s failure to turn over exculpatory evidence in violation of Brady. A Brady violation, unlike the due process violation *128 in Blackledge, is remediable upon a future trial. DiSimone is therefore not excused from exhausting in the state courts his claim that retrial for depraved indifference murder is constitutionally barred. 2

The State’s withholding of Brady material, which was the ground justifying the district court’s altogether proper vacating of the state court conviction, was remediable upon a retrial. As to whether retrial would violate double jeopardy, or would necessarily involve constitutionally insufficient evidence, petitioner has never presented either question to the state courts. Because petitioner has not exhausted his state remedies, the district court lacked authority to bar his retrial. We therefore vacate this aspect of the district court’s order and express no views on the question whether DiSimone may be retried.

CONCLUSION

The district court’s order directing that petitioner be released from custody based on his sentence of conviction is affirmed. The court’s order barring retrial is vacated. 3

. It is also uncontested that petitioner may not be retried on the murder count, upon which he was acquitted.

. United States ex rel. Schuster v. Vincent, 524 F.2d 153 (2d Cir.1975) is not to the contrary. In that case we found the petitioner entitled to absolute discharge and ordered that the parole board no longer have jurisdiction over him, id. at 161, where the State had violated our prior mandate to hold a sanity hearing and the "inference [was] virtually inescapable that [the petitioner’s] entire 31-year confinement in the hospital for the criminally insane was improper.” Id. at 158. For two reasons, this precedent does not support the district court’s disposition. First, we explicitly noted in Schuster that the petitioner had requested the relief of absolute discharge in the state courts, and "thus exhausted available State remedies, as required by 28 U.S.C. § 2254.” Id. at 158. Second, even if the State’s abusive conduct in that case might have justified excusing the petitioner from fulfilling the exhaustion requirement (in order to protect him from further disregard of constitutional rights), the case before us presents no such extreme circumstances.

. Petitioner has moved pursuant to Federal Rule of Appellate Procedure 10(e) to supplement the record on appeal with further alleged Brady material that the State disclosed only after oral argument was heard. This new evidence would not affect our ruling. The State’s Brady violations, although entirely sufficient to justify vacating DiSimone’s conviction, were not so egregious as to raise doubts about DiSimone's receipt of fair process upon any retrial. The motion is therefore denied as moot.