Superstabilizing mutual exclusion.
A superstabilizing protocol is a protocol that (i) is self-stabilizing, meaning that it can recover from an arbitrarily severe transient fault; and (ii) can recover from a local transient fault while satisfying a passage predicate during recovery. This paper investigates the possibility of superstabilizing protocols for mutual exclusion in a ring of processors, where a local fault consists of any transient fault at a single processor; the passage predicate specifies that there be at most one token in the ring, with the single exception of a spurious token colocated with the transient fault. The first result of the paper is an impossibility theorem for a class of superstabilizing mutual exclusion protocols. Two unidirectional protocols are then presented to show that conditions for impossibility can independently be relaxed so that superstabilization is possible using either additional time or communication registers. A bidirectional protocol subsequently demonstrates that superstabilization in <i>O</i>(1) time is possible. All three superstabilizing protocols are optimal with respect to the number of communication registers used.
Introduction
The notion of superstabilization is introduced in [DH95] as a refinement of (self-) stabilization.
Superstabilization continues the trend of recent research that combines stabilization with other
forms of fault handling [AG93, GP93, BB95]. The main attraction of stabilization is the
possibility of software that initializes itself without requiring an external signal, which can
be useful in the presence of transient faults or in distributed systems that asynchronously
reconfigure (perhaps in the normal course of phased computation). Stabilizing protocols are
typically engineered for the worst case of a transient fault and are not designed to mask the most
likely cases of faults or reconfigurations. Fault-tolerant behavior has been classified as either
masking or nonmasking in [AG93]. Briefly put, a protocol is masking fault-tolerant if its users
A preliminary report of this research appears in Proceedings of the International Conference on Parallel
and Distributed Processing Techniques and Applications PDPTA'95, pp. 31-40, 1995.
do not observe illegitimate protocol behavior during recovery after a fault: error-correcting
codes, for example, mask faults within the limit of their tolerances. Stabilizing protocols are
nonmasking, meaning that an observer of a protocol can witness corrupted output variables
and incorrect behavior up to the point where recovery is complete. Superstabilization can be
viewed as a partial masking technique for likely cases of transient faults and reconfigurations,
while retaining stabilization to deal with arbitrarily severe transient faults.
The focus of stabilization is convergence to a stable, legitimate behavior from an arbitrary
initial state. The choice of an arbitrary initial state models the worst case possibility for a
transient failure in a system: all the program counters, internal registers, channels, and so on
could be set to unpredictable and inconsistent values by a transient fault. But a transient
fault does not destroy code or hardware, and this fact enables a system to restore its state,
after some convergence period, to proper behavior. The system behavior during convergence
is typically not a concern, since it is not generally possible to make any guarantees beyond
achieving convergence in the event of a severe transient fault. Superstabilization offers the
following refinement: in addition to stabilization, a protocol may be able to guarantee certain
safety properties during the period of convergence following a transient fault, provided that
the transient fault is limited. This refinement is attractive if a system is unlikely to encounter
severe transient faults, whereas certain limited transient faults occur relatively often.
An application of stabilization proposed in [DIM93] is to the domain of dynamic systems:
an initial state comes about as the result of online system reconfiguration. In a dynamic
system, protocols at the network layer may be required to deal with a dynamic topology, where
processors and links are added and removed concurrently with protocol operation. Because
stabilizing protocols can deal with any initial state, they can also be applied to situations of
dynamic reconfiguration. Superstabilization is investigated in [DH95] under the assumption
that dynamic topology change events generate interrupts at affected processors.
The contribution of this research is to show that principles of superstabilization are also applicable
to situations other than network reconfigurations with interrupts. The fundamental (and
familiar) problem of mutual exclusion is investigated, with the idea of making safety guarantees
for cases of limited transient faults. The system model is an oriented ring of processors that
communicate using atomic link registers. The starting point is a version of Dijkstra's stabilizing
K-state protocol [D74] adapted to the processor-register model. The class of local transient
faults consists of processor-local faults, meaning that a transient fault can change a processor's
program counter and internal variables. We do not assume that such processor-local faults
generate interrupts or any other kind of notification.
A desirable passage predicate is that the mutual exclusion property be maintained, meaning
there should be no two simultaneous "token holders" in the system following a processor-local
fault in a legitimate state. Such a passage predicate may not be feasible; for instance, if
we equate critical section execution with token-holding, a processor-local fault could always
set a processor's program counter so that the processor's next action occurs within the critical
section - making it impossible to prevent two processors from simultaneous execution of their
critical sections following a processor-local fault. If it is impossible to prevent two simultaneous
token holders after a fault, then at least the system should contain the effect of the fault: no
spurious token injected by a fault should propagate to other processors. Note that techniques
used to contain processor-local faults might also be useful in the context of a hierarchically
layered system design, where it is desirable to confine the effect of faults within layer and
module boundaries. Three protocols described in this paper successfully contain processor-
local faults; thus the critical section execution could be placed at a higher layer than the token
circulation protocol to mask processor-local faults. We do not elaborate on such layering in
this paper; instead we concentrate on the following (feasible) passage predicate: at all times,
there is at most one token holder with the single exception of a temporary spurious token
located at a processor-local fault.
Observations of the preceding paragraph indicate that fault-masking (at least at the level explored
in this research) is incomplete. Following a processor-local fault, the protocol can be
in an illegitimate state. However, the illegitimate states observable in such circumstances all
satisfy the passage predicate; the fault is not entirely masked, but the blow is softened. Perhaps
the notion of fault-containment [CRD+95, N90] is closer in spirit to superstabilization
than is fault-masking. Although techniques from existing work from either fault-masking or
fault-containment research may be adapted for purposes of superstabilization, the additional
constraint of stabilization gives the present research a new twist: any fault-masking or containment
apparatus must itself be able to survive an arbitrary transient fault as well as dealing
with the limited faults for which it is primarily intended.
Organization of Paper. The computing model (processors and atomic registers), stabiliz-
ation, superstabilization, and some performance measures for this paper are defined in Section
2. In Section 3 the problem of mutual exclusion in a ring is introduced: Dijkstra's stabilization
mutual exclusion protocol is presented in the processor-register model, processor-local faults
are introduced, and we consider examples to motivate techniques needed for superstabilization.
Section 3 also defines legitimacy and a passage predicate for the ring of processors, and the
section ends with a proof of impossibility of superstabilization under certain resource and time
constraints. Section 4 describes two unidirectional superstabilizing protocols. Neither of these
protocols achieves the optimum recovery time for a processor-local fault, and Section 5 presents
results to indicate this optimum recovery time likely requires a bidirectional protocol. Section
6 shows that optimal recovery time from a processor-local fault is possible in a bidirectional
ring. Section 7 contains concluding remarks.
System Model
The system consists of an oriented ring of n processors, numbered 0 through (n \Gamma 1). The
neighbors of processor
processor identities is conducted modulo n. Processors are modeled as conventional sequential
machines with program counters and internal variables. Program statements refer to variables
by unsubscripted names; in proofs we denote the location of a variable by subscript, for instance
Each variable has a finite domain of possible values.
Processors communicate by reading and writing registers. Each register has a finite domain of
possible values, and can be written by one processor and read by one processor. This implies,
for instance, that if processor i writes register R ij that processor j reads, then processor i is not
allowed to read register R ij . In the literature of registers [HV95], this type of register is termed
a single-reader single-writer register, denoted 1W1R. Were processor i permitted to read R ij
as well, then the register would be of type 1W2R. In keeping with the ring topology, a register
by i and read by j can only be defined if (j \Gamma
1). The ring is unidirectional if (j every register R ij .
A local state for a processor i is a specification of values for i's program counter and all of i's
internal variables. A global state is a specification of local states for all processors and values
for all registers. A state predicate is a specification of some set of global states.
A processor step is the execution of some local transition (changing internal variables and
program counter), a register read, or a register write. Each processor step is atomic, initiating
and completing with no temporal overlap with any other processor step. Each step is thus a
global state transition representable by a pair of global states. A computation is an infinite
sequence of global states so that every consecutive pair of states in the sequence is some
processor step (at any global state, some step is enabled in our protocols, so the notion of
infinite computation is justified in all cases). A computation segment is a finite, contiguous
subsequence of a computation. A computation is fair if it contains infinitely many steps of
each processor. All arguments about protocol behavior in this paper assume fair computations.
A processor-local fault at processor i is an atomic event that sets all the variables of i and
the program counter of i to arbitrary values within their domains. A processor-local fault
does not change the value of a register. Because a processor-local fault is not a processor
step, no computation includes a fault: we reason about fault tolerance by proving properties
of computations that begin with a state generated by a fault.
The legitimate states of a protocol are usually characterized by a predicate with respect to
some desired property. Let L be the weakest (most inclusive) set of states that is closed
(any processor step starting from a state in L results in some state in L), convergent (every
computation, starting from any arbitrary state, eventually contains some state in L), and every
state in L satisfies a given property P . We call L the set of legitimate states for a protocol,
or equivalently, L is called the legitimacy predicate. If there exists such a predicate L for a
protocol with respect to a given P , then we say the protocol is stabilizing with respect to P .
Where P is understood from context we simply call a protocol stabilizing. From this definition,
it follows that every protocol is stabilizing with respect to the predicate P j true. For mutual
exclusion, P specifies that no two processors have program counters in the critical section.
Note that for reactive protocols, such as mutual exclusion, the predicate P is inadequate to
describe all desired properties; we need also to specify and prove that a liveness property holds
of a computation (e.g., every process obtains a token infinitely many times). The definition of
stabilization can be extended to include desired liveness properties, but it is not useful to do
so for the results in this paper.
Let oe be a legitimate state and let oe 0 be obtained by applying a processor-local fault to oe; we call
oe 0 a 1-faulty state. A protocol is superstabilizing with respect to (P ; Q) if it is stabilizing with
respect to P and every computation starting from a 1-faulty state satisfies predicate Q at all
states. Predicate Q is called the passage predicate for the protocol. Again, where P and Q are
understood from context, we simply say that a protocol is superstabilizing. Every stabilizing
protocol is superstabilizing with respect to the passage predicate true; for superstabilization
to be interesting, the passage predicate should satisfy some useful safety properties.
All the protocols in this paper are specified by programs that infinitely iterate through a sequence
of statements including read and write register statements. A segment of a computation
is called a cycle of processor i if it contains steps of processor i corresponding to a complete
iteration of i's program, from the first statement until the program jumps back to the first state-
ment. Note that a segment may start at some state oe where i's program counter is positioned
in the middle of i's iteration; in this case, steps of i must complete this partial iteration and
then complete an entire iteration before the segment is a cycle of i. Depending on the choice
of oe, a cycle could thus contain "one and one-half" iterations of i in a cycle. Also observe that
one cycle of processor i could be many cycles of some other processor j.
For the asynchronous model of processors and registers, we use the notion of a "round" to
measure the (concurrent) time for progress of events in a computation. Informally, a round is
a unit of time sufficient for all processors to complete a cycle. Formally, a complete round is a
computation segment that includes at least one cycle for every processor. A minimal round is
a complete round for which no proper subsegment is a complete round; in the sequel, we use
round to denote a minimal round. Any fair computation is a concatenation of rounds, which
enables us to refer to the k th round of a computation.
The stabilization time of a protocol is the worst-case number of rounds, for any initial state, in
a computation before a legitimate state is reached. The superstabilization time of a protocol
is the worst-case number of rounds, for any initial 1-faulty state, in a computation before a
legitimate state is reached. Stabilization time measures how efficiently a protocol copes with the
worst case for a transient fault and superstabilization time measures the worst-case recovery
time for a single, processor-local fault from a legitimate state.
The following two definitions will be used to describe best-case times for token circulation in
a ring. A (minimal) round is simple if it is the concatenation of n segments, each of which
contains steps of only one processor. A round is linear if it is simple or it is the concatenation
of (n each containing steps of only one processor, such that the first and last
segment have steps of the same processor.
3 Stabilizing Mutex
We consider the problem of mutual exclusion in a unidirectional ring under the model of
processors and registers. For the problem of mutual exclusion, legitimate behavior is some
computation in which every processor obtains access to a "token" (or critical section) infinitely
many times, yet no two processors have simultaneous token access at any time. We call this
high-level token behavior the mutex property and encode the safety portion of mutex with a
predicate P . A stabilizing mutex protocol is stabilizing with respect to predicate P , which
specifies that at most one processor accesses the critical section (at any legitimate state).
Two perspectives for evaluating the efficiency of a stabilizing or superstabilizing protocol are the
efficiency in the absence of faults (normal behavior) and the protocol's efficiency in recovering
from a fault. We use rounds to measure the worst-case time in recovery from a fault, either for
stabilization or superstabilization. Call a computation segment a complete token circulation if
every processor has a token at some state in the segment. A minimal token circulation is a
complete token circulation such that no proper subsegment of the computation segment is a
complete token circulation. In the sequel, we use token circulation to denote a minimal token
circulation. To characterize the efficiency of a protocol's normal behavior, we investigate the
best and worst case for token circulation times. The best case is described in terms of the
following definition, which is useful for impossibility proofs. A mutual exclusion protocol for a
ring of processors is called k-latent if k is the minimum value so that for every legitimate state
oe there exists a token circulation that begins at oe and contains k linear rounds. A protocol is
optimal with respect to latency if it is 1-latent, meaning that a token can circulate the ring in
one round from any legitimate state.
The most efficient token-passing protocol is one in which the token is passed from i to (i
with two register operations: i writes to R i(i+1) and (i+1) reads R i(i+1) to complete the transfer
of a token. A somewhat less efficient technique would be the passing of a token where i writes
two registers, R i(i+1) and S i(i+1) , followed by (i reading both of these registers. It turns
out that either of these techniques can be used to construct a 1-latent protocol: the definition
of 1-latency does not discriminate with respect to the number of registers used in transferring
a token. A more complicated technique for transferring a token is the following "handshake"
mechanism: first i writes to R i(i+1) ; then (i
reads Q i(i+1) and again writes to R i(i+1) ; finally, (i again to complete the
token transfer. Such a handshake mechanism is a two-phase interaction between i and (i 1).
A protocol using this handshake mechanism for token circulation is not 1-latent - it turns
out to be n-latent in the protocol of Section 6. Intuitively, a 1-latent protocol is most efficient
because the interaction between processors for token passing is minimal. In an implementation
of registers based on lower-level messages, the delay incurred by p i writing to two registers
R i(i+1) and S i(i+1) could be roughly the same as writing to one register provided writes occur
in parallel. But the handshake mechanism is a sequential interaction between i and (i
and this delay cannot be hidden.
3.1 The Basic Ring Protocol
Dijkstra's K-state stabilizing protocol for a unidirectional ring can be adapted to the processor
and register model, but a number of definitions require adjustment. Roughly speaking, the
state-reading model used in [D74] corresponds, in the unidirectional case, to an n-register ring
of processors (one key difference is that a processor cannot read the register it writes, whereas
in the state-reading model, a process has read access to all the variables it writes). Instead
of associating mutual exclusion with a "privilege" or enabledness of an action, which makes
R i(i+1)
perform critical section
S5 if (i 6=
S6 perform critical section
S8

Figure

1: mutex protocol for processor i.
sense given an execution demon, a different representation is necessary for the processor model.
Similarly, the characterization of legitimacy has to be modified to suit the new representation
of mutual exclusion.
An adaptation of the K-state stabilizing protocol is presented in Figure 1. The unidirectional
ring is implicit in the use of 1W1R registers. Each register is of the
n. The diagram in Figure 1 illustrates that each processor i reads from R (i\Gamma1)i and
writes to R i(i+1) in this protocol. Each processor i has two internal variables: N is an image
of the register it reads and C is an image of the register it writes. Processor zero plays the
role of the exceptional machine. The notation ++ C denotes (C in statement S4
and in the sequel. We require that K be larger than the total number of variables and registers
that contain token values: for the protocol of Figure 1 this requirement 1 is K ? 3n. For this
protocol (and subsequent protocols in this paper), if at some state oe the program counter of
a processor p is located at a critical section statement (e.g., S3 or S6 above) or, by steps of p
alone starting from state oe, processor p can execute the critical section, then we say that p is
a token holder at state oe.
At a high level, legitimate behavior of this protocol is simple to describe using the mutex
property. The predicate P is formally specified by:
We choose the constraint K ? 3n for convenience in proofs; the protocol is correct with smaller values of
K. The larger value of K simplifies proofs, as shown in [V94].
The notation S3 i denotes that processor i's program counter is set to S3, i.e., processor i is
executing its critical section. Here, and elsewhere in the paper, the notation
is used for quantifications in predicates, where op is a quantifier and a list of dummy
indices, range delimits the range of the dummies (range may be omitted if the dummy range
is understood), and term is an expression or nested quantification.
This definition of P specifies that no two processors may simultaneously execute the critical
section. In the sequel, each protocol in this paper is stabilizing with respect to some version
of P , and we henceforth leave P to be implicitly understood (its definition differs for other
protocols only in the specific statement numbers for critical sections).
Defining a legitimacy predicate L a more detailed affair that the simple specification of P . For
example, in a legitimate state one would expect the following to hold:
(1)
In words, (1) says that the C-value for a processor is equal to the value in its write-register
whenever the program counter is set to S1, as one would expect after the execution of S8
and S9. A complete characterization of a legitimate state in terms of internal variable values,
register values, and program counters turns out to be a lengthy expression. To spare the reader
details, we leave L implicit and concentrate on the following crucial component of L for the
ring protocol.
In the state-reading model, which has neither program counters nor registers, LC is the characterization
of a legitimate state. The LC predicate states that every process either has an "old"
value x in its C variable or a "new" value that is ++ x; any if any new values are present, they
are in a contiguous segment starting from processor zero. Steps of the protocol unidirectionally
copy a new value to replace an old value adjacent to it; the result of this copy operation is a
state satisfying LC . After all old values are replaced by the new value (or if initially all values
are the same), then LC is satisfied by the choice in the existential quantification of LC 's
definition.
Lemma 1 The mutex protocol of Figure 1 is stabilizing with O(n) stabilization time.
Proof: The proof consists of showing that convergence and closure to states satisfying LC , and
then verifying that LC ) P . Consider an arbitrary computation starting from an arbitrary
initial state and number the rounds of the computation starting with round zero. After the
completion of round zero, the computation reaches a state where (1) holds, because each
processor executes S8 and S9 at least once during round zero. More generally, after processor
i has completed any cycle, R i(i+1) is equal to C i . This observation permits us to reason using
C variables for rounds one and higher.
We do not prove in detail closure of LC and convergence to LC , since this would repeat known
arguments. To see the O(n) bound, we introduce the predicate
Note that G (n\Gamma1) implies LC ; if the protocol has completed round zero - so that all processors
have synchronized images of registers with program counters - and G (n\Gamma1) holds, then the
protocol has stabilized. Henceforth in the proof we consider only rounds one and higher.
It is simple to show by induction that G k holds after round t +k, for
processor zero does not execute S4 in rounds t through t +k. Therefore if S4 does not execute
for holds. Consequently, in the case where C 0 is unique (not equal to
any other processor's C variable), G (n\Gamma1) holds after (n \Gamma 1) additional rounds.
Within how many rounds is the C 0 value unique? Since there are n processes and S4 increments
modulo K, by the pigeon-hole principle C 0 becomes unique after at most 3n executions of S4
(only S4 can introduce new C values into the system, and K ? 3n implies there is some token
value not in any register or variable). Combining this with observations about G k , we see that
any computation contains a state satisfying LC by round 4n.
Based on the invariance of LC and some straightforward details of L concerning program
counters and internal variables, it follows that P holds at each state following convergence
(the structure of LC is also useful for proving that each processor performs a critical section
infinitely often).
Lemma 2 The mutual exclusion protocol of Figure 1 is a 1-latent protocol, and circulates
the token in at most n rounds.
Proof: Consider a legitimate state oe where i is either a token holder or was the last processor
to hold a token and has not completed its cycle (every legitimate state has at least one such
processor i). Construct a linear round by first scheduling steps of processor i until it completes
its current cycle, then schedule processor (i 1)'s cycle, and so on, completing the round with
the inclusion again of a cycle of processor i if necessary. In this schedule, each processor is
token holder during the linear round. The proof that n rounds suffice for token circulation
follows from arguments similar to the (inductive) reasoning used in Lemma 1.
3.2 Processor-Local Faults
We now consider the event of a processor-local fault at a legitimate state. There are essentially
two worst-case aspects to such a fault: (a) the fault can set the program counter for processor
i to S6 (leaving all the internal variables unchanged); or (b) the fault can set the program
counter to S8 for i and the value of C to an arbitrary value; it is then possible that the first
step of the computation following the fault is the write operation of processor i, which writes
R i(i+1) with the value injected by i's processor-local fault. Processor-local faults that combine
aspects of (a) and (b) are also possible.
A fault of type (b) is, in a sense, more severe than (a). After a fault of type (a), in one
additional step by processor i, the protocol is in a legitimate state; moreover, in all the states
that violate mutual exclusion following the fault, processor i is the only processor invalidly in
its critical section. After a fault of type (b), it is possible that the subsequent computation
contains a state where three processors are simultaneously at a critical section. We sketch such
a scenario with an example of a ten processor ring, showing the values of the C variables for
a legitimate state:
The underscored value indicates a processor that is a token holder. From this state, consider
a processor-local fault that sets a C variable to 5 and suppose that the first subsequent step
writes the C variable to the output register, which its neighbor then reads to obtain the state
Here two processors are token holders. In subsequent steps, the value 5 is propagated so that
the state
results. The processor inflicted by the processor-local fault then reads from its neighbor and
rewrites its register, which can lead to the state
where three processors are token holders.
What modifications to the protocol can address the concerns of faults of type (a) and (b)? So
long as activation of a critical section is dependent on internal variables and a program counter,
a fault of type (a) is impossible to prevent. The strongest passage predicate one can construct
must allow for the possibility that two processors are token holders, however it should be that
one of these two processors is the processor inflicted with the processor-local fault and that the
protocol satisfies mutual exclusion within a cycle of the inflicted processor. It will be possible
to construct a protocol satisfying the mutex passage predicate provided that effects of a type
(b) fault can be managed.
For the remainder of the paper, let Q(ffi) be the mutex passage predicate, defined parametrically
with respect to a 1-faulty global state ffi. For the definition, let CS i be 1 if i's program counter
is at a critical section, otherwise let CS i be 0. Let pr:ffi be the index of the processor inflicted
by the fault for state ffi.
Note that a stronger passage predicate than Q(ffi) is desirable: we would prefer that processor
pr:ffi execute a critical section only one time during the recovery period, however Q(ffi) will be
satisfied by a computation segment in which pr:ffi executes its critical section numerous times
while the "real token" continues to circulate. In principle, such a stronger passage predicate
could be formally specified using auxiliary variables that record fault and computation history,
but we prefer the simpler specification of Q(ffi) for this paper (the protocols in subsequent
sections do, in fact, satisfy a stronger passage predicate).
As an attempt to address a type (b) fault, consider the following replacement of statement S6
of the protocol:
S6a if
S6b perform critical section
This strengthened precondition for executing the critical section eliminates the scenario for
multiple token holders sketched above, however the following situation is still possible after a
processor-local fault and subsequent steps:
Although it can be shown that the improved protocol no longer has the possibility of three
token holders existing after a processor-local fault from a legitimate state, the mutex passage
predicate is not satisfied in every case: the effect of a processor-local fault is not contained to
a single processor. The following theorem shows that more resources are necessary in order to
address this concern.
Theorem 1 No 1-latent protocol for mutual exclusion using fewer than 2n 1W1R registers
is superstabilizing with respect to the mutex passage predicate.
Proof: by contradiction, for n ? 3. Suppose a 1-latent protocol exists with at most 2n \Gamma 1
registers that is superstabilizing with respect to the mutex passage predicate. In order to
stabilize, each processor has read access to at least one register and write access to at least
one register (otherwise there could be no token circulation). Because the registers are of type
1W1R, some processor p has read access to only one register R p .
Consider a legitimate state oe such that some processor q is at the first statement of its cycle and
becomes a token holder in that cycle; we also suppose q 6= p, and q does not have write-access
to R p . Such a choice of oe and q is possible because n ? 3 and the protocol is a stabilizing
mutual exclusion protocol.
By the assumption of 1-latency, there exists a linear round starting at oe so that every processor
is a token holder. The first cycle of such a linear round consists of steps by processor q, so that
it ceases to be a token holder. The second cycle of the round consists of steps by either
or (q + 1) that include token-holding at that processor (this can be proved by contradiction,
for if the second cycle is at some r 62 then an illegitimate computation could
be constructed where r has the initial cycle and then both r and q are token holders at some
state). This argument about the structure of the linear round can be continued to establish a
path of token holders from q to p.
Given the linear-round construction above, it is clear that there exists a state fl such that oe
and fl are identical with respect to p's state and R p contains a value t so that a computation
beginning from fl, and containing only steps of p, results in p being the token holder. It
is therefore possible for the following processor-local fault to occur at state oe: the program
counter for the writer of R p is set to a write( R p := t ) operation; the first step from the 1-faulty
state then writes to R p , and a subsequent computation segment consisting solely of steps of p
results in p being a token holder. The existence of such a processor-local fault and subsequent
computation violates the mutex passage predicate.
Unidirectional Superstabilizing Protocols
The conditions of impossibility for Theorem 1 suggest two ways one might hope to construct a
superstabilizing protocol: devise a protocol that is k-latent for some k ? 1, or design a protocol
using at least 2n registers. These possibilities are the subject of the following two subsections.
4.1 n-Latent Protocol
One way a superstabilizing mutual exclusion can be possible is by increasing the latency of
token rotation. The protocol presented here uses n 1W1R registers, but the size of the register
is larger than used in the protocol of Figure 1. Each register is mapped into
where each field has K states. Each of these fields represents a "token" of Dijkstra's protocol,
and stabilizes in the same sense as the protocol of Figure 1. One of these tokens is
called the major token, which controls access to the critical section; the remaining n tokens
are called minor tokens, and each processor in the ring plays the exceptional role (in the way
that processor zero is exceptional for Dijkstra's protocol) for one of the minor tokens. The
main idea of this subsection's protocol is that the major token advances one position in the
ring only after a minor token circulates once around the ring. After one linear round, the major
token advances one processor; after n linear rounds major token circulation is completed.
Let register R ij be subdivided into n+ 1 fields, denoted R ij [k] for Each processor i
has three internal variables: w is a boolean and the two variables C and N are register image
variables. Fields (R ij [n]; C[n]; N[n]) represent the major token, and fields (R ij [k]; C[k]; N[k])
represent the minor token of exceptional processor k, for presents the
protocol for processor i, i 6= 0. The protocol for processor zero is not presented, but differs
only from Figure 2 in statements S4, S12 and S14 (the modification follows from the protocol
of

Figure

1).
A legitimate state for the n-latent protocol satisfies three key properties. (1) Major and minor
token values are legitimate by natural extension of the LC definition, introduced for the proof
of Lemma 1, to the appropriate fields. (2) Exactly one processor p either holds a token, is
releasing a token, is waiting for its minor token to circulate (with w p set to false) before it
holds a token. (3) If a processor q is not waiting for its minor token to circulate, then all fields
(R ij [q]; C[q]; N[q]) for that minor token have the same value.
Lemma 3 The protocol of Figure 2 is stabilizing, has O(n 2 ) stabilization time, is n-latent,
and any token circulation has at most n 2 rounds.
S5 if w then
perform critical section

Figure

2: n-latent mutex protocol, i 6= 0.
(See Appendix for proof.)
Theorem 2 The protocol of Figure 2 is superstabilizing with respect to the mutex passage
predicate with O(n) superstabilization time.
(See Appendix for proof.)
Although superstabilization guarantees that the passage predicate holds during convergence
following a 1-faulty state, a processor-local fault can disrupt the normal order in which processors
become major token holders. For instance, it is easy to construct examples where a
number of processors are "skipped" in the order of token-holding until all minor tokens stabilize
following a processor-local fault. So, although the protocol is superstabilizing, it may
not be entirely fault-masking for a processor p at some distance from the processor-local fault.
Suppose the fault is not located at processor p; after the fault and before convergence to a
legitimate state is complete, processor p could lose a turn at executing the critical section.
Whether the protocol is fault-masking or not for such processors depends on a user's ability
to observe that a turn at the critical section is lost in a computation disrupted by a fault.
specification of the observation power of a user is needed to formalize masking fault-tolerance.)
In closely related work [UKMF97], ideas from the superstabilizing protocol of Figure 2 have
been improved and presented for the state-reading model of [D74]. In the state-reading model,
registers and program counters are replaced by variables, and a process-local fault can corrupt
all the variables of a process. The superstabilizing protocol of [UKMF97] is (1 n=2)-latent
by having the major token advance through two processes in each minor token circulation (n
must be even for this protocol); the space requirement is also reduced by combining all minor
tokens into a single minor token (this reduces the token space from O(n lg n) to O(lg n)). It is
also shown in [UKMF97] that no bn=2c-latent superstabilizing mutex protocol is possible for
a unidirectional ring in the state-reading model.
4.2 1-Latent Protocol
The previous subsection's protocol exploits increased latency to achieve superstabilization; the
other approach suggested by the structure of Theorem 1 is to use 2n registers. The protocol
presented in this subsection adds a "duplicate" register Q ij to the protocol of Figure 1 so that
execution of the critical section is dependent on values from two registers.
The main idea for each processor i, i 6= 0, is that i will not propagate the values it reads from
two registers unless these values are equal; and the protocol specifies that processor i does not
write the same value to two registers without reading a register between the two writes. One
way to describe this protocol is to say that processor i uses a "waiting" strategy to deal with
1-faulty states, since i waits for both its input registers to have equal token values. Figure 3
presents the protocol. For this protocol, let K be any value satisfying K ? 5n, since there are
five token entities per processor: C, M, and N variables, plus two output registers.
The idea of waiting cannot be employed at all processors because certain initial global states
would lead to deadlock. Processor zero therefore uses a different strategy to deal with 1-faulty
states. The code for processor zero uses a function trval returning a pair of natural numbers,
defined as follows:
In a pair (t; C) assigned by trval(y; C; N;M), the value of C is a token value for processor
zero, and the value t is a counter value, which will be zero in a legitimate state, and at most
7n for an illegitimate state (the value 7n was chosen to simplify the proof of convergence).
The first 'if'-case of trval's definition addresses the normal situation of the token at processor
zero: it increments the token only in the case where both registers written by processor (n \Gamma 1)
are valid. We call the (7n; ++ M) cases corrective values for C 0 , which are provided in case
a processor-local fault corrupts C 0 . Unfortunately, there are cases of initial states where
this corrective calculation of C 0 , if repeatedly employed, prevent stabilization of the token
mechanism. Therefore the counter t has been added to the protocol so that the corrective
measure will be applied only a bounded number of times in any computation. Since this counter
is also subject to corruption by a fault, its value is circulated in the ring by an additional register
field.
At all legitimate states, t states also satisfy L R ,
which we define to be the following: for each processor p, values of the C variable and registers
conform to some entry in the following table.
R fffi fffi ffff ffff fffi fifi fifi fifi fiff fiff ffff fifi
The convention for this table is fi. The row for R registers shows the token field only,
and the two values represent R (p\Gamma1)p and R p(p+1) respectively. Each table entry thus represents
value relationships for a processor: for instance, the first entry shows a processor p 6= 0 with
both input registers equal to some value ff, C both p's output registers are equal to
fi. The final column under the p 6= 0 heading is a permissible configuration only for the case
processor zero can propagate a token value in either register order, whereas
the order is fixed for other processors).
By looking at the definition of L R , the reader may appreciate that verification of superstabiliza-
tion involves numerous subcases, since each entry in the table is subject to fault considerations.
The proofs are somewhat tedious and postponed to the paper's Appendix.
Lemma 4 The protocol of Figure 3 is stabilizing, has O(n 2 ) stabilization time, is 1-latent,
and every token circulation has at most n rounds.
(See Appendix for proof.)
to be the conjunction LC - L R , where LC is the predicate over token values specified
for the proof of Lemma 1.
Lemma 5 In any computation starting from a 1-faulty state, the protocol of Figure 3 reaches
a state satisfying L T in O(1) rounds, with the mutex passage predicate holding at every state.
(See Appendix for proof.)
Theorem 3 The protocol of Figure 3 is superstabilizing with respect to the mutex passage
predicate and has O(n 2 ) superstabilization time.
R i(i+1)
-:
S5 if
S6 perform critical section
S8
protocol for i 6= 0
T4 if
T5 perform critical section
T11 perform critical section
T13 goto
protocol for

Figure

3: unidirectional 2n-register protocol.
Proof: By Lemma 5 any computation starting from a 1-faulty state establishes the invariant
holds and the state is legitimate
(to see that this bound is tight, consider a fault at processor zero that sets t 0 := (n
The superstabilizing protocol given in this subsection improves over the n-latent protocol in two
ways. First, latency is improved by adding registers. Second, although the superstabilization
time is larger, the recovery from a processor-local fault can be said to take O(1) time - since
L T holds within O(1) rounds following a fault. However, even though L T holds the state is
not legitimate: the system is not ready to mask another processor-local fault until the state is
legitimate. Considering the convergence segment following a fault, we see that the initial part of
this segment recovers token variables from the fault and the latter part of this segment is a kind
of "garbage collection" adding sufficient robustness to the state so that another processor-local
fault can be tolerated.
5 Optimum Latency and Superstabilization
This section describes certain limits of superstabilizing mutex protocols that are 1-latent. The
results show that 1-latent protocols either require techniques beyond those used in previous
sections or require bidirectional communication.
We begin with an observation regarding the passing of a token in a superstabilizing protocol.
Lemma 6 For any 1-latent protocol there exists a computation in which the token circulates
unidirectionally.
Proof: by contradiction. Suppose a 1-latent protocol has no computation in which the token
circulates unidirectionally. Then in every suffix of every computation, the token is passed from
some processor i to (i \Sigma 1) and then again to i. Such an order of token passing contradicts the
definition of a linear round.
Lemma 6 covers the case of nondeterministic token circulation; for example, the choice of
passing a token from processor i to (i could be nondeterministic. But for the
protocol to be 1-latent, it must be possible from any legitimate state for a token circulation to
complete in one linear round, which implies unidirectional token movement. For the remainder
of this section, we consider only 1-latent protocols and restrict attention to computations in
which token circulation is unidirectional.
Define the number of token passing registers of a protocol to be the minimum, for i in the
range the number of registers that i writes and (i reads in the passing of a
token from processor i to processor (i 1). The protocols of Section 3.1 and Section 4.1 use
one token passing register and the number of token passing registers for the protocol of Section
4.2 is two.
superstabilizing mutual exclusion protocol uses fewer than two token
passing registers.
allows us to concentrate on computations where token passing is unidirec-
tional. The lemma can then be proved using an argument similar to that presented for Theorem
1: a processor-local fault can cause a write to a token passing register that fools another processor
into executing its critical section so that the mutex passage predicate is falsified.
Lemma 7 implies that the 1-latent protocol of Section 4.2 is optimal in the number of registers
it uses, and that a 1-latent bidirectional protocol circulating a token unidirectionally uses at
least three registers, since at least two registers are required for token passing.
The remainder of this section presents definitions and results for a particular type of unidirectional
protocol. Given a 1-latent unidirectional mutual exclusion protocol, there are a certain
number of registers, say k i , written by processor i and read by processor (i 1). Some predicate
exists that describes the legitimacy relation over values for a local state of processor
i, the output registers of processor i, and the local state of processor (i 1). We call a global
state detectably corrupt at can be inferred from the local state of processor
and the contents of the output registers of processor i. Suppose state oe is detectably
corrupt at 1). Two possible properties of oe are: (i ) there exists some legitimate state
in which the output registers of processor i are equal to their values at state oe, and (ii ) there
exists some legitimate state in which the local state of processor (i equals that at state oe.
If both (i ) and (ii ) hold at oe, then we say oe is a spliced corrupt state, since values of i's output
registers are legitimate and the state of (i + 1) is legitimate, but these two are legitimate for
different states (so oe is the result of "splicing together" two legitimate states).
A spliced corrupt state poses a question for the design of a superstabilizing mutual exclusion
protocol. If a spliced corrupt state oe is detectably corrupt at (i; i +1), should processor (i +1)
alter its state so that P i holds? Two possible strategies for processor (i + 1) are correcting
and waiting. The correcting strategy consists of processor (i reading its input registers to
detect :P i , followed by processor (i its local state so that :P i no longer holds.
The waiting strategy consists of processor (i +1) entering some protocol phase in which (i +1)
continues to execute cycles, with :P i holding, until i's output registers change values, after
which processor (i does not detect :P i or processor (i its state so
that :P i is not detectable. In the waiting strategy, processor (i waits for the situation to
be corrected by i or waits for a signal from i that (i should correct its state to fix the
problem.
A stabilizing mutual exclusion protocol is regular if, for each processor (j +1), whenever :P j is
detectable by processor (j uses one strategy, correcting or waiting,
in response to detecting :P j . In other words, a protocol is not regular if a processor (j
sometimes uses the correcting strategy and sometimes uses a waiting strategy, depending on
values of the local state of (j its input registers. Note that Dijkstra's protocol is
regular: processor zero employs a waiting strategy, effectively ignoring the values of its input
registers unless they appear to be legitimate; all other processors use the correcting strategy.
Lemma 8 Any regular 1-latent unidirectional stabilizing mutual exclusion protocol specifies
at least one processor to use a waiting strategy.
Proof: by contradiction. Consider a regular protocol in which all processors use correcting
strategies. We construct an illegitimate state by splicing together some number of legitimate
states. For instance, take one segment A ff of t processors in a ring of size n from legitimate
state ff, where the token of ff is located within A ff , and another segment A fi of (n \Gamma t) processors
from legitimate state fi, where the token of fi is located within A fi and the two segments A ff and
A fi are disjoint. We construct a new state fl by splicing the two segments together. A possible
computation starting from fl is the following scenario. In each round, both tokens advance
one processor in the ring (possible by 1-latency), and two processors execute the correction
strategy. Thus in each round, two legitimate segments of size t and (n \Gamma t) persist while
the protocol fails to converge. The assumption that each processor uses a correcting strategy
therefore contradicts stabilization.
Lemma 9 If any processor uses a waiting strategy in a regular 1-latent unidirectional super-
stabilizing mutual exclusion protocol, then the protocol cannot have O(1) superstabilization
time.
Proof: by contradiction. We construct a 1-faulty state oe 0 from a legitimate state oe by selecting
some processor (j + 1) that employs the waiting strategy and corrupting the state of (j
that oe 0 is a spliced corrupt state. The output registers of (j have the same values in both
oe and oe 0 . Since (j the waiting strategy, the computation starting from oe 0 remains
illegitimate until processor j writes some register to a different value than is present in state
oe. Let us consider a computation in which j completes many cycles before (j its
input registers. Since all variables and registers are finite, the values of j's output registers are
periodic over the computation, that is, there exist values of j's output registers that repeat.
Moreover, these values are all possible in legitimate states of the protocol for !(1) rounds (i.e.,
more than a constant number of rounds), since no processor other than (j initially detects
illegitimacy, and no signal written by (j + 1) can circulate the ring to processor j within O(1)
rounds. Therefore we can construct a computation in which processor (j does not observe
any change of its input registers for !(1) rounds - because each time (j its input
registers, they have the same values by the periodicity argument. Thus the protocol does not
converge from a 1-faulty state to a legitimate state within O(1) rounds, which contradicts the
claim of O(1) superstabilization time.
Theorem 4 No regular 1-latent unidirectional mutual exclusion protocol is superstabilizing
with O(1) superstabilization time.
Proof: The result follows from the two previous lemmas.
6 A Bidirectional Protocol
The 2n-register protocol given in Section 4.2 has O(n 2 ) superstabilization time, and the n-
register protocol of Section 4.1 has O(n) superstabilization time. This section presents a
protocol with O(1) superstabilization time, at the expense of bidirectional communication -
the bidirectional approach is motivated by Theorem 4. The basic idea of this protocol is a
simple adaptation of the n-register superstabilizing protocol: each processor i controls a minor
token, however this minor token circulates only between processors i and (i \Gamma 1). The ring is
therefore bidirectional, and two 1W1R registers are needed for each processor. The diagram
shown in Figure 4 illustrates how processors i and (i communicate for this protocol.
Each register has two fields, one for the major token value and one for a minor token value.
Each processor i uses its C variable for the major token and maintains two local variables for
minor token circulation: t represents i's minor token, and v contains an image of (i
minor token value. Additional local variables A, T , N, and D are register field images.
The (legitimate) progression of minor token activity is: processor (i assigns t := ++ t, and
then executes a subsequently executes read( (D;
assigns v := A; processor i then executes
which processor (i reads the v-field of the R register into variable T; finally, processor
t, which implies completion of its minor token circulation.
In addition to variables for token manipulation, each processor i records two "recently read"
values (major and minor token) from processor (i \Gamma 1). This recording is implemented in
history variables (arrays W and V), which are two-element arrays, and a local index variable
w that toggles between zero and one whenever processor i detects a new value pair from
processor (i \Gamma 1). More precisely, if processor i observes that the minor token differs from
V[w] or observes that the major token differs from W[w], then i toggles w and records the
major and minor token values just read. The history variables strengthen the condition for
execution of the critical section: the major token must have the same value for two consecutive
recordings before the critical section can be executed.
Each processor has a correction assignment (S7 or T7). The correction assignment for i 6= 0
is identical, with respect to the major token, to the normally executed S12. The correction
assignment T7 of Figure 4 is not the standard major token assignment of T12; the possibility of
repeated execution of T7 during convergence complicates the proof of stabilization. We assume
since there are seven major token variables and fields per processor.
Legitimacy for the protocol is specified with three components, LC for legitimacy of the major
token, L t for legitimacy of the minor tokens, and Lw for legitimacy of the history variables.
The Lw predicate, defined as follows, asserts allowed values for W i and V i in two situations at
the end of a cycle for processor i (statement S19):
(The major token is not being passed from (i \Gamma 1) to i.)
ffl If ++ C
major token is being passed
from (i \Gamma 1) to i.)
The construction of Lw underlies the design of S15-S16 (T15-T16), which correct history
variables after a processor fault.
The protocol of Figure 4 is stabilizing with O(n 3 ) stabilization time; the protocol
is n-latent and any token circulation is at most 3n rounds.
R i(i+1)
-:
Xy
S5 W[w];V[w] := N; T
S7 then C := N
perform critical section
else
protocol for i 6= 0
T3 if N 6= W[w] - T 6= V[w] then
T7 then C := ++ N
T11 perform critical section
T13 else
T17
protocol for

Figure

4: bidirectional 2n-register protocol.
(See Appendix for proof.)
Theorem 5 The protocol of Figure 4 is superstabilizing with O(1) stabilization time.
(See Appendix for proof.)
Protocols presented in this paper demonstrate that stabilization and (limited) masking tolerance
of transient faults can be combined. Our investigation indicates that the goals of masking
tolerance of a single fault, rapid token circulation, and stabilization may collide or require
additional resources. Each of the protocols given here uses the minimum number of registers
possible in some optimal sense: the n-register protocol is optimal for a superstabilizing protocol,
the 2n-register protocol is optimal for a 1-latent superstabilizing protocol, and the bidirectional
protocol is optimal for O(1) superstabilization time.
An open question suggested by the three presented protocols is the possibility of a protocol
that is superstabilizing, 1-latent, and has O(1) superstabilization time (possibly with optimal
stabilization time as well). The limits given by the results of Section 5 suggest that the form
of such a protocol might be bidirectional, with three registers per processor.
A limitation of this investigation is that we consider only processor-local faults in the definition
of a 1-faulty state. This precludes consideration of a transient fault that corrupts only a
register. Although a processor-local fault can lead to corruption of a register, we have additional
information from such an event: if a register is corrupted because a transient fault set
the program counter to a write operation, then the program counter will be set to the statement
following the write after the fault-induced event. We use this fact in our constructions
by arranging the protocols to read and verify variables following write operations. It is likely
that techniques used in this paper can be extended to cover the case of register faults as well,
perhaps at the expense of additional resources.
Some techniques used for superstabilization in this paper are basic methods of fault tolerance:
replication of data entities (registers) and replication in time (implicit in the use of minor tokens
and the bidirectional acknowledgment). A different approach to the problem of transient faults
is to use techniques of coding theory or encryption to reduce the probability that a transient
fault will violate the passage predicate. The paper [Y96] suggests that public-key encryption
be used to encode the token, which makes it unlikely that a transient fault could falsify the
mutex predicate (the fooling argument used for Theorem 1 is "practically" refuted).
Although the present study is limited to the problem of mutual exclusion in the processor-
register ring model with processor-local faults, results from the paper [GGHP96] show similar
limitations for the state-reading model and general transformational programs. The paper
[GGHP96] uses a model in which a process can read all the states of its neighbors in one atomic
step, and only non-reactive programs are considered, which excludes mutual exclusion from
consideration. A result of [GGHP96] is that goals of optimum stabilization time and O(1) fault
correction time from a 1-faulty state can conflict (with no consideration of a passage predicate).
An approach for rapid stabilization following transient faults, suited to a network model, is
given in [KPS97] for non-reactive protocols, but there is no consideration of safety during
convergence. The papers [GS95, CW97] consider limited forms of change from a legitimate
state: a stabilizing algorithm for maximum-flow trees is considered, where the capacities on
links can asynchronously change, and a form of safe convergence to a new legitimate state is
guaranteed.
The investigation of this paper is limited to mutual exclusion in a ring with processor-local
faults. By contrast, other research [GP93, DH95, AG93] combining stabilization and other
forms of fault-tolerance considers the general methodological problem of systematic construc-
tion, that is, identifying conditions under which various techniques can be used in modular
form to synthesize programs with various fault tolerances (nonmasking tolerance to transient
faults plus masking tolerance to failstop processes, and so forth). The general method [GP93]
is not applicable to the problem we consider, namely the nonmasking tolerance of worst case
transient faults and maintenance of a specified passage predicate for single processor-local
faults. The general superstabilizing construction of [DH95] relies on interrupts from faults,
so it does not apply to processor-local faults. The method suggested by [AG93], based on
programming with constraints, does not specify details sufficient to address superstabilization.
The design of superstabilizing protocols is non-trivial in the same sense that stabilizing protocols
are: any "stabilizing supervisor" added to a protocol in order to make it stabilizing must
itself overcome transient faults that strike the supervisor; similarly, any mechanism added to
maintain a passage predicate following a single, local fault must itself guarantee safe behavior
during convergence after such a fault, as well as convergence from a general fault. The apparently
simple solution of adding redundant components and then using a voting module to mask
single faults will not work if the voting module does not mask single faults to its own variables
and program counters. An approach proposed in [AK97] is to develop programs by a layered
methodology, where new statements are successively added to a program, using superposition
operators, to deal with different types of faults. This approach is general in the sense that every
fault-tolerant program (in the guarded command model of computation) can be shown to be
a (layered) composite structure, with its elements corresponding to fault detection and correction
of various fault types; the problem of how to devise fault-tolerant programs remains,
however, a challenging task. The experience of this paper suggests that refinement may be
an appropriate methodology for the development of superstabilizing programs - each of the
protocols presented here can be seen as a refinement of Dijkstra's K-state protocol.



--R

Designing masking fault-tolerance via nonmasking fault- tolerance
A highly safe self-stabilizing mutual exclusion algorithm

Hive: Fault Containment for Shared-Memory Multiprocessors



Closure and Convergence: A Foundation of Fault-Tolerant Computing
Gopal AS

SuperStabilizing Protocols for Dynamic Distributed Systems.
Constructing 1-Writer Multireader Multivalued Atomic Variables from Regular Variables

A Latency Optimal Supersta- bilizing Mutual Exclusion Protocol
Propagated Timestamps: A Scheme for the Stabilization of Maximum Flow Routing protocols.
Maximum Flow Routing.

--TR
Fault-Tolerant Computing
Unifying self-stabilization and fault-tolerance
Closure and Convergence
Self-stabilization by counter flushing
Constructing 1-writer multireader multivalued atomic variables from regular variables
Hive
A highly safe self-stabilizing mutual exclusion algorithm
Fault-containing self-stabilizing algorithms
Time-adaptive self stabilization
Designing Masking Fault-Tolerance via Nonmasking Fault-Tolerance
Self-stabilizing systems in spite of distributed control
Self-Stabilizing Mutual Exclusion in the Presence of Faulty Nodes

--CTR
Yoshiaki Katayama , Eiichiro Ueda , Hideo Fujiwara , Toshimitsu Masuzawa, A latency optimal superstabilizing mutual exclusion protocol in unidirectional rings, Journal of Parallel and Distributed Computing, v.62 n.5, p.865-884, May 2002
Yehuda Afek , Shlomi Dolev, Local stabilizer, Journal of Parallel and Distributed Computing, v.62 n.5, p.745-765, May 2002
mutual exclusion;fault-containment;self-stabilization