FOR PUBLICATION
 UNITED STATES COURT OF APPEALS
      FOR THE NINTH CIRCUIT

JONATHAN KING,                            No. 06-55858
             Petitioner-Appellant,
                v.                          D.C. No.
                                         CV-05-03654-JFW
STUART J. RYAN,
                                            OPINION
             Respondent-Appellee.
                                     
       Appeal from the United States District Court
          for the Central District of California
        John F. Walter, District Judge, Presiding

                 Argued and Submitted
           March 9, 2009—Pasadena, California

                    Filed May 5, 2009

   Before: Michael Daly Hawkins, Marsha S. Berzon and
            Richard R. Clifton, Circuit Judges.

                Opinion by Judge Berzon




                           5241
                     KING v. RYAN                5243




                     COUNSEL

Fay Arfa (argued) of Fay Arfa, A Law Corporation, Los
Angeles, California, for petitioner-appellant King.
5244                         KING v. RYAN
David Fredric Glassman (argued) and G. Tracey Letteau of
the Office of the California Attorney General, Los Angeles,
California, for respondent-appellee Ryan.


                              OPINION

BERZON, Circuit Judge:

   Jonathan King appeals from the district court’s order dis-
missing his petition for a writ of habeas corpus. King filed a
“mixed” habeas petition in federal court — that is, one includ-
ing both exhausted and unexhausted claims — just two days
before the end of the one-year statute of limitations applicable
under the Anti-Terrorism and Effective Death Penalty Act
(“AEDPA”). See 28 U.S.C. § 2244(d)(1). King then asked the
district court to stay the petition and dismiss his unexhausted
claims so that he could exhaust them in state court before
adding them back into the stayed federal petition, thereby
invoking the three-step procedure outlined by this Court in
Kelly v. Small, 

(9th Cir. 2002) (hereinafter “the
Kelly procedure”).

   The district court denied King’s request. Instead, it ordered
King to either abandon his unexhausted claims and proceed
with his exhausted claim or dismiss the entire action without
prejudice. King did neither. The district court then dismissed
King’s unexhausted claims and allowed the case to proceed
only with respect to King’s one remaining fully-exhausted
claim.1 We hold that, in doing so, the district court applied an
erroneous legal standard. Contrary to the district court’s order,
the Kelly procedure remains available after the Supreme
Court’s decision in Rhines v. Weber, 

(2005),
and unlike the procedure permitted by Rhines, does not
require that a petitioner show good cause for his failure to
  1
   King does not appeal the court’s subsequent dismissal of this claim on
the merits.
                          KING v. RYAN                      5245
exhaust state court remedies. We nonetheless affirm the dis-
missal because the error was harmless: as explained below,
King fares no better under the Kelly standard we apply today
than he did under the district court’s analysis.

                               I.

   King is currently serving a 32-year sentence for two counts
of attempted second-degree robbery, two counts of second-
degree robbery, two counts of assault with a firearm, and one
count of willfully evading a pursuing police officer. King
unsuccessfully appealed his conviction to the California Court
of Appeal and then to the California Supreme Court, which
affirmed in an order that became final on May 18, 2004. On
May 16, 2005, King filed a habeas petition in U.S. District
Court, just two days before the end of AEDPA’s one-year
limitations period. See 28 U.S.C. § 2244(d)(1).

   King’s habeas petition acknowledged that nine of his ten
claims were unexhausted at the time of filing. On May 18,
2005, King filed a motion appearing to invoke the three-step
procedure outlined in Kelly, which affirmed the three-step
stay and abeyance procedure first articulated in Calderon v.
U.S. Dist. Ct. (Taylor), 

, 986 (9th Cir. 1998).
Pursuant to the Kelly procedure, (1) a petitioner amends his
petition to delete any unexhausted claims; (2) the court stays
and holds in abeyance the amended, fully exhausted petition,
allowing the petitioner the opportunity to proceed to state
court to exhaust the deleted claims; and (3) the petitioner later
amends his petition and re-attaches the newly-exhausted
claims to the original petition. 

