OPINION OF THE COURT
NYGAARD, Circuit Judge.This case arises from a situation that is troubling on several accounts: First, because it highlights the procedural morass that state prisoners face in pursuing habe-as relief, and second, because it illustrates the tension between what should be the touchstone of any penal system-rehabilitation-and a convicted sex offender’s rights against self-incrimination under the Fifth Amendment. Presently, we must determine whether a Pennsylvania state prisoner challenging his denial of parole on Fifth Amendment grounds must first seek a writ of mandamus in state court before seeking federal habeas review. For the reasons that follow, we hold that the answer is no.
I.
Robert DeFoy was convicted in state court of armed robbery. He served ten years of a 10-20 year sentence before being paroled. Shortly after his release, De-Foy was recommitted as a technical parole violator to serve eighteen additional months. After serving this additional time, he was re-paroled.
While on parole for the second time, DeFoy was arrested for involuntary deviate sexual intercourse, statutory rape, and corruption of a minor. During trial on these charges, DeFoy testified as to his innocence but was convicted nonetheless and sentenced to 78-156 months imprisonment. In addition, the state court revoked his parole on the armed robbery sentence and ordered him to serve an additional forty months imprisonment for that offense.1 Finally, the sentencing judge rec*441ommended that DeFoy participate in Pennsylvania’s Sexual Offender Treatment Program. Because DeFoy was unwilling to admit he committed the sex offenses, however, he was precluded from participating in the Program.2 In turn, he was twice denied parole while serving the armed robbery sentence because he had not participated in the Program. DeFoy’s direct appeals in the Pennsylvania courts were denied on the basis that denials of parole are not appealable in those courts. He did not file a writ of mandamus or a writ of habeas corpus in state court and instead sought federal habeas relief.
DeFoy’s amended petition under 28 U.S.C. § 2254 included several claims, but only one is presently relevant. According to DeFoy, the requirement that he admit guilt to qualify for the Sexual Offender Treatment Program violates his Fifth Amendment right against coerced self-incrimination. The District Court referred this claim to the Magistrate Judge, who ultimately concluded it was likely DeFoy could have filed a petition for a writ of mandamus in the Pennsylvania state courts. In light of our instruction that any ambiguity concerning the availability of a state remedy should result in a habeas petition claim being dismissed as unex-hausted, see Coady v. Vaughn, 251 F.3d 480, 489 (3d Cir.2001), the Magistrate Judge recommended that the District Court dismiss the petition. The District Court adopted the Magistrate Judge’s Report and Recommendation in its' entirety, but entered a certificate of appealability on the following question: “Whether constitutional claims concerning the denial of parole in Pennsylvania, other than those premised upon the ex post facto Clause, must be presented to the state courts in order to satisfy; the ' exhaustion requirement.”
II.
We have jurisdiction over a District Court’s final order dismissing a habeas petition pursuant to 28 U.S.C. §§ 2253 and 1291. '
A.
The threshold issue before us is whether DeFoy’s petition is moot. The Commonwealth claims this is the case because De-Foy is no longer serving his sentence for armed robbery, but instead is now serving his sentence for the sex offenses. Thus, according to the Commonwealth, any denial of parole occurring while DeFoy was still serving his armed robbery sentence will remain unaffected by our ruling. This argument is flawed.
A prisoner may seek federal habe-as relief only if he is in custody in violation of the constitution or federal- law. 28 U.S.C. § 2254(a). Moreover, a petition for habeas corpus relief generally becomes moot when a prisoner is released from custody before the court has addressed the merits of the petition. Lane v. Williams, 455 U.S. 624, 631, 102 S.Ct. 1322, 71 L.Ed.2d 508 (1982). This general principle derives from the case or controversy requirement of Article III of the Constitution, which “subsists through all stages of federal judicial proceedings, trial and appellate ... the parties must continue to have a personal stake in the outcome of the lawsuit.” Lewis v. Cont’l Bank Corp., 494 U.S. 472, 477-78, 110 S.Ct. 1249, 108 L.Ed.2d 400 (1990) (internal citations and *442quotations omitted). In other words, throughout _ the litigation, the plaintiff “must have suffered, or be threatened with, an actual injury traceable to the defendant and likely to be redressed by a favorable judicial decision.” Id. at 477, 110 S.Ct. 1249; see also Maleng v. Cook, 490 U.S. 488, 492, 109 S.Ct. 1923, 104 L.Ed.2d 540 (1989) (holding that habeas petitioner does not remain “in custody” after the sentence imposed has fully expired merely because of the possibility that the prior conviction will be used to enhance sentences imposed for any subsequent crimes of which he is convicted); United States v. Romera-Vilca, 850 F.2d 177, 179 (3d Cir. 1988) (holding that prisoner’s motion to vacate his conviction was not mooted when he was released from custody, where he faced potential deportation as a collateral consequence of conviction).
In Garlotte v. Fordice, 515 U.S. 39, 41, 115 S.Ct. 1948, 132 L.Ed.2d 36 (1995), the Supreme Court held that a prisoner’s challenge to the validity of his conviction was not moot despite the fact that he was no longer in custody for that conviction. The Court reasoned that because Garlotte was still in custody for sentences consecutive to that already served, he could attack the conviction underlying the sentence that ran first in the series. Id. Although the facts in Garlotte are somewhat different from those here \i.e., the prisoner there had been convicted and sentenced by the same court at the same time), Garlotte allows us to review a completed sentence when the prisoner, like DeFoy, is still serving a sentence imposed by a different court at a different time. See Foster v. Booher, 296 F.3d 947, 950 (10th Cir.2002).
DeFoy was required to serve the remainder of his armed robbery sentence before he could begin serving his sex offense sentence. The effect of any error as to the former was to delay the start of the latter. Thus, because any remedy we grant DeFoy might affect his release date for the sentence he is currently serving, we conclude that under Garlotte and Foster, DeFoy’s habeas petition is not moot.3
B.
We may not review a petition for writ of habeas corpus “unless it appears that ... the applicant has exhausted the remedies available in the courts of the State,” or shows that doing so would be futile because state procedures are unavailable or ineffective. 28 U.S.C. § 2254(b). The exhaustion doctrine addresses “federalism and comity concerns by affording the state courts a meaningful opportunity to consider allegations of legal error without interference from the federal judiciary.” Coady, 251 F.3d at 488 (internal citations and quotations omitted). The burden is on the habeas petitioner to prove exhaustion. Toulson v. Beyer, 987 F.2d *443984, 987 (3d Cir.1993). The District Court-in the midst of considerable jurisprudential confusion on the issue-concluded that DeFoy failed to exhaust his state remedies because he could have filed a petition for a writ of mandamus in the state court before proceeding with his federal habeas corpus petition. We apply plenary review to this conclusion. Whitney v. Horn, 280 F.3d 240, 249 (3d Cir. 2002).
Although we have requested, and received, some clarification from the Pennsylvania Supreme Court regarding the remedies available to prisoners who wish to challenge their denial of parole- on constitutional grounds, see, e.g., Coady v. Vaughn, 564 Pa. 604, 770 A.2d 287 (2001), the Court’s response is not conclusive as to the issues before us now. Therefore, some recitation of the relevant Pennsylvania case law is in order. t
In Burkett v. Love, 89 F.3d 135, 142 (3d Cir.1996), we predicted that Pennsylvania courts would permit three methods of attacking the denial of parole in Pennsylvania courts: direct appeal, mandamus, and state habeas corpus. Our predictions were refuted in Weaver v. Pennsylvania Board of Probation & Parole, 688 A.2d at 766, when the Pennsylvania Commonwealth Court declined to adopt the reasoning in Burkett and held these suggested remedies to be unavailable. It noted, specifically, “we do not believe that the remedies suggested in Burkett are available to a prisoner who has been denied parole based upon an unconstitutional factor.” Id. at 771-72. It is certainly worth noting that the issue in Weaver was identical to the issue here: whether a parole board may deny parole based on the fact that a prisoner has not completed a sex offender treatment program when that failure stems from the prisoner’s refusal to admit guilt for the sex offense in the first place.
In light of Weaver, several District Courts in our Circuit relied on the premise that there were no remedies in Pennsylvania state courts for prisoners who wished to challenge the denial of parole, even when the denial was based on an unconstitutional factor. As a result, these courts excused exhaustion of state remedies. See, e.g., Bonilla v. Vaughn, No. 97-7440, 1998 WL 480833 at *5 (E.D.Pa. Aug.. 14, 1998); Speth v. Pennsylvania Bd. of Probation & Parole, No. 98-1631, 1998 WL 272155 at *2 (E.D.Pa. May 18, 1998); cf. George v. Vaughn, No. 98-3, 1998 WL 188847, at *2 (E.D.Pa. April 21,1998) (“[I]t is not clear whether any remedies are available in Pennsylvania, to. challenge the denial of parole.”).
This area of law became conflicted, however, when the Pennsylvania Commonwealth Court in Myers v. Ridge, 712 A.2d 791, 794 (Pa.Commw.Ct.1998), seemingly ignoring Weaver, reached the merits of a prisoner’s due process, ex post facto, and equal protection claims because it found that it may entertain an application for a writ of mandamus to review the Board’s denial of parole “to the extent that a constitutional or statutory violation has occurred.” The Commonwealth Court’s failure to distinguish its decision in Myers from its holding in Weaver-or for that matter to even cite to Weaver-added to the already confusing jurisprudence.
The Pennsylvania Supreme Court entered the fray in Rogers v. Pennsylvania Board of Probation and Parole, 555 Pa. 285, 724 A.2d 319 (1999), holding that direct appeal is not available- to challenge the denial of parole. Id. However, in a footnote, the Rogers Court made what can be considered as only a passing reference to the question at issue, recognizing the potential viability of. a writ of mandamus. Id. at 323 n. 5. It noted that mandamus “may be available to compel the Parole *444Board to conduct a hearing or to apply the correct law.” Id. (emphasis added). It seems plain enough that saying something “may” be available is not the same as saying something “is” available.
Given the Pennsylvania Supreme Court’s equivocation, we did not consider this to be a conclusive and final clarification of the issue, and we subsequently certified the question to the Pennsylvania Supreme Court. Specifically, we asked:
1. May a person who has been denied parole from a Pennsylvania sentence obtain review from a Pennsylvania state court of a claim that the denial of parole violated the ex post facto clause of the United States Constitution?
2. If so, may review be appropriately secured on direct appeal, through a petition for a writ of mandamus, or in some other manner?
Coady, 251 F.3d at 489. The Pennsylvania Supreme Court advised that where:
discretionary actions and criteria are not being contested but rather the actions of the board taken pursuant to changed statutory requirements are being challenged, an action for mandamus remains viable as a means for examining whether statutory requirements have been altered in a manner that violates the ex post facto clause. Such an action could be brought in the original jurisdiction of the Commonwealth Court. Absent a change in the statutes governing parole, however, denial of parole would generally constitute a discretionary matter that is not subject to review.
Coady, 770 A.2d at 290. Importantly, the Pennsylvania Supreme Court in Coady provided guidance only as to challenges to denials of parole premised on violations of the ex post facto Clause. It specifically held that “parole denial claims are not normally suited to review by way of mandamus.” Id. at 290. It held, moreover, that “[mjandamus will not lie to compel a purely discretionary act.” Id.
Inasmuch as Weaver has never been overruled, we conclude that it is the best indication of how the Pennsylvania Supreme Court would resolve the issues raised by DeFoy. Because the Commonwealth Court’s decision in that case is directly on point, it is highly instructive here. Therefore, a Pennsylvania state prisoner challenging the denial of parole need not file a petition for a writ of mandamus in order to satisfy the dictates of exhaustion.
The Weaver Court held that mandamus is not available to a prisoner denied parole based upon a constitutional error by the parole board. 688 A.2d at 771-72. The Court explained:
Mandamus is based upon a duty by an agency to follow a law and is available only when, under a correct interpretation of that law, the agency has an absolute ministerial duty-no choice-to act in a certain way. Mandamus cannot be used to say that an agency considered improper factors, that its findings of fact were wrong, or that the reasons set forth in its decision are a pretense. If that was the nature of mandamus, there would be no difference between it and an appeal from the agency’s decision or other forms of actions to address those concerns.
Id. at 777 (emphasis added) (footnote omitted). As in Weaver, DeFoy’s refusal to admit guilt was the dispositive-albeit potentially improper-factor in the denial of his parole. As the Weaver Court explains, however, mandamus is not available to review a parole board’s consideration of improper factors. By force of logic, therefore, DeFoy is not entitled to seek a writ of mandamus on his claim.
*445We do not believe the decision of the Pennsylvania Supreme Court in Coady is in conflict with our conclusion. Our certified question in that case concerned the availability of mandamus for challenges to the denial of parole premised solely upon the ex post facto Clause, not upon any and all constitutional protections. In response, the Pennsylvania Supreme Court held that mandamus is available where a challenge to the denial of parole is premised on the ex post facto Clause. In the same breath, however, it held that “[a]bsent a change in the statutes governing parole ... denial of parole would generally constitute a discretionary matter that is not subject to review [via a petition for writ of mandamus].” Coady, 770 A.2d at 290. The Court also explained that “parole denial claims are not normally suited to review by way of mandamus.” Id. A fair reading of Coady suggests a hesitance on the part of the Pennsylvania Supreme Court to permit a writ of mandamus to review the denial of parole.
We therefore read Coady’s holding narrowly, applying only to ex post facto claims. Indeed, if mandamus extended beyond the holding in that case, it would-as the Commonwealth Court explained in Weaver-be no different than a direct appeal. See Weaver, 688 A.2d at 777. And whatever the status of mandamus, it is settled that no direct appeal is available. See Coady, 770 A.2d at 289. Thus, mandamus is not available for Pennsylvania state prisoners seeking to challenge the denial of their parole on constitutional grounds other than the ex post facto Clause.
Accordingly, in answer to the question submitted by the District Court, we conclude that claims of constitutional violations in the denial of parole in Pennsylvania need not be presented to the state courts via a petition for writ of mandamus in order to satisfy the requirement of exhaustion. We reverse the District Court to the extent it held otherwise and remand so the District Court may address the merits of DeFoy’s petition.4
III.
We reverse the judgment of the District Court dismissing DeFoy’s claims as unex-hausted and remand for proceedings consistent with this opinion.
. Under Pennsylvania law, "[a]grant of parole does not eliminate a prisoner's sentence, but instead, the prisoner continues to serve his sentence during which time he or she is the subject of society’s rehabilitation efforts under supervision." Weaver v. Pa. Bd. of Prob. & Parole, 688 A.2d 766, 769 (Pa. Commw.Ct.1997). Once DeFoy violated his parole by committing new crimes, he was *441subject to being recommitted on his armed robbery sentence.
. One of the specific criteria for the treatment phase of the Program stipulates that an inmate must "admit [his] offense,”. See App. at 239.
. There is also a narrow exception to the general mootness rule that rescues DeFoy's petition from being moot. The doctrine of collateral consequences applies where a former prisoner can demonstrate he will suffer some collateral consequences if his conviction is allowed to stand. See Carafas v. LaVallee, 391 U.S. 234, 237-38, 88 S.Ct. 1556, 20 L.Ed.2d 554 (1968); Chong v. Dist. Dir., INS, 264 F.3d 378, 384 (3d Cir.2001). It is a petitioner's burden to demonstrate that collateral consequences exist to avoid having a case dismissed as moot. United States v. Kissinger, 309 F.3d 179, 181 (3d Cir.2002). The Supreme Court has held that the length of a term of supervised release cannot be reduced "by reason of excess time served in prison.” United States v. Johnson, 529 U.S. 53, 60, 120 S.Ct. 1114, 146 L.Ed.2d 39 (2000). Requiring DeFoy to admit his guilt after having consistently denied it may have the collateral consequence of his being indicted for perjury. Therefore, even if DeFoy had already been released from prison, the collateral consequences doctrine would prevent the issue from being moot.
. We do not reach DeFoy's constitutional argument under the Fifth Amendment. He alleges that because Pennsylvania's practice makes parole for any sex offender contingent on participation in the Sexual Offender Treatment Program, and the Program in turn requires that he admit guilt, the Program violates his rights under the Fifth Amendment. We acknowledge that if DeFoy’s allegations are accurate, then he was presented with an unenviable choice: refuse to admit guilt and be ineligible to participate in the Program, thereby losing eligibility for parole, or admit guilt and incriminate himself, providing evidence that would most certainly be used against him in any post-conviction efforts to demonstrate his innocence. However, because the District Court did not certify to us the question of the Program's constitutionality, we express no view.