Distributed Reset.
A reset subsystem is designed that can be embedded in an arbitrary distributed system in order to allow the system processes to reset the system when necessary. Our design is layered, and comprises three main components: a leader election, a spanning tree construction, and a diffusing computation. Each of these components is self-stabilizing in the following sense: if the coordination between the up-processes in the system is ever lost (due to failures or repairs of processes and channels), then each component eventually reaches a state where coordination is regained. This capability makes our reset subsystem very robust: it can tolerate fail-stop failures and repairs of processes and channels, even when a reset is in progress.
Introduction
We describe in this paper how to "augment" an arbitrary distributed system so that each of
its processes can reset the system to a predefined global state, when deemed necessary. The
augmentation does not introduce new processes or new communication channels to the system.
It merely introduces additional modules to the existing processes. The added modules, communicating
with one another over existing channels, comprise what we call the reset subsystem.
Ideally, resetting a distributed system to a given global state implies resuming the execution
of the system starting from the given state. With this characterization, however, each reset
of a distributed system can be achieved only by a "global freeze" of the system. This seems
rather limiting and, in many applications, more strict than needed. Therefore, we adopt the
more lax, characterization: resetting a distributed system to a given global state
implies resuming the execution of the system from a global state that is reachable, by some
system computation, from the given global state.
There are many occasions in which it is desirable for some processes in a distributed system to
initiate resets; for example,
ffl Reconfiguration: When the system is reconfigured, for instance, by adding processes
or channels to it, some process in the system can be signaled to initiate a reset of the
system to an appropriate "initial state".
ffl Mode Change : The system can be designed to execute in different modes or phases.
If this is the case, then changing the current mode of execution can be achieved by
resetting the system to an appropriate global state of the next mode.
ffl Coordination Loss: When a process observes unexpected behavior from other pro-
cesses, it recognizes that the coordination between the processes in the system has
been lost. In such a situation, coordination can be regained by a reset.
ffl Periodic Maintenance: The system can be designed such that a designated process
periodically initiates a reset as a precaution, in case the current global state of the
system has deviated from the global system invariant.
As processes and channels can fail while a reset is in progress, we are led to designing a reset
subsystem that is fault-tolerant. In particular, our reset subsystem can tolerate the loss of
coordination between different processes in the system (which may be caused by transient failures
or memory loss) and, also, can tolerate the fail-stop failures and subsequent repairs of processes
and channels.
The ability to regain coordination when lost is achieved by making the reset subsystem self-stabilizing
in the following sense. If the reset subsystem is at a global state in which coordination
between processes is lost, then the reset subsystem is guaranteed to reach, within a finite number
of steps, a global state in which coordination is restored. Once coordination is restored, it is
maintained unless a later failure causes it to be lost again, and the cycle repeats [6, 7]. The
ability to tolerate fail-stop failures and subsequent repairs of processes and channels is achieved
by allowing each process and channel in the system to be either "up" or "down" and by ensuring
that the ability of the system to self-stabilize is not affected by which processes or channels are
"up" or "down".
Our reset subsystem is designed in a simple, modular, and layered manner. The design consists
of three major components: a leader election, a spanning tree construction, and a diffusing
computation. Each of these components is self-stabilizing, can tolerate process and channel
failures and repairs, and admits bounded-space implementations. These features distinguish our
design of these components from earlier designs [1, 9, 10] and redress the following comment
made by Lamport and Lynch [15, page 1193] : "A self-stabilizing algorithm [that translates a
distributed system designed for a fixed but arbitrary network into one that works for a changing
network] using a finite number of identifiers would be quite useful, but we know of no such
algorithm."
The rest of the paper is organized as follows. In the next section, we describe the layered
structure of our reset subsystem. This structure consists of three layers: a (spanning) tree layer,
a wave layer, and an application layer. These three layers are discussed in Sections 3, 4, and 5
respectively. In Section 6, we discuss implementation issues; in particular, we exhibit bounded,
low atomicity implementations of each layer. Finally, we make concluding remarks in Section 7.
2 Layers of the Reset Subsystem
We make the following assumptions concerning the distributed system to be augmented by our
reset subsystem. The system consists of K processes named P:1; ::: ; P:K. At each instant, each
process is either up or down , and there is a binary, irreflexive, and symmetric relation defined
over the up processes. We call this relation the adjacency relation. Only adjacent processes can
communicate with one another.
The set of up processes and the adjacency relation defined over them can change with time. For
simplicity, however, we assume that the adjacency relation never partitions the up processes in
the system. (Clearly, if partitioning does occur, then any reset request initiated in a partition
will result in resetting the state of only that partition.)
Each process P:i in the system consists of two modules adj:i and appl:i; see Figure 0a. The task
of module adj:i is to maintain a set N:i of the indices of all up processes adjacent to P:i. (Details
of the implementation of adj:i are outside the scope of this paper. One possible implementation,
however, is for each adj:i to communicate periodically with the adj:j module of every potentially
adjacent process P:j and to employ a timeout to determine whether the index j of process P:j
should be in N:i.) The task of the other module, appl:i, is application specific. To perform its
task, appl:i can communicate with module appl:j, j 6= i, only if j is in N:i. One state of appl:i is
distinguished. Together, the distinguished states of each appl:i module comprise the predefined
global "reset" state of the distributed system.
Augmenting such a distributed system with a reset subsystem consists of adding two modules,
tree:i and wave:i, to each process P:i in the system; see Figure 0b. The tree:i modules of
adjacent processes communicate in order to maintain a rooted spanning tree that involves all
the up processes in the system. (Henceforth, the two terms "process" and "up process" are
used interchangeably.) The constructed tree is maintained to be consistent with the current
adjacency relation of the system; thus, any changes in the adjacency relation are eventually
followed by corresponding changes in the spanning tree. Each tree:i module keeps the index
of its "father" process, f:i, in the maintained tree; this information is used by the local wave:i
module in executing a distributed reset.
A distributed reset is executed by the wave:i modules in three phases or "waves". In the first
phase, some appl:i requests a system reset from its local wave:i which forwards the request to
the root of the spanning tree. If other reset requests are made at other processes, then these
requests are also forwarded to the root process. It is convenient to think of all these requests
as forming one "request wave". In the second phase, module wave:i in the root process receives
the request wave, resets the state of its local appl:i to the state of appl:i in the predefined global
state, and initiates a "reset wave". The reset wave travels towards the leaves of the spanning
tree and causes the wave:j module of each encountered process to reset the state of its local
appl:j to the state of appl:j in the predefined global state. When the reset wave reaches a leaf
process it is reflected as a "completion wave" that travels back to the root process; this wave
comprises the third phase. Finally, when the completion wave reaches the root, the reset is
complete, and a new request wave can be started whenever some appl:i deems necessary.
From the above description, it follows that the states of different appl:i modules are reset at
different times within the same distributed reset. This can cause a problem if some appl:i whose
state has been reset communicates with an adjacent appl:j whose state has not yet been reset. To
avoid this problem, we provide a session number sn:i in each appl:i. In a global state, where no
distributed reset is in progress, all session numbers are equal. Each reset of the state of appl:i
is accompanied by incrementing sn:i. We then require that no two adjacent appl:i modules
communicate unless they have equal session numbers. This requirement suffices to ensure our
characterization of a distributed reset; that is, a distributed reset to a given global state yields
a global state that is reachable, by some system computation, from the given global state.
The tree:i modules in different processes constitute the tree layer discussed in Section 3. The
wave:i modules constitute the wave layer discussed in Section 4. The appl:i modules constitute
the application layer discussed in Section 5.
2.1 Programming Notation
The program of each process has the form
begin hmodulei [] . [] hmodulei end
Each module is of the form
module hmodule namei
var hvariable declarationsi ;
parameter hparameter declarationsi ;
begin
hactioni [] . [] hactioni
Thus, a module of a process is defined by a set of variables, a set of parameters, and a set
of actions. Each of these is defined in some detail next.
Each variable in the variable set of a module can be updated (i.e., written) only by modules in
that process; each variable can be read only by modules in that process and modules in adjacent
processes.
Each parameter in the parameter set of a module ranges over a finite domain. The function of
a parameter is to define a set of actions as one parameterized action. For example, let j be a
parameter whose value is 0, 1 or 2; then the parameterized action act:j in the action set of a
module abbreviates the following set of three actions.
Each action in the action set of a module has the form
hguardi \Gamma! hassignment statementi
A guard is a boolean expression over the variables and parameters in the module, and the
variables of one adjacent process. An assignment statement updates one or more variables in
the module.
The operational semantics for a system of such processes is as follows. A state of the system is
defined by a value for every variable in the processes of the system. An action whose guard is
true at some state of the system is said to be enabled at that state. A computation of the system
is a maximal, fair sequence of system steps: in each step, some action that is enabled at the
current state is executed, thereby yielding the next state in the computation. The maximality
of a computation implies that no computation is a proper prefix of another computation. The
fairness of a computation means that each continuously enabled action is eventually executed
in the computation [12].
3 The Tree Layer
The task of the tree layer is to continually maintain a rooted spanning tree even when there are
changes in the set of up processes or in the adjacency relation. In the solution described below,
we accommodate such changes by ensuring that the tree layer performs its task irrespective of
which state it starts from.
In our solution, the rooted spanning tree is represented by a "father" relation between the
processes. Each tree:i module maintains a variable f:i whose value denotes the index of the
current father of process P:i. Since the layer can start in any state, the initial graph of the father
relation (induced by the initial values of the f:i variables) may be arbitrary. In particular, the
initial graph may be a forest of rooted trees or it may contain cycles.
For the case where the initial graph is a forest of rooted trees, all trees are collapsed into a
single tree by giving precedence to the tree whose root has the highest index. This is achieved
as follows. Each tree:i module maintains a variable root:i whose value denotes the index of the
current root process of P:i. If root:i is lower than root:j for some adjacent process P:j then
tree:i sets root:i to root:j and makes P:j the father of P:i.
For the case where the initial graph has cycles, each cycle is detected and removed by using
a bound on the length of the path from each process to its root process in the spanning tree.
This is achieved as follows. Each tree:i module maintains a variable d:i whose value denotes the
length of a shortest path from P:i to P:(root:i). To detect a cycle, tree:i sets d:i to be d:(f:i)+1
whenever f:i 2 N:i and d:i ! K. The net effect of executing this action is that if a cycle exists
then the d:i value of each process P:i in the cycle gets "bumped up" repeatedly. Eventually,
some d:i exceeds K \Gamma 1, where K is the maximum possible number of up processes. Since the
length of each path in the adjacency graph is bounded by K\Gamma1, the cycle is detected. To remove
a cycle that it has detected, tree:i makes P:i its own father.
Because of our assumption that the initial state is arbitrary, we need to consider all other cases
where the initial values of f:i, root:i and d:i are inconsistent. One possibility is that these initial
values are "locally" inconsistent, that is, one or more of the following hold: root:i ! i,
root:i 6= i or d:i 6= 0, or f:i is not i nor in N:i. In this case, tree:i makes itself locally consistent
by setting root:i to i, f:i to i and d:i to 0.
Another possibility is that root:i may be inconsistent with respect to the state of the father
process of P:i, that is, root:i 6=root:(f:i) may hold. In this last case, tree:i corrects the value of
root:i to that of root:j.
Module tree:i is given in Figure 1.
module
var
begin