; see
also Part III infra. Following Kelly’s outline, but without cit-
ing that case by name, King requested that the district court
“dismiss [his] unexhausted claims,” and proposed that “after
exhausting the new claims in state court,” he would return to
federal court and “file a First Amended Petition reasserting
the previously unexhausted claims.”
5246                      KING v. RYAN
   Later in the same motion, however, King expressly refer-
enced the U.S. Supreme Court’s decision in Rhines. Rhines
declared that “in limited circumstances,” federal district
courts have the authority to stay a mixed habeas petition and
hold the entire petition — exhausted and unexhausted claims
alike — in abeyance while the petitioner returns to state court
to exhaust his remedies 

; see also Part
III infra. The procedure set out in Rhines is less cumbersome
for a petitioner than the Kelly procedure, but importantly, it is
available only upon a showing that the petitioner had good
cause for not exhausting his state claims 

. Citing Rhines, King’s motion asserted that he had dem-
onstrated good cause for his failure fully to exhaust his peti-
tion, and asked that the district court exercise its discretion to
“stay the petition pending exhaustion.”

   In other words, King proposed two different approaches to
his mixed petition: one (Kelly) which would not require good
cause but also would not leave the entire mixed petition pend-
ing in district court, and a second (Rhines) which would
require a good cause showing and would leave the entire
mixed petition pending in district court.

   On May 24, 2005, before the district court ruled on his
motion, King filed a state habeas petition in Los Angeles
County Superior Court, raising all nine of his unexhausted
claims. After the Superior Court denied the petitions and
King’s state court appeal failed, King petitioned for review to
the California Supreme Court. While the state habeas pro-
ceedings were pending, the magistrate judge assigned to
King’s federal habeas case issued a Report and Recommenda-
tion (R&R) in which he recommended denying King’s request
for a stay and also recommended that King be ordered to
either delete all nine of his unexhausted claims and proceed
with his one exhausted claim or dismiss the entire petition and
file a new petition after exhausting his state court remedies.
The magistrate judge discussed the requirements outlined in
Rhines and determined that King had not demonstrated “good
                             KING v. RYAN                           5247
cause” for failure to exhaust nine of his ten claims. The R&R
contained no discussion of the alternative Kelly procedure.

   King filed an objection to the magistrate judge’s R&R,
arguing that he did have good cause for his failure to exhaust
his state remedies. On October 7, 2005, the district court
adopted the magistrate judge’s R&R. Unlike the magistrate
judge, the district court recognized that King’s motion most
clearly tracked the three-step stay-and-abeyance procedure
outlined in Kelly, and it proceeded to analyze the motion
under that rubric. The district court held, however, that
Rhines’s good cause standard applies to the Kelly procedure
as well, reasoning that both Kelly and Rhines are directed at
solving the same problem — namely, the interplay between
AEDPA’s one-year statute of limitations and the total exhaus-
tion requirement first articulated in Rose v. Lundy, 

(1982). See Part II infra. The district court then rejected
King’s good cause argument.

   In addition, the court stated, “even assuming the [Rhines]
good cause standard does not apply to the Ninth Circuit’s
three step procedure [outlined in Kelly], it is not at all clear
that the [Kelly] procedure benefits petitioner.” The court pro-
vided two related reasons why that might be so: First, at the
time King requested a stay, the one-year limitations period
had already run, so King could not possibly exhaust his
claims in state court and return to federal court in time to file
his claims. Second, “the recent Supreme Court decision in
Mayle v. Felix, [

(2005)], might significantly
limit [King’s] ability to have his amended claims ‘relate back’
to the filing of the original petition,” making it problematic
for King to add them to his petition after the one-year period
expired. (Internal citations and quotation marks omitted.)2 The
court concluded that either way, “it appears the better
  2
    Mayle v. Felix, 

(2005), establishes the circumstances in
which amended claims in a habeas petition “relate back” to the filing date
of the original petition. See Part IV infra.
5248                      KING v. RYAN
approach for petitioner would have been to seek a stay of the
mixed Petition (i.e., the Rhines approach) instead of seeking
to follow the [Kelly] three-step approach.”

   Denying King’s motion to stay the petition and dismiss the
unexhausted claims, the district court ordered King to file
within five days either a notice of abandonment of the unex-
hausted claims or a request to dismiss the entire action with-
out prejudice. The district court’s order went on to state that
“[i]f no written response is received within five days of the
filing date of this Order, . . . the Court will dismiss the unex-
hausted claims and order further proceedings with respect to
the one exhausted claim in the Petition.” King did not respond
to the district court’s order, and on November 2, 2005, the
district court dismissed the unexhausted claims and referred
the matter back to the magistrate judge for adjudication of the
one remaining, exhausted claim.

   That same day, approximately forty minutes before the dis-
trict court’s order was filed, the California Supreme Court
denied King’s petition for review on the merits, at which
point the nine previously-unexhausted claims were fully
exhausted. King promptly filed a motion for reconsideration
with the district court, drawing the district court’s attention to
the California Supreme Court’s ruling. The district court
denied King’s motion for reconsideration, explaining that its
decision to deny King’s motion to stay his petition was final
as of October 7, 2005, and that the California Supreme
Court’s ruling therefore came too late to salvage the nine orig-
inally unexhausted claims.

   King next requested leave to file an amended habeas peti-
tion with the district court which included his nine newly-
exhausted claims, citing neither Kelly nor Rhines, but only
Federal Rule of Civil Procedure 15(a). On January 6, 2006,
the district court once again refused King’s request, this time
stating that the proposed amendment was improper because
those nine claims had been dismissed with prejudice
                                KING v. RYAN                              5249
(although the district court had not so stated in its previous
order) and also because they were now time-barred under
AEDPA. Consequently, the district court proceeded to con-
sider King’s one originally-exhausted claim, which it ulti-
mately dismissed on the merits.

   King now appeals both the district court’s refusal to imple-
ment the three-step procedure in Kelly and its denial of his
motion to file a first amended complaint. This court granted
a certificate of appealability on four issues: (1) whether the
Kelly three-step procedure for staying a fully exhausted
habeas petition remains available after Rhines; (2) if so,
whether a petitioner seeking to stay a fully exhausted petition
pursuant to the Kelly three-step procedure must demonstrate
good cause for the failure to exhaust claims in state court, as
is required for the stay of a mixed petition under Rhines; (3)
whether King demonstrated good cause for his failure to
exhaust nine of his ten claims in state court; and (4) whether,
after dismissing the nine unexhausted claims, the district court
erred in denying King leave to file a first amended petition
under FRCP 15(a), where the newly-exhausted claims sought
to be added were the same as those raised in the original petition.3

   We would not need to address the first and second certified
issues if we determined that King had demonstrated good
cause under Rhines for his failure to exhaust his state court
  3
    Notably absent from the certificate of appealability is the question
whether the district court abused its discretion in denying King’s Novem-
ber 8 motion for reconsideration premised on the fact that all nine of
King’s previously unexhausted claims had been fully exhausted by the
time the district court issued its November 2 order. Because this issue was
not covered in the certificate of appealability or raised in King’s opening
brief to this court, we do not address it. See 9th Cir. R. 22.1(e)
(“Petitioners shall brief only issues certified by the district court or the
court of appeals. Alternatively, if a petitioner concludes during the course
of preparing the opening brief, that an uncertified issue should be dis-
cussed in the brief, the petitioner shall first brief all certified issues under
the heading, ‘Certified Issues,’ and then, in the same brief, shall discuss
any uncertified issues under the heading, ‘Uncertified Issues.’ ”).
5250                      KING v. RYAN
remedies before filing his petition in federal court. In its Octo-
ber 7 order, adopting the magistrate judge’s R&R, the district
court rejected King’s good cause argument both because it
was based on factual allegations not presented to the magis-
trate judge, and because those factual allegations were hear-
say and insufficiently detailed to establish good cause. Given
our deferential standard of review of both the district court’s
good cause finding and its refusal to consider new evidence
submitted in opposition to the magistrate’s findings, see
Brown v. Roe, 