Figure

1: Module tree:i
We show in Appendix A that starting at any state (i.e., one that could have been reached by
any number of changes in the set of up processes and the adjacency relation over them), the
tree layer is guaranteed to eventually reach a state satisfying the state predicate G, where
At each state in G, for each process P:i, root:i equals the highest index among all up processes,
f:i is such that some shortest path between process P:i and the root process P:(root:i) passes
through the father process P:(f:i), and d:i equals the length of this path. Therefore, a rooted
spanning tree exists. Also, note that each state in G is a fixed-point; i.e., once the tree:i modules
reach a state in G, no action in any of the tree:i modules is enabled.
Our proof employs the "convergence stair" method [13]: we exhibit a finite sequence of state
predicates H:0; H:1; :::; H:K such that
(iii) For each l such that 0- l -K:
H:l is closed under system execution; that is, once H:l holds in an arbitrary system com-
putation, it continues to hold subsequently.
(iv) For each l such that 0- l !K:
Upon starting at an arbitrary state in H:l the system is guaranteed to reach a state in
.
We also show that convergence to a state in G occurs within O(K rounds, where
deg is the maximum degree of nodes in the adjacency graph, dia is the diameter of the adjacency
graph and, informally speaking, a round is a minimal sequence of system steps wherein each
process attempts to execute at least one action.
We conclude this section with the remark that the problems of leader election and spanning tree
construction have received considerable attention in the literature (see, for example, [15, 16, 17]).
Most of these algorithms are based on the assumption that all processes start execution in some
designated initial state. This restriction is too severe for our purposes, and we have lifted it
by designing the tree layer to be self-stabilizing; i.e., insensitive to the initial state. We note
that a self-stabilizing spanning tree algorithm has been recently described in [9]. However, the
algorithm in [9] is based on the simplifying assumption that, at all times, there exists a special
process which knows that it is the root. We have not made this assumption: if a root process
fails, then the remaining up processes elect a new root.
4 The Wave Layer
As outlined in Section 2, the task of the wave layer is to perform a diffusing computation [10]
in which each appl:i module resets its state. The diffusing computation uses the spanning tree
maintained by the tree layer, and consists of three phases. In the first phase, some appl:i
module requests its local wave:i to initiate a global reset; the request is propagated by the wave
modules along the spanning tree path from process P:i to the tree root P:j. In the second phase,
module wave:j in the tree root resets the state of its local appl:j and initiates a reset wave that
propagates along the tree towards the leaves; whenever the reset wave reaches a process P:k the
local wave:k module resets the state of its local appl:k . In the third phase, after the reset wave
reaches the tree leaves it is reflected as a completion wave that is propagated along the tree to
the root; the diffusing computation is complete when the completion wave reaches the root.
To record its current phase, each wave:i module maintains a variable st:i that has three possible
values: normal, initiate, and reset. When module wave:i has propagated the
completion wave of the last diffusing computation and is waiting for the request wave of the next
diffusing computation. When module wave:i has propagated the request wave of
the ongoing diffusing computation and is waiting for its reset wave. When reset, module
wave:i has propagated the reset wave of the ongoing diffusing computation and is waiting for
its completion wave.
Variable st:i is updated as follows. To initiate a new diffusing computation, the local appl:i
module updates st:i from normal to initiate. To propagate a request wave, wave:i likewise
updates st:i from normal to initiate. To propagate a reset wave, wave:i updates st:i from a
value other than reset to reset. Lastly, to propagate a completion wave, wave:i updates st:i
from reset to normal.
It is possible for some appl:i to update st:i from normal to initiate before the completion wave
of the last diffusing computation reaches the root process; thus, multiple diffusing computations
can be in progress simultaneously. To distinguish between successive diffusing computations,
each wave:i module maintains an integer variable sn:i denoting the current session number of
wave:i.
Recall that the operation of the wave layer is subject to changes in the set of up processes and
in the adjacency relation. As before, we accommodate such changes by ensuring that the layer
performs its task irrespective of which state it starts from. In our solution, starting from an
arbitrary state, the wave layer is guaranteed to reach a steady state where all the sn:i values
are equal and each st:i has a value other than reset. In particular, if no diffusing computation
is in progress in a steady state, then all the sn:i values are equal and each st:i has the value
normal. Furthermore, if a diffusing computation is initiated in a steady state where all sn:i
have the value m then it is guaranteed to terminate in a steady state where all
This is achieved by requiring that, during the reset wave, each wave:i module increments sn:i
when it resets the state of the local appl:i module.
Module wave:i is given in Figure 2. The module has five actions. Action (1) propagates the
request wave from a process to its father in the spanning tree. When the request wave reaches
the root process, action (2) starts a reset wave at the root process. Action (3) propagates the
reset wave from the father of a process to the process. Action (4) propagates the completion
wave from the children of a process to the process.
The above four actions of all wave:i modules collectively perform a correct diffusing computation
provided that the wave layer is in a steady state. The steady states of the wave layer are those
where each wave:i satisfies Gd:i,
Action (5) ensures the self-stabilization of the wave layer to steady states.
module
begin
st:i=normal
st:i=initiate - f:i= i \Gamma! st:i; sn:i := reset; sn:i+1 (2)

Figure

2: Module wave:i
We show in Appendix B that starting at any state, the wave layer is guaranteed to eventually
reach a steady state satisfying (8i : sn:i=n - st:i 6=reset) for some integer n. Our proof of this
consists of showing that
(i) Starting at an arbitrary state, the system is guaranteed to reach a state in GD, where
(ii) The state predicate GD is closed under system execution.
(iii) Starting at an arbitrary state in GD where the root process P:k has
is guaranteed to reach a state in (8i : sn:i=n - st:i 6=reset).
We also show that each diffusing computation that is initiated at a state in GD will terminate;
i.e., starting from a state satisfying (GD -
the system is guaranteed to reach a state in (GD -
Lastly, we show that convergence to a GD state occurs within O(ht) rounds and that diffusing
computations terminate within O(min (ht\Thetadg; n) ) rounds, where ht is the height of the spanning
tree constructed by the tree layer, dg is the maximum degree of nodes in the spanning tree, and
n is the number of up processes in the system.
5 The Application Layer
The application layer in a given distributed system is composed of the appl:i modules as shown
in

Figure

0. In this section, we discuss two modifications to the application layer by which our
reset subsystem can be correctly added to the given distributed system.
The first modification is to augment each appl:i module with actions that allow it to request
a distributed reset; as discussed in Section 4, these actions set the variable st:i to initiate and
are enabled when normal holds and a distributed reset is necessary. The situations in
which distributed resets are necessary are application specific. One such situation, however, is
when the global state of the application layer is erroneous. Erroneous states may be detected
by periodically executing a self-stabilizing global state detection algorithm [8, 14]. Towards this
end, we note that it is possible to implement a self-stabilizing global state detection with minor
modifications to our reset subsystem.
The second modification is to restrict the actions of each appl:i module so that the application
layer can continue its execution while a distributed reset is in progress. (Recall that one objective
of our design is to avoid freezing the execution of the given distributed system while performing
resets.) This modification is based on the observation that, during a distributed reset, appl:i
modules can continue executing their actions as long as there is no communication between
modules one of which has been reset and another which has not been reset. Equivalently, if
appl:i modules communicate they should have the same session number (sn) values. Therefore,
we require that the expression "sn:i =sn:j" be conjoined to the guard of each appl:i action that
accesses a variable updated by appl:j; i 6= j: The net effect of this modification is that upon
completion of a distributed reset the collective state of all appl:i modules is reachable by some
application layer execution from the given collective state that the appl:i modules are reset to.
6 Implementation Issues
In this section, we discuss two issues related to implementations of modules tree:i and wave:i .
First, we show that the state-space of each process can be bounded and, second, we show how
to refine the "high" atomicity actions employed thus far into "low" atomicity ones.
6.1 Bounded-Space Construction
Each tree:i module, i 2f1 ::: Kg, updates three variables each requiring log K bits. In contrast,
module wave:i uses an unbounded session number variable. A bounded construction is also
possible: wave:i can be transformed by making sn:i of type f0::N \Gamma1g, where N is an arbitrary
natural constant greater than 1, and replacing the increment operation in the first action with
an increment operation in modulo N arithmetic. Thus, each wave:i module can be implemented
using a constant number of bits. The proof of correctness of the transformed module is similar
to the proof presented in Appendix B, and is left to the reader.
6.2 Transformation to Read/Write Atomicity
Thus far, our design of the tree:i and wave:i modules has not taken into account any atomicity
constraints. Some actions in these modules are of high atomicity; these actions read variables
updated by other processes and instantaneously write other variables. We now refine our design
so as to implement these modules using low atomicity actions only.
Consider the following transformation. For each variable x:i updated by process P:i, introduce
a local variable ~ x:j:i in each process P:j; j 6= i; that reads x:i. Replace every occurrence of x:i in
the actions of P:j with ~ x:j:i, and add the read action ~
x:j:i := x:i to the actions of P:j. Based
on this transformation, read/write atomicity modules for tree:i and wave:i are presented next,
along with proofs of correctness.
The code for read/write atomicity implementation of module tree:i is shown in Figure 3.
We show in Appendix C that starting at any state, the tree layer is guaranteed to eventually
reach a state satisfying the state predicate G, where
The structure of our proof is identical to the proof presented in Appendix A; we exhibit a finite
sequence of state predicates H:0; H:1; :::; H:K such that
(iii) For each l such that 0- l -K:
H:l is closed under system execution; that is, once H:l holds in an arbitrary system com-
putation, it continues to hold subsequently.
(iv) For each l such that 0- l !K:
Upon starting at an arbitrary state in H:l the system is guaranteed to reach a state in
.
module
var
~
root:i:j; ~
~
begin
root:i:j; ~
root:i:j; ~
d:i:j := root:j; f:j; d:j

Figure

3: Implementation of tree:i using Read/Write Atomicity
The code for read/write atomicity implementation of module wave:i is shown in Figure 4.
We show in Appendix D that starting at any state, the wave layer is guaranteed to eventually
reach a state satisfying (8i : sn:i =n - st:i 6= reset) for some integer n. The structure of our
proof is identical to the proof presented in Appendix B; we exhibit a state predicate GD such
that
(i) Starting at an arbitrary state, the system is guaranteed to reach a state in GD.
(ii) GD is closed under system execution.
module
~
~
begin
sn:i:j \Gamma! st:i; sn:i := reset; ~
st:i:j 6=reset - sn:i= ~
sn:i:j \Gamma! sn:i := ~
sn:i:j
st:i:j; ~

Figure

4: Implementation of wave:i using Read/Write Atomicity
(iii) Starting at an arbitrary state in GD where the root process P:k has
is guaranteed to reach a state in (8i : sn:i=n - st:i 6=reset).
We also show that each diffusing computation that is initiated at a state in GD will terminate;
i.e., upon starting from a state satisfying (GD -
integer n the system is guaranteed to reach a state in (GD -
We note that a similar proof exists for a bounded construction of the low atomicity wave:i
module in which sn:i is replaced with a variable of type is an arbitrary
natural constant greater than 3, and the increment operation in the first action is replacing with
an increment operation in modulo N arithmetic.
Conclusions
We have presented algorithms that enable processes in arbitrary distributed systems to perform
distributed resets. These algorithms are novel in that they are self-stabilizing and can tolerate
the fail-stop failures and repairs of arbitrary processes and channels even when a distributed
reset is in progress.
Two comments are in order regarding our choice of fair, nondeterministic interleaving semantics.
First, the requirement of fairness with respect to continuously enabled actions is not necessary,
but is used only in simplifying the proofs of correctness. Second, our design remains correct
even if we weaken the interleaving requirement as follows: in each step, an arbitrary subset of
the processes each execute some enabled action, as long as no two executed actions access the
same shared variable [2, 3, 5].
A comment is also in order regarding our methodology for achieving fault-tolerance in distributed
systems. One way to achieve system fault-tolerance is to ensure that when faults occur
the system continues to satisfy its input-output relation. Systems designed thus "mask" the
effects of faults, and are hence said to be masking fault-tolerant. An alternative way to achieve
system fault-tolerance is to ensure that when faults occur the input-output relation of the system
is violated only temporarily. In other words, the system is guaranteed to eventually resume
satisfying its input-output relation. In this paper, it is the latter "nonmasking" approach to
fault-tolerance that we have adopted.
We give three reasons for sometimes preferring nonmasking fault-tolerance to masking fault-tolerance
when designing distributed systems. First, in some distributed systems, masking
fault-tolerance may be impossible to achieve. For example, there is no masking fault-tolerant
distributed system whose up processes communicate asynchronously and reach consensus on a
binary value even when one or more of the processes fail [11]. Second, even if it is possible to
implement masking fault-tolerance, the cost of doing so may be prohibitive. For example, the
amount of redundancy or synchronization required may be infeasible to implement. And third,
requiring masking fault-tolerance may be more strict than is desirable. For example, a call-back
telephone service that eventually establishes a connection may be quite useful even if it does not
mask its initial failure to establish a connection.
Of course, to be of practical use, nonmasking fault-tolerant distributed systems should be designed
so that the time taken to resume satisfying the desired input-output relation, when faults
occur, is within acceptable bounds.
We envisage several applications of distributed resets where their nonmasking fault-tolerance
is useful. We are currently implementing distributed operating system programs based on distributed
resets including, for example, system programs for multiprocess resynchronization. We
are also currently studying reconfiguration protocols for high speed networks.
We note that distributed resets provide a systematic method for making arbitrary distributed
systems self-stabilizing (cf. [14]): application layer modules can be augmented to perform a self-stabilizing
global state detection periodically, and to request a distributed reset upon detecting
erroneous global states thereby making the distributed system self-stabilizing. Distributed resets
can also be used to transform an arbitrary self-stabilizing program into an equivalent self-stabilizing
program implemented in read/write atomicity.
There are several issues that need to be further investigated. One such issue is the transformation
of our read/write atomicity programs (cf. Figures 3 and 4) into message passing programs, and
the analysis of the resulting programs. Note that for message passing programs the predefined
global reset state includes, in addition to the states of each appl:i module, the state of each
channel in the system. Therefore, in addition to resetting the local state of the module appl:i,
each wave:i module has to send some - possibly empty - sequence of application messages,
each tagged with the new session number, on every outgoing channel of P:i.
Another issue for further study is the design of an efficient mechanism for maintaining a timely
and consistent state of neighboring process indices. A third issue is the security problems
involved in allowing any application process to reset the distributed system, and the protection
mechanism necessary to enforce that application processes interact with the reset subsystem
in the desired manner. Finally, observing that self-stabilizing systems are only one type of
nonmasking fault-tolerant systems, it is desirable to investigate alternative nonmasking fault-tolerant
solutions to the distributed reset problem that are less robust than our self-stabilizing
solutions but are even more efficient.

Acknowledgements

We thank George Varghese for helpful discussions on this paper and the anonymous referees for
their suggestions.



--R

"Applying static network protocols to dynamic networks"
"A foundation of fault-tolerant computing,"
"Convergence of iteration systems"
"Distributed reset (extended abstract)"
"On relaxing interleaving assumptions"
"Token systems that self-stabilize"
"Uniform self-stabilizing rings"
"Distributed snapshots: Determining global states of distributed systems"
"Self-stabilization of dynamic systems assuming only read/write atomicity"
"Termination detection for diffusing computa- tions"
"Impossibility of distributed consensus with one faulty process"

"Stabilizing communication protocols"
"Self-stabilizing extensions for message-passing systems"
"Distributed computing: models and methods"
"An algorithm for distributed computation of a spanning tree in an extended LAN"
"A correctness proof of a topology information maintenance protocol for a distributed computer network"
--TR
Uniform self-stabilizing rings
Token Systems That Self-Stabilize
Self-stabilizing extensions for message-passing systems
Self-stabilization of dynamic systems assuming only read/write atomicity
Distributed computing
Stabilizing Communication Protocols
A foundation of fault-tolerant computing
Impossibility of distributed consensus with one faulty process
Distributed snapshots
An algorithm for distributed computation of a spanningtree in an extended LAN
A correctness proof of a topology information maintenance protocol for a distributed computer network
Distributed Reset (Extended Abstract)

--CTR
Jorge A. Cobb , Mohamed G. Gouda, Stabilization of general loop-free routing, Journal of Parallel and Distributed Computing, v.62 n.5, p.922-944, May 2002
Hongwei Zhang , Anish Arora, GS3: scalable self-configuration and self-healing in wireless sensor networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.459-480, 15 November
Wilfried Steiner , Michael Paulitsch , Hermann Kopetz, The TTA's Approach to Resilience after Transient Upsets, Real-Time Systems, v.32 n.3, p.213-233, March     2006
Franck Petit , Vincent Villain, Optimal snap-stabilizing depth-first token circulation in tree networks, Journal of Parallel and Distributed Computing, v.67 n.1, p.1-12, January, 2007
Christian Boulinier , Franck Petit , Vincent Villain, When graph theory helps self-stabilization, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Neeraj Mittal , Prajwal K. Mohan, A priority-based distributed group mutual exclusion algorithm when group access is non-uniform, Journal of Parallel and Distributed Computing, v.67 n.7, p.797-815, July, 2007
Mohamed G. Gouda , Marco Schneider, Maximizable routing metrics, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.663-675, August
Mohamed G. Gouda , Marco Schneider, Memory requirements for silent stabilization, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.27-34, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Alain Cournier , Ajoy K. Datta , Franck Petit , Vincent Villain, Optimal snap-stabilizing PIF algorithms in un-oriented trees, Journal of High Speed Networks, v.14 n.2, p.185-200, April 2005
Mehmet Hakan Karaata, Self-Stabilizing Strong Fairness under Weak Fairness, IEEE Transactions on Parallel and Distributed Systems, v.12 n.4, p.337-345, April 2001
Anish Arora , Mikhail Nesterenko, Unifying stabilization and termination in message-passing systems, Distributed Computing, v.17 n.3, p.279-290, March 2005
Mehmet Hakan Karaata, An optimal self-stabilizing strarvation-free alternator, Journal of Computer and System Sciences, v.71 n.4, p.480-494, November 2005
Mehmet Hakan Karaata, A stabilizing algorithm for finding biconnected components, Journal of Parallel and Distributed Computing, v.62 n.5, p.982-999, May 2002
Fatima Belkouch , Marc Bui , Liming Chen , Ajoy K. Datta, Self-stabilizing deterministic network decomposition, Journal of Parallel and Distributed Computing, v.62 n.4, p.696-714, April 2002
Mikhail Nesterenko , Anish Arora, Stabilization-preserving atomicity refinement, Journal of Parallel and Distributed Computing, v.62 n.5, p.766-791, May 2002
Joffroy Beauquier , Maria Gradinariu , Colette Johnen, Memory space requirements for self-stabilizing leader election protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.199-207, May 04-06, 1999, Atlanta, Georgia, United States
Sandeep S. Kulkarni , Ravikant, Stabilizing causal deterministic merge, Journal of High Speed Networks, v.14 n.2, p.155-183, April 2005
Azzedine Boukerche , Kaouther Abrougui, An efficient leader election protocol for mobile networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
Anish Arora , Paul C. Attie , E. Allen Emerson, Synthesis of fault-tolerant concurrent programs, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.173-182, June 28-July 02, 1998, Puerto Vallarta, Mexico
Albert Mo Kim Cheng , Seiya Fujii, Self-Stabilizing Real-Time OPS5 Production Systems, IEEE Transactions on Knowledge and Data Engineering, v.16 n.12, p.1543-1554, December 2004
Yehuda Afek , Shlomi Dolev, Local stabilizer, Journal of Parallel and Distributed Computing, v.62 n.5, p.745-765, May 2002
Yehuda Afek , Anat Bremler, Self-stabilizing unidirectional network algorithms by power-supply, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.111-120, January 05-07, 1997, New Orleans, Louisiana, United States
Felix C. Grtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Computing Surveys (CSUR), v.31 n.1, p.1-26, March 1999
Hongwei Zhang , Anish Arora, GS3: scalable self-configuration and self-healing in wireless networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
A. Arora , P. Dutta , S. Bapat , V. Kulathumani , H. Zhang , V. Naik , V. Mittal , H. Cao , M. Demirbas , M. Gouda , Y. Choi , T. Herman , S. Kulkarni , U. Arumugam , M. Nesterenko , A. Vora , M. Miyashita, A line in the sand: a wireless sensor network for target detection, classification, and tracking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.605-634, 5 December 2004
diffusing computation;robustness;fault tolerant computing;process failures;self-stabilizing components;system recovery;distributed reset subsystem;distributed processing;channel failures;process repairs;up-process coordination;leader election;embedded system;layered design;channel repairs;fault tolerance;spanning tree construction;reliability;fail-stop failure tolerance