, 744 (9th Cir. 2002), we conclude
that the district court did not abuse its discretion in finding no
good cause and refusing to allow King a stay under Rhines.

  We discuss the remaining issues in turn below.

                               II.

   [1] Habeas petitioners have long been required to adjudi-
cate their claims in state court — that is, “exhaust” them —
before seeking relief in federal court. See, e.g., United States
ex rel. Kennedy v. Tyler, 

, 17-19 (1925); Ex parte
Royall, 

(1886); Act of June 25, 1948, ch. 646,
62 Stat. 869, 967 (codified as amended at 28 U.S.C.
§ 2254(b)). This requirement is “grounded in principles of
comity[,] as it gives states the first opportunity to address and
correct alleged violations of state prisoner’s federal rights.”
Wooten v. Kirkland, 

, 1023 (9th Cir. 2008)
(internal quotation marks omitted). The current statutory
exhaustion requirement prevents a federal court from granting
habeas relief “unless it appears that . . . the applicant has
exhausted the remedies available in the courts of the State.”
28 U.S.C. § 2254(b)(1)(A).

   In 1982, the U.S. Supreme Court interpreted the exhaustion
rule in the habeas context as requiring “total exhaustion” of
“mixed” petitions — that is, those petitions that contain both
exhausted and unexhausted claims. 

.
Rose required district courts to dismiss a mixed petition,
                            KING v. RYAN                        5251
“leaving the prisoner with the choice of returning to state
court to exhaust his claims or of amending or resubmitting the
habeas petition to present only exhausted claims to the district
court.” 

   [2] The 1996 passage of AEDPA, which imposes a one-
year statute of limitations on the filing of habeas petitions in
federal court, see 28 U.S.C. § 2244(d)(1), greatly changed the
practical impact of Rose’s total exhaustion principle.
AEDPA’s one-year limitations period meant that petitioners
whose mixed petitions were dismissed under Rose ran the risk
of being time-barred from bringing their claims again, once
exhausted, in federal court. To address this problem, this Cir-
cuit developed a three-step procedure for mixed petitions,
allowing (1) a petitioner to amend his petition to delete any
unexhausted claims; (2) the court in its discretion to stay and
hold in abeyance the amended, fully exhausted petition, pro-
viding the petitioner the opportunity to proceed to state court
to exhaust the deleted claims; and (3) once the claims have
been exhausted in state court, the petitioner to return to fed-
eral court and amends his federal petition to include the
newly-exhausted claims. See 

. We
have reaffirmed Taylor’s three step stay-and-abeyance proce-
dure several times in the ten years since it was first articu-
lated. See, e.g., Robbins v. Carey, 

, 1148-49
(9th Cir. 2007); 

, overruled on
other grounds by Robbins, 481 F.3d at 1049;4 James v. Pliler,

, 1127 (9th Cir. 2001) (holding that the decision
to hold an exhausted petition in abeyance is a matter of trial
court’s discretion).

   [3] In Kelly, this Court expressed concern that circum-
stances might arise in which the “outright dismissal [of a
mixed petition would] render it unlikely or impossible for the
petitioner to return to federal court within the one-year limita-
  4
   Robbins reaffirmed Kelly but rejected the requirement that district
courts sua sponte consider implementing the three-step procedure.
5252                     KING v. RYAN
tion period imposed by 

. To
avoid this problem, we joined “the ‘growing consensus’ in
recognizing the clear appropriateness of a stay when valid
claims would otherwise be forfeited.” Id.; see also Olvera v.
Giurbino, 

, 574 (9th Cir. 2004) (finding an abuse
of discretion where the district court failed to grant a stay if
the petitioner could not have exhausted his claims and
returned to federal court within AEDPA’s deadline).

   [4] Three years after Kelly, the Supreme Court, in Rhines,
considered “whether a federal district court has discretion to
stay [a] mixed petition to allow the petitioner to present his
unexhausted claims to the state court in the first instance, and
then return to federal court for review of his perfected peti-
tion.” 

. Given the interplay
between Rose and AEDPA, and the consequent need to pro-
tect against the risk that habeas petitioners with mixed peti-
tions might “forever los[e] their opportunity for any federal
review of their unexhausted claims,” 

Rhines carved
out “limited circumstances” in which it is within the district
court’s discretion to grant a stay of a mixed petition. 

Rhines cautioned, however, that its stay procedure must
not run afoul of AEDPA’s twin purposes — “reduc[ing]
delays in the execution of state and federal criminal sen-
tences,” 

(internal quotation marks and citations
omitted), and “encourag[ing] petitioners to seek relief from
state courts in the first instance.” 

these con-
cerns, Rhines held that “stay-and-abeyance is only appropriate
when the district court determines there was good cause for
the petitioner’s failure to exhaust his claims first in state
court.” Furthermore, Rhines held stays inappropriate when the
unexhausted claims are “plainly meritless,” or where the peti-
tioner has engaged in “abusive litigation tactics or intentional
delay.” 

  Shortly after Rhines, in Jackson v. Roe, 

(9th
Cir. 2005), this Court noted the important distinctions
between the Rhines and Kelly procedures. As Jackson
                         KING v. RYAN                      5253
explained, Rhines allows a district court to stay a mixed peti-
tion, and does not require that unexhausted claims be dis-
missed while the petitioner attempts to exhaust them in state
court. In contrast, the three-step procedure outlined in Kelly
allows the stay of fully exhausted petitions, requiring that any
unexhausted claims be dismissed. 

Because the peti-
tioner in Jackson attempted to use the Rhines procedure, we
had no occasion to decide whether the Kelly procedure
remains available after Rhines. Although we noted that “be-
cause Rhines . . . authorize[s] stays of mixed petitions, albeit
in limited circumstances, the three-step procedure may fall
into disuse,” 

n.10, we “[left] for another day the
question of whether the stay standard announced by the
Supreme Court in Rhines applies to [the] three-step [Kelly]
procedure.” 

                              III.

   The case now before us picks up where Jackson left off.
King argues that the district court erred in refusing to allow
him to use the three-step procedure outlined in Kelly and Tay-
lor. He maintains that the district court should have allowed
him to dismiss his unexhausted claims, stay his fully
exhausted petition, and file an amended petition containing all
his claims once they had been exhausted, without requiring a
showing of good cause for his failure to exhaust earlier. For
the reasons explained below, we reiterate that the Kelly proce-
dure remains available after Rhines and hold that its availabil-
ity is not premised upon a showing of good cause.

   [5] As we recognized in Jackson, “Rhines did not . . . com-
ment on the validity of the three-step stay-and-abeyance pro-
cedure approved in Taylor and 

.
Although the Kelly procedure may appear to be nothing more
than a more cumbersome version of Rhines that requires the
dismissal and then the re-amendment of the unexhausted
claims, we cautioned in Jackson that “[t]he two approaches
are distinct: Rhines applies to stays of mixed petitions,
5254                     KING v. RYAN
whereas the three-step procedure applies to stays of fully
exhausted petitions . . . .” 

this observation
in Robbins, noting that Rhines “approved a version of the
stay-and-abeyance 

(footnote
omitted). We also held that “[the Kelly procedure] remains in
place for district courts” after Rhines. 

Although
Robbins held that the Kelly procedure survives Rhines, it did
not directly address whether the Rhines “good cause” limita-
tion applied to the Kelly procedure. We address that question
now and decide that it does not.

   [6] Rhines carved out an exception to Rose’s total exhaus-
tion rule, allowing a mixed petition to remain pending in fed-
eral court under limited circumstances. When implemented,
the Rhines exception eliminates entirely any limitations issue
with regard to the originally unexhausted claims, as the claims
remain pending in federal court throughout. It was to prevent
abuse of this special dispensation, and to preserve the central
purposes of the total exhaustion rule (avoiding delay and
piecemeal litigation), that the Supreme Court in Rhines lim-
ited the availability of the exception to circumstances in
which the petitioner had good cause for his failure to exhaust
all his claims in state court before filing his federal habeas
petition.

   [7] In contrast, the Kelly procedure, because it does not
leave a mixed petition pending, does not sanction any excep-
tion to Rose and so does not present the same dangers of
abuse. Indeed, Kelly is not only a more cumbersome proce-
dure for petitioners, but also a riskier one. A petitioner seek-
ing to use the Kelly procedure will be able to amend his
unexhausted claims back into his federal petition once he has
exhausted them only if those claims are determined to be
timely. And demonstrating timeliness will often be problem-
atic under the now-applicable legal principles.

  [8] Under Duncan v. Walker, 

(2001), the fil-
ing of a petition for federal habeas corpus relief does not toll
                          KING v. RYAN                      5255
AEDPA’s statute of limitations (unlike an application for
state habeas corpus relief, which does). 

Addition-
ally, Mayle provides that a petitioner may amend a new claim
into a pending federal habeas petition after the expiration of
the limitations period only if the new claim shares a “common
core of operative facts” with the claims in the pending peti-
tion, 

; a new claim does not “relate
back” to the filing of an exhausted petition simply because it
arises from “the same trial, conviction, or sentence.” 

Because the Kelly procedure requires petitioners to
dismiss their unexhausted claims and then attempt to add
them back into the federal complaint later, the Kelly proce-
dure, unlike the Rhines procedure, does nothing to protect a
petitioner’s unexhausted claims from untimeliness in the
interim. And Duncan and Mayle, taken together, make dem-
onstrating timeliness of claims amended into federal habeas
petitions after exhaustion often problematic.

   [9] Given these strictures, the Kelly procedure is therefore
unlikely to be abused by late-filing habeas petitioners who
have not exhausted all of their federal claims and for whom
the expiration of AEDPA’s one-year limitations period is
imminent. Nor does the Kelly procedure involve any excep-
tional judicial action. It is in part an exercise of litigants’
usual prerogative, specifically recognized in Rose, to amend
complaints if they can do so to make them cognizable in fed-
eral court, see 

(“[The petitioner] can
always amend the petition to delete the unexhausted claims,
rather than returning to state court to exhaust all of his
claims.”), and in part an exercise of the equally normal discre-
tion of federal courts to control the timing of decision in cases
pending before them. See O’Neill v. United States, 

, 687 (9th Cir. 1995) (“[T]he district courts are entitled to
discretion in managing cases within the federal system.”).

   [10] In short, nothing about the Kelly procedure goes suffi-
ciently beyond normal court procedures or raises such ele-
vated concerns about possible abuse to require the imposition
5256                      KING v. RYAN
of a special standard such as “good cause.” We therefore hold
that district courts retain the same degree of discretion they
had before Rhines to implement the Kelly procedure, particu-
larly when “outright dismissal [of an entire mixed petition
would] render it unlikely or impossible for the petitioner to
return to federal court within the one-year limitation period
imposed by [AEDPA].” 

. We further
reiterate the “clear appropriateness of a stay when valid
claims would otherwise be forfeited.” 

holding does not decide the case in King’s favor, how-
ever. As we noted in Jackson, and as we recognize again here,
“the Supreme Court’s . . . decision in Mayle, imposing stricter
limitations than previously required by this court for amend-
ments to relate back to the original filing date, is likely to
make . . . [the Kelly] approach less useful for petitioners in
many 

n.10. The case now before
us is one such instance. Indeed, the district court recognized
as much when it refused to invoke the Kelly procedure as
King requested, noting that Mayle “might significantly limit
[King’s] ability” to amend his nine initially unexhausted
claims back into his federal petition. Furthermore, in the dis-
trict court’s subsequent order of January 6, 2006, denying
King’s motion for leave to file a first amended petition pursu-
ant to FRCP 15(a) (which was filed subsequent to and inde-
pendent from King’s motion requesting a stay and abeyance
under Kelly), the district court held more explicitly that “after
examining petitioner’s exhausted and unexhausted claims, it
does not appear that any of petitioner’s unexhausted claims
would relate back to the date of petitioner’s original filing, as
the one exhausted claim and the nine unexhausted claims are
not tied to a common core of operative facts.”

   King challenges in only one respect the district court’s
finding that his claims do not relate back under Mayle: he
urges that Mayle is satisfied so long as his new claims are
                         KING v. RYAN                      5257
related to any of the claims that appeared (properly or not) in
the original petition he filed with the district court. Because
King’s nine new claims are the same as the nine unexhausted
claims he attempted to include in his original petition, he
asserts, the new claims are sufficiently related to the original
filing date to be considered timely under Mayle.

   We disagree. The only sensible interpretation of Mayle is
that it requires new claims to relate back to claims properly
contained in the original petition — that is, those claims that
were exhausted at the time of filing. Only this interpretation
of Mayle comports with Duncan’s reasoning about the goal of
exhaustion in habeas cases. Wary of “creat[ing] . . . opportu-
nities for delay and piecemeal litigation without advancing the
goals of comity and federalism that the exhaustion require-
ment 

, Duncan concluded that
AEDPA’s statute of limitations period must continue to run
while federal habeas proceedings are 

. “By tolling the limitation period for the pursuit of state
remedies and not during the pendency of applications for fed-
eral review,” Duncan reasoned, “[we] provide[ ] a powerful
incentive for litigants to exhaust all available state remedies
before proceeding in the lower federal courts.” 

Reading Mayle to permit post-exhaustion amendments to “re-
late back” to any claims included in but then dismissed from
the original complaint, as King suggests we should, would be
equivalent to abandoning Duncan and simply tolling
AEDPA’s limitations period for the entire period during
which a petitioner has a petition pending in federal court, so
long as the petitioner had the foresight to include all of his
unexhausted claims in the petition when he initially filed it.

   [11] Rejecting such a self-defeating interpretation, we hold
that Mayle requires a comparison of a petitioner’s new claims
to the properly exhausted claims left pending in federal court,
not to any earlier version of the complaint containing claims
subsequently dismissed for failure to exhaust. Cf. Raspberry
v. Garcia, 

(9th Cir. 2006) (holding that a
5258                      KING v. RYAN
habeas petition filed after the district court dismissed a previ-
ous petition without prejudice for failure to exhaust state court
remedies does not automatically “relate back” to the filing
date of the original petition). Mayle thus requires a more
detailed inquiry than King suggests. The question is whether
his nine newly exhausted claims relate back to the one claim
in his original habeas petition that was exhausted to begin
with — King’s claim that he was denied his due process right
to a fair trial because there was insufficient evidence to sus-
tain the twenty-year gun enhancement applied to his sentence.

   [12] Critically, King in his briefs before this court does not
address the relevant Mayle question, making no attempt to
argue that his nine previously unexhausted claims share a
“common core of operative facts” with his one exhausted
claim. 

. As King has therefore waived
any challenge to the district court’s holding that his new
claims do not relate back to his original exhausted claim, we
do not disturb that holding.

                          Conclusion

   In sum, we hold that the three-step stay-and-abeyance pro-
cedure outlined in Kelly remains available. Although this pro-
cedure might not be as useful for petitioners today in avoiding
untimeliness as it was when Kelly was decided, district courts
still maintain discretion to implement Kelly’s three-step stay-
and-abeyance procedure, particularly when “outright dis-
missal [of a mixed petition would] render it unlikely or
impossible for the petitioner to return to federal court within
the one-year limitation period imposed by [AEDPA].” 

. The propriety of this option does not turn
on the petitioner showing good cause for his failure to exhaust
state court remedies. Instead, a petitioner may invoke Kelly’s
three-step procedure subject only to the requirement that the
amendment of any newly exhausted claims back into the peti-
tion must satisfy 

. Because the district
court found that King did not satisfy Mayle, and the sole chal-
                        KING v. RYAN                   5259
lenge King raises is based on an erroneous reading of Mayle,
we affirm the district court.

  AFFIRMED.