Resource Bounds for Self-Stabilizing Message-Driven Protocols.
Self-stabilizing message-driven protocols are defined and discussed.      The class weak exclusion that contains many natural tasks      such as $\ell$-exclusion and token passing is defined,      and it is shown that in any execution of any self-stabilizing      protocol for a task in this class, the configuration size must grow      at least in a logarithmic rate. This last lower bound is valid even      if the system is supported by a time-out mechanism that prevents      communication deadlocks. Then we present three self-stabilizing      message-driven protocols for token passing. The rate of growth of      configuration size for all three protocols matches the aforementioned      lower bound. Our protocols are presented for two-processor systems      but can be easily adapted to rings of arbitrary size. Our results      have an interesting interpretation in terms of automata theory.
Introduction
A distributed system is a set of state machines, called processors, which communicate either
by shared variables or by message-passing. In the first case, the system is a shared memory
system, in the second case the system is a message-passing system. A distributed system is self-stabilizing
if it can be started in any possible global state. Once started, the system regains its
consistency by itself, without any kind of an outside intervention. The self-stabilization property
is very useful for systems in which processors may crash and then recover spontaneously in an
arbitrary state. When the intermediate period in between one recovery and the next crash is
long enough, the system-stabilizes. Self-stabilizing systems were defined and discussed first in
the fundamental paper of Dijkstra, [Dij-74]. The work of [Dij-74] as well as most of the following
work on self-stabilizing systems assume the communication model of shared variables. Among
these papers are [Kr-79], [Tc-81], [Dij-82], [La-86], [BGW-87], [Bu-87], [BP-88], [IJ-90], [IJ-90a],
[DIM-90] and [DIM-91].
In the study of fault tolerant message-passing systems, it is customarily assumed that messages
might be corrupted over links, hence, processors may enter arbitrary states and link contents
may be arbitrary. Self-stabilizing protocols treat these problems naturally, since they are
designed to recover from inconsistent global-states. Surprisingly, there are very few papers which
address self-stabilizing, message-passing systems. The earliest research in this model was done
by Gouda and Multari in [Mu-89, GM-91]. In that work, they have developed a self-stabilizing
sliding window protocol and two-way handshake that use unbounded counters. They proved
that any self-stabilizing message passing protocol must use time-outs and have infinite number
of safe states. Following [GM-91], two additional works dealt with self-stabilizing protocols in
this model: The work of Katz and Perry, [KP-90], presents a general tool for extending an
arbitrary message-passing protocol to a self-stabilizing protocol. The work of Afek and Brown,
[AB-89], presents a self-stabilizing version of the well-known alternating-bit protocol, (see e.g.
[BSW-69]).
In this work we research complexity issues related to self-stabilizing, message-passing sys-
tems; to do that we define a configuration of any message-passing system as a list of the states of
the processors and of the messages which are in transit on each link. The size of a configuration
of a message-passing system is the number of bits required to encode the configuration entirely.
A protocol for a message-passing system is message-driven if any action of the processors is
initiated by receiving a message. In the work of Gouda and Multari, [GM-91], it is proven that
any message-driven protocol has a possible configuration in which all processors are waiting
for messages but there are no messages on any link. This unwanted situation is called communication
deadlock. A self-stabilizing system should stabilize when started from any possible
initial configuration, including a configuration with communication deadlock. This implies that
a non-trivial, completely asynchronous, self-stabilizing system cannot be message-driven. This
problem can be dealt with in at least two methods: Gouda and Multari, in [GM-91], proposed
the use of a time-out mechanism which preserves the message driven structure of the protocol at
the expense of compromising the complete asynchronisity. On the other hand, Katz and Perry,
in [KP-90], have chosen to give up the message-driven structure and present protocols for which
at any configuration there is at least one processor whose next operation is sending a message.
Thus, there is an execution in which in every atomic step a message is sent, and no message is
ever received. In this execution the size of the configurations grows linearly.
In this work we define and study the class of self-stabilizing, message-driven protocols. By
the argument of [GM-91], there exists no self-stabilizing, message-driven protocol which is completely
asynchronous. Since we look for protocols whose configuration size does not grow in linear
rate we resort to slightly limited assumptions of asynchronous behavior. For lower bounds we
assume an abstract time-out device which detects communication deadlocks and initiates the
system upon their occurrence. Consequently, the lower bounds we present take into account
only executions in which no communication deadlock occurs. Our upper bounds assume that in
every initial configuration there is at least one message on some link. This assumption is much
weaker than the assumption on a general time-out mechanism.
A specific task which we study in details is token-passing. Informally, the token-passing task
is to pass a single token fairly among the system's processors. Usually it is assumed that in the
system's predefined initial configuration there exists a single token. In self-stabilizing system in
which there is no predefined initial configuration, each execution should reach a configuration
in which exactly one token is present in the entire system. Token-passing is a very basic task
in fault tolerant systems, among other works it was studied in [DK-86] for some fault tolerant
message-passing systems and in [IJ-90], for self-stabilizing, shared memory systems. The token-passing
task can be looked at as a special case of mutual-exclusion since possession of the single
token can be interpreted as a permission to enter the critical section.
In the first part of the presentation we prove a lower bound on the configuration size for
protocols for a large class of tasks called weak-exclusion. The weak-exclusion class contains all
non-trivial tasks which require continuous changes in the system's configuration; in particular
this class includes both '-exclusion and token-passing. We show that the configuration size
of any self-stabilizing protocol which realizes any weak-exclusion task is at least logarithmic
in the number of steps executed by the protocol. The lower bound holds for message-driven
protocols for any week-exclusion task, including protocols for systems equipped with time-out
mechanism. This result should be compared with a result of [GM-91] where it is shown that
any message-driven, self-stabilizing protocol (not necessarily for week-exclusion task) must have
infinitely many safe system configurations, but not that each specific execution must contain
infinitely many distinct configurations, as implied by our results. Our lower bound does not
specify which part of the system grows, is it the size of the memory used by the state machines,
the size of messages stored on the links, the number of messages stored on the links or all of
these together?
We then present three self-stabilizing, message-driven protocols for token-passing. The communication
deadlock problem is avoided by the assumption that at least a single message is
present on some communication link. Using this assumption, we present three token-passing
protocols, for two processors each. The rate of growth of configuration size for all three protocols
matches the aforementioned lower bound. All protocols are presented for systems with two
processors but can be easily adapted to work on rings of arbitrary size without increasing their
asymptotic complexity. This is done by considering the ring as a single virtual link.
In the first protocol both processors memory and messages size grow unboundedly with
time, this protocol uses ideas similar to the ideas of the sliding window protocol of [GM-91].
The second protocol is an improvement on the first protocol in which the size of the memory
of the processors grows (in logarithmic rate) while the size of the link content is bounded. The
second protocol is an improvement of the deterministic alternating bit protocol of [AB-89]. The
third protocol is a self-stabilizing token-passing protocol in which processors are deterministic
finite state machines and messages are of fixed size. The only growing part of the system is the
number of messages on the links; the rate of growth matches the lower bound mentioned above.
Our results can be described also in terms of automata theory, as follows: Let \Sigma be an
alphabet. Define a queue machine Q to be a finite state machine which is equipped with a
queue, which initially contains an arbitrary non empty word from \Sigma + . Initially Q is in an
arbitrary state, and in each step it performs the following: (a) reads and deletes a letter from
the head of the queue, (b) adds one or more letters from \Sigma to the tail of the queue, and (c) moves
to a new state. The computational power of a queue machine is severely limited by the fact that
its input alphabet and its work alphabet are identical. In particular a queue machine cannot
perform simple tasks like computing the length of the input word, or even deciding whether the
input word contains a specific letter.
Assume that the alphabet contains a specified subset - of token letters. A queue machine is
a token-controller if, starting with a nonempty queue of arbitrary content, eventually the queue
contains exactly one occurrence of a letter from - forever. Our lower bound result implies that
if a token-controller exists, then in every computation the size of the queue must grow at least
logarithmic in the number of moves of the machine. Our third protocol implies that a token-
controller whose configuration size growth matches the lower bound exists. In view of the fact
that a queue machine cannot compute any estimation of the number of occurrences of letters
from - in the input word, this latter result appears to be somewhat counter intuitive.
Self-Stabilizing Message-Driven Systems
2.1 Asynchronous Message-Driven Systems
An asynchronous, distributed, message-passing system contains n processors where each processor
is a state machine. Processors communicate using message-passing along links. An edge
stands for two directed links, one from P i to P j and the other from P j to P i . A
message sent from P i to P j can be delayed for an unbounded amount of time on the connecting
link. Messages which did not reach their destination yet, are stored on the link and transferred
in FIFO (First In First Out) order.
A processor is uniquely defined by the set of its atomic steps. Whenever a processor is
active it executes one of its atomic steps. In a message-driven protocol an atomic step of
any processor P begins with a receive operation in which P receives a message from one
of its incoming links. The atomic step ends with zero or more send operations in which
sends messages along some of its outgoing links. An atomic step a of P i is defined by
is in state s i 1
e is the link through which P i receives the message msg, e 1 are the outgoing links
along which P i sends msg respectively and s i 2
is the state of P i following the
execution of this atomic step.
Let n and m be the number of processors and links respectively in the system. For
denote by S i the set of states of P i . A configuration of the system is a vector of states of
all processors together with m lists, a list for every link, of messages stored on that link. A
configuration is denoted by c=(s 1 \Theta s 2 \Theta \Delta \Delta \Delta s n \Theta M e 1
\Theta M e 2
em
a list of the messages stored on e j , for 1 - j - m. Let c be a configuration
) be an atomic step.
a is applicable to (P i in) c, if P i is in state s i 1
in c and msg is the first message stored on e in c.
Application of a to c yields the result configuration c 0 . We denote this fact by c a
sequence of atomic steps, is applicable to configuration c 0 , if the first atomic
step in the sequence, a 1 , is applicable to c 0 , the second atomic step is applicable to c 1 where
a 1
\Delta) is a (finite or infinite) sequence which
starts with some arbitrary configuration c 0 and for every i ? 0, c
a i
that is: the sequence
of atomic steps is applicable to c 0 . Note: Since we deal with self-stabilizing
systems we do not assume any particular initial configuration, every configuration is a valid
initial configuration. Execution E is fair if every atomic step that is applicable infinitely often
is executed infinitely often.
Each execution E defines a partial order on the atomic steps of E by the relation happened
before of Lamport in [La-78]:
1. If a i and a j are atomic steps executed by the same processor in E and a i appears before
a j in E, then a i happened before a j .
2. If during a i the message msg is sent and during a j the same message msg is received, then
a i happened before a j .
3. If a i happened before a j and a j happened before a k then a i happened before a k .
We also adopt the definition of concurrent atomic steps from [La-78]: atomic steps a 1
are said to be concurrent in an execution E if for 1 does not happen before a j
and a j does not happen before a i in E. The following proposition gives a sufficient condition for
a set of steps to be concurrent in some execution:
be k distinct processors and let be a set of
atomic steps where a j is aplicable to P in some configuration c. Then there exists
an execution in which the atomic steps a 1 \Delta \Delta \Delta a k are concurrent.
Proof: Observe that once step a is applicable to processor P in configuration c, step a
remains applicable to P in all subsequent configurations. The execution E is defined as the
execution that starts from c, in which processors P
are activated one after the other,
and each processor P i j executes a j . The proof follows since the processors are distinct and since
in E, no message that was sent during a received before a k is executed. Note that
the proposition holds for any system in which once some step is applicable it remains applicable
as long as it is not executed.
An asynchronous protocol, PR, is defined by a set of n processors. By the above definitions,
an asynchronous protocol defines a set of executions that satisfy the following:
1. \Delta) be an arbitrary execution of PR. Then every prefix of E is also
an execution of PR.
2. arbitrary finite execution of PR. Then for every
atomic step a and configuration c, satisfying c r
a
c, PR has an execution E ffi (a; c) 1 .
1 For sequences S 1
denotes the concatenation of S 1
2.2 Self-Stabilizing Message-Driven Protocols
A self-stabilizing system demonstrates a legitimate behavior some time after it is started from
an arbitrary configuration. A natural way to specify a behavior in an abstract way is by a set
of sequences of configurations. We define tasks as sets of legitimate-sequences. The semantics
of any specific task is expressed by requirements on its sequences. Intuitively each legitimate
sequence can be thought of as an execution of a protocol but we do not require it formally. For
instance, the mutual-exclusion task is defined as the set of sequences of configurations which
Each processor has a subset of its states called critical section; in each configuration,
at most one processor is in its critical section, and every processor is in its critical section in
infinitely many configurations. To formally define a task T , one should specify for each possible
system ST , a set of legitimate sequences for ST . The task T is defined as the union of the
legitimate sequence set over all possible systems. A configuration c of a system is safe with
respect to a task T and a protocol PR if any fair execution of PR starting from c belongs to T .
In proving lower bound results on self-stabilizing message-driven protocols, we assume that
the system can recover from a communication deadlock (called deadlock from now on). In
other words: When we prove our lower bounds, we assume only that the protocol stabilizes in
executions in which no deadlock occurs. For this purpose, we distinguish between two types of
deadlocks: global and local. A configuration c is a global deadlock configuration if no atomic step
is applicable to c. Our first lower bound holds for asynchronous systems that can recover from
global deadlocks by applying a global time-out mechanism. This abstract mechanism initiates
a system in a global deadlock configuration to a default initial configuration, after which no
deadlock occurs. Below we bring the requirement for self-stabilizing systems equipped with a
global time-out mechanism. In this definition the system is required to reach a safe configuration
in every infinite fair execution. Note that by our definition an infinite fair execution does not
have a deadlock configuration.
assuming global time-out mechanism
Let PR and LE be a message driven protocol and set of legitimate sequences, respectively.
Protocol PR is sellf-stabilizing relative to LE, if for every c, there is an execution of PR
that starts with c and every such infinite fair execution reaches a safe configuration with
respect to LE and PR.
Later on, we prove a lower bound that holds for systems immuned from a stonger type
of communication deadlock called local deadlock. Processor P is in a local deadlock during
execution E, if P is activated (i.e. executes an atomic step) only finitely many times during E.
The second lower bound holds for systems equipped with an abstract local time-out mechanism
which prevents such executions (e.g. by enabling each processor which is idle for a sufficiently
long time to initiate the system to some default configuration after which no deadlock is possible).
Note that a local time-out mechanism is strictly stronger than a global time-out mechanism.
assuming local time-out mechanism
Let PR and LE be a message driven protocol and set of legitimate sequences, respectively.
Protocol PR is sellf-stabilizing relative to LE, if for every c, there is an execution of
PR that starts with c, and every such infinite fair execution, in which each processor is
activated infinitely often, reaches a safe configuration with respect to LE and PR.
3 Lower Bound
In this section we prove a lower bound on the rate in which the configuration size grows along
every execution of any protocol for a large class of tasks called weak-exclusion. This class
contains all non-trivial tasks which require continuous changes in the system's configuration; in
particular this class includes both '-exclusion and token-passing. For an execution E, denote
by A i (E) the set of distinct atomic steps executed by P i during E. A task belongs to the class
weak-exclusion if its set of legitimate sequences, LE, satisfies:
[WE]- For any E 2 LE there exists a set of two or more atomic steps
where a j 2 A i j (E), such that the atomic steps in B are never concurrent during E.
We first consider self-stabilizing protocols for systems equipped with a global time-out mech-
anism. For these protocols we prove that in every execution (in which no communication dead-lock
occurs) all configurations are distinct. From this we conclude that the configuration size of
every self-stabilizing protocol which realizes any weak-exclusion task is at least logarithmic in
the number of steps executed by the protocol. Throughout the proof we assume that PR is a
self-stabilizing, message-driven protocol for an arbitrary weak-exclusion task, in a system with
a global time-out mechanism. At the end of this section, we present a slightly weaker lower
bound for systems with a local time-out mechanism.
For any configuration c and any link e, denote by M c
e
the sequence of messages present on e
in c. For any execution E, denote by M E
e;s
e;r
) the sequence of messages sent (received) along
e during E.
Proposition 2: For every execution and for every link e, M c 0
e;r
cr
e
Proof: The left hand side of the equation contains the messages present on e in c 0 , concatenated
with the messages sent during E, through e. The right hand side of the equation contains
the messages received during E through e, concatenated with the messages left on e in c r . It is
not hard to verify that both sides of the equation represent the same sequence of messages.
An execution configuration c ' is equal to its initial
configuration c 0 is called a circular execution. A link e is active in a circular execution E if
some messages are received (and hence, by the circularity of E, some messages are sent) along
e in E. Repeating a circular execution E forever yields an infinite execution E 1 which is
not necessarily fair - The original execution may have an applicable step a which is never
executed during E. The step a is applicable throughout E 1 but it is never executed. To
avoid this problem the original circular execution is changed by removing all messages from
links that are not active throughout E. The result execution, which is still called E is still
circular and its infinite repetition E 1 is a fair infinite execution. Observe that an execution
in which a certain configuration appears more than once has a circular sub-execution,
. Thus, to show that in
every execution of PR all the configurations are distinct, we assume that PR has a circular
sub-execution E and reach a contradiction by showing that PR is not self-stabilizing.
Using E, we now construct an initial configuration c init by changing the list of messages in
transit on the system's links. For each link e, the list of messages in transit on e, at c init , is
obtained by concatenating the list of messages in transit on e at c 0 with the list of all messages
sent on e during E. Roughly speaking, the effect of this change is creating an additional
"layer" of messages that helps to decouple each send from its counterpart receive and achieve an
additional flexibility in the system which enables the proof of the lower bound: Formally, c init
is obtained from c 0 as follows:
ffl The state of each processor in c init is equal to its state in c 0 .
ffl For any active link in E, M c init
e
e
e;s
and for any non-active link in E, M c init
e
is
empty.
Let A(i) be the sequence of atomic steps executed by P i during E. Define merge(A) to be
the set of sequences obtained by all possible mergings of all sequences A(i), 1
keeping the internal order in each A(i). Note that all the sequences in merge(A) have the same
finite length and contain the same atomic steps in different orders.
Lemma 3: Every A 2 merge(A) is applicable to c init , and the resulting execution,
is a circular execution of PR.
Proof: Let A be an arbitrary sequence in merge(A) and let P i be an arbitrary processor of
the system. Then we have: (i) The initial state of P i in c init is equal to its initial state in c 0 . (ii)
In c init all messages which P i receives during E are stored on P i 's appropriate incoming links in
the right order. (iii) The atomic steps of P i appear in A in the same order they appear in A(i).
above imply that the sequence A is applicable to c init , and the application of A to c init
yields an execution, EA , with result configuration, c res whose state vector is equal to the state
vector of c init and in which for every active link M EA
e;s
e;s
and M EA
e;r
e;r
To prove that the obtained execution is circular it remains to be shown that the content of
every link in the result configuration, c res , is equal to its content in c init i.e. M c init
e
cres
e
. For
any arbitrary link e it holds that:
1. M c init
e
e;s
e;r
cres
e
(by Proposition 2 and by the fact that M EA
e;s
e;s
and
e;r
e;r
2. M c 0
e (by Proposition 2 and the circularity of E).
Replacing M c init
e
in equation 1 with its explicit contents yields:
3. M c 0
cres
e .
Using equation 2 to replace M c 0
e
e;s
by
e;r
e
in equation 3 gives:
4. M E
e;r
e
e;s
e;r
cres
Dropping
e;r from the two sides of equation 4 yields the desired result: M c init
cres
e
, which proves the lemma.
Define blowup(E) to be the set of executions whose initial sate is c init and whose sequence
of atomic steps belongs to merge(A). Notice that, for every circular execution E and for every
execution holds that A i
Lemma 4: For any set of atomic steps
(E), there is
an execution E 2 blowup(E) that contains a configuration for which all the atomic steps in B
are concurrent.
Proof: For notational simplicity, assume that g. Let
be the sequence constructed as follows: first take all the steps in A(1) that
precede a 1 , then take all the steps in A(2) that precede a 2 ,., then take all the steps in A(n)
that precede a n . Applying the sequence constructed so far to c init results in a configuration in
which all the a i 's are applicable. This sequence is completed to a sequence A in merge(A) by
taking the remaining atomic steps in an arbitrary order, which keeps the internal order of each
A i .
PR be a self-stabilizing, message-driven protocol for an arbitrary weak-
exclusion task T , in a system with a global time-out mechanism. If PR has a circular execution
then PR has an infinite fair execution E 1 none of whose configuration is safe for T .
Proof: Let E be an arbitrary execution in blowup(E). Define E 1 to be the infinite execution
obtained by repeating E forever). By the definition of blowup(E), E 1 is fair. So it remains to
show that no configuration in E 1 is safe.
Assume by way of contradiction that some configuration c 0 in E 1 is safe. Now, we construct
a finite circular execution E 0 whose sequence of atomic steps A 0 is obtained by concatenating
sequences from merge(A), that is A i PR is a protocol for some weak-
exclusion task, E 0 should have some set of atomic steps
that
are never applicable for a single configuration c during E 0 . We reach a contradiction by refuting
this statement for For this we choose some arbitrary enumeration
the sets containing n atomic steps of n distinct processors. Execution E 0 is constructed by first
continuing the computation from c 0 as in E until configuration c init is reached. Then apply
Lemma 4 to extend E 0 by s consecutive executions contains
a configuration in which all the steps in B k are applicable and that ends with c init . The proof
follows. Note: Execution E 0 can be repeated forever to obtain an infinite execution which
does not have any suffix in LE, thus, the protocol PR is not even pseudo self-stabilizing (see
[BGM-90]).
The proof for the lower bound is completed by the following theorem:
Theorem 6 : Let PR be a self-stabilizing, message-driven protocol for an arbitrary weak-
exclusion task, in a system with a global time-out mechanism. For every execution E of PR,
all the configurations of E are distinct. Hence, for every t ? 0, the size of at least one of the
first t configurations in E is at least dlog 2 (t)e.
Proof: Assume by way of contradiction that there exists an execution E of PR in which not
all the configurations are distinct, then E contains a circular sub-execution, E. By Lemma 5,
there exists an infinite execution E 0 of PR, which is obtained by an infinite repetition of some
execution from blowup(E), and which never reaches a safe configuration, a contradiction.
For proving a similar lower bound to systems with a local time-out mechanism the definition
of a circular execution must be modified. Removing messages from non active links to construct
an infinite execution from E as in the proof of Theorem 6 may yield an infinite execution in
which some processor is enabled only finitely many times. In order to allow repetitions of finite
executions to form an infinite fair execution, in which every processor is active infinitely often,
we require that each such finite execution contains an atomic step of each processor in the
system. For this we need the concept of a round of an execution: Let E 0 be a minimal prefix
of an execution E in which every processor receives a message; E 0 is the first round of E. Let
00 be the suffix of E which satisfies . The second round of E is the first round of
be the prefix that contains the first i atomic steps of E. Let t
be the number of rounds in E i . The next theorem presents a lower bound for systems equipped
with a local time-out mechanism. The proof is similar to the proof of Theorem 6.
Theorem PR be a self-stabilizing, message-driven protocol for an arbitrary weak-
exclusion task, in a system with a local time-out mechanism. For every execution E of PR,
does not contain a circular sub-execution which contains a complete round. From this we
conclude that in each execution of PR, E, the first t rounds contain at least t distinct configu-
rations. Hence, for every t ? 0, the size of at least one configuration in E i , is at least dlog 2
In particular, in any fair execution, the configuration size is unbounded.
4 Upper Bound
The token-passing task is defined informally as a set of executions in which a single token is
present in the entire system and is passed fairly among the system's processors. Token-passing
is a special case of mutual-exclusion since possession of the single token can be interpreted
as a permission to enter the critical section. For this reason token-passing also satisfies the
weak-exclusion property, and hence the lower bound of section 3 holds for it. In particular, it
means that any self-stabilizing, message-driven protocol PR for token-passing must use some
unbounded resource, since in any infinite execution the system size grows beyond any bound. In
this section we present three self-stabilizing, token-passing protocols for systems of two proces-
sors. In each protocol the configuration size grows during every execution at a rate that matches
the lower bound. Each of these protocols can be easily adapted to work on rings of arbitrary
size without increasing its asymptotic complexity, by considering the ring as a single virtual link.
Similar ideas can be used for adapting the protocols to arbitrary rooted tree systems.
By a standard symmetry argument there exists no self-stabilizing, deterministic, token-passing
protocol if the processors are identical. Hence, in this section we assume that the system
consists of two distinct processors, called sender and receiver, connected by two links: The first
link carries messages from the sender to the receiver while the second link carries messages from
the receiver back to the sender. The receiver processor is identical in all three protocols and
it is probably the simplest possible finite-state machine. Its program is to copy each message
it receives from its incoming link to its outgoing link without any alteration. To the outside
world, the combined behavior of the receiver and the two links looks like the behavior of a single
queue whose head and tail are used by the receiver. In our analysis we ignore the receiver and
consider systems with a single processor, the sender, communicating with itself using a single
link on which messages are kept in FIFO order. In each step the sender consumes a message
from the head of the link and puts one (or more) messages back at the tail of the link. Tokens are
represented by a special symbol, T , which is appended to some of the messages. Our protocols
specify the messages that carry a token, but they do not use explicitly the token symbol T , The
protocol should guarantee that eventually there is a unique message in the system to which T is
appended. All our protocols assume that initially there is at least one message on the link (this
assumption is weaker than both the global and the local versions of the time-out mechanism).
With this last assumption, the requirement that the link never becomes empty is equivalent to
the requirement that whenever a message is received, at least one message is sent. Hence in
every step of the protocol the sender receives the message on the head of the (single) link and
then puts one or more messages at the link's end. The three protocols we present are:
Protocol 1: In this protocol the sender is an infinite state machine, and in every execution the
link capacity is unbounded.
Protocol 2: In this protocol the sender is an infinite state machine, but in each infinite execution
the link capacity is bounded (the bound for each specific execution depends on its initial
configuration).
Protocol 3: In this protocol both processors are finite state machines.
do forever
3 if msg counter - counter then (* token arrives *)
4 begin (* send new token *)
5 counter:= msg counter +1
6 send(counter, T)
8 else send(counter)
9 end

Figure

1: protocol 1
protocol 1 (of the sender) appears in Figure 1. The sender uses a variable called counter. Each
message consists of the present value of counter, possibly with the token symbol T . Whenever
the sender receives a message whose counter value, msg counter, is not smaller than counter,
it sets counter := msg counter sends this new value of counter together with the
token T ; otherwise the sender just sends the current value of counter (without the token T ).
The token letter T is not used by the protocol itself. The correctness of the protocol is based
on the fact that eventually the value of counter will be larger than all the values that appear in
the messages present on the link in the initial configuration. The asymptotic size of counter in
each execution is
is the number of messages sent. The details of the proof are
omitted.
4.1 Aperiodic Sequences
Protocols 2 and 3 use the following method: each message is associated with some ternary
number which is called color. The protocol considers any message whose color is different from
the color of the previous message as carrying a token. The sender has a local variable called
token color. At any given configuration the sender is sending a sequence of messages whose color
is equal to (the value of) token color; at the same time the sender waits for a message whose
color is equal to token color. As long as the sender receives messages of different colors it sends
messages whose color is equal to token color. Once the sender receives a message whose color
is equal to token color, it chooses a new token color, and initiates a new sequence of messages
whose color is the new token color by sending the first message in this new sequence. This
first message is carrying a (virtual) token. Then the sender continues sending messages of the
new token color (without tokens), until it receives a message of the new token color, and so on.
Our goal is to reach a configuration after which the link always holds at most two consecutive
sequences of messages where the colors of all messages in each sequence are equal. In every
step the sender consumes a single message from the first sequence whose color is the previous
token color and produces one or more messages whose color is equal to the present token color.
After the last message whose color is the previous token color is consumed the link contains a
single sequence of messages whose color is token color. In the next step the sender receives the
token carried by this sequence and sends it once again by initiating a new sequence of
messages whose color is the new token color. In each of the described configurations there exists
a single token which is carried by the first message of the sequence whose color is token color.
The correctness of the protocols follows from the fact that the sequences of token-colors sent by
the receiver is aperiodic, as defined below.
sequence A= (a 1 ; a positive integer k and for all
. The sequence A is eventually periodic if it has a suffix which is periodic. A is
aperiodic if it is not eventually periodic.
Aperiodic sequences over the integers f0; 1; 2g were used in [AB-89] in order to obtain self-
stabilizing, data link protocols. Such sequences are created there either by a random number
generator or by an infinite state machine (in the first case the algorithm is randomized). The
elements of this sequence are used by the protocol of [AB-89] whenever it has to decide on the
ternary number to be sent with a new message. In this paper aperiodic sequences are generated
by using a counter and the sequence xor defined below:
Definition: For an integer i, xor(i) is the sum of the bits (mod 2) in the binary representation
of i (e.g., 0). The sequence denoted by
xor.
As we show later, the sequence xor is aperiodic.
(of the sender) which appears in Figure 2, is an improvement of the protocol that
appears in [AB-89] in the sense that it achieves the lower bound of the previous section. the
sense that it achieves the lower bound of the previous section. (The amount of memory used
for producing the aperiodic sequence is not addressed nor specified in [AB-89].) In protocol 2
do forever
token color then (* token arrives *)
4 begin (* send new token *)
6 counter := counter +1
8 send(token color)
9 end

Figure

2: protocol 2
the sender keeps a counter in its local memory; whenever a message with a new color is sent
the counter is incremented. The new color 2 f0; 1; 2g is determined by the previous color and
by applying xor to the counter. Roughly speaking, the correctness of the protocol is implied by
the fact that since xor is aperiodic, the sequence of colors generated by the sender is aperiodic
as well. The nature of the variables and the correctness proof of protocol 2 are easily derived
from the description of protocol 3 and from its correctness proof, hence, they are omitted.
4.2 Informal Description of Protocol 3
We now present protocol 3, in which both processors are finite state machines. It is easily
observed that when an aperiodic sequence is supplied by some external device, a finite state
machine can use this sequence to perform the protocol in [AB-89]. Our construction uses the fact
that the finite state machine augmented with the previously described FIFO link can generate
an aperiodic sequence. The finite state machine uses the link both for message-passing and for
generating the aperiodic sequence, while its size is kept within the optimal bound. Protocol 3
can be easily transformed to a self-stabilizing, data link protocol in which both processors are
finite state machines.
Protocol 3 appears in Figure 3. In this protocol each message is a pair (color; bit), where
1g. The local variables color and token color are ternary variables
while the variables counter bit; counter xor; carry; and new counter bit are binary. The binary
xor operation is denoted by \Phi. For a sequence of such
messages, N(s) denotes the integer whose binary representation is bit k ; bit
the least significant bit). A maximal sequence of consecutive messages of the same color sent
by the sender is called a block. For each block b, N(b) denotes the integer described above and
jbj denotes the number of messages in b. The first message in each block is viewed as a token.
To show that the protocol is self-stabilizing, we have to prove that eventually the link contains
exactly one message which is the first message in a block. This goal is achieved by making the
sequence of the colors of the blocks aperiodic.
The sender uses a local variable called token color, which denotes the color of the block it
is now sending. It continues to send messages of this color as long as the colors of the messages
it receives are different from token color. Once the sender receives a message whose color is
equal to token color (which eventually means that all messages on the link belong to the same
block), it: (a) possibly sends one last message of the current block, (b) changes the value of
token color, and (c) sends the first message of a new block, with this new color.
do forever
receive(color,counter bit)
token color then (* token arrives *)
(* new token *)
6 token color := (color
7 counter xor := 0
9 end
counter xor := counter xor \Phi counter bit
new counter bit := carry \Phi counter bit
carry := carry - counter bit
send (token color,new counter bit)
14 end

Figure

3: protocol 3
In Lemma 8 we show that in every execution the sender initiates infinitely many blocks.
be the sequence of blocks initiated by the sender, where the color of b i is
and the integer it represents is N(b i ), as defined above. The protocol is designed so that the
following properties are kept:
(p1) The sequence (color(b 1
(p2) For every large enough i, N(b and the bit field in the last message of b i is
(that is: N(b i const for some constant const, and the representation of N(b i ) by
b i has no leading zeroes, implying that jb
We will prove that (p1) above implies that eventually there is only one token in the system,
while (p2) guarantees that the size of the system is logarithmic in the number of steps. We now
show that the protocol indeed satisfies (p1) and (p2) above. For this, we describe the two rules
by which the sender computes the bits and the colors it sends. We need the following definition:
1. Denote by s k the sequence of messages whose colors are different from
are received by the sender while it sends the block b k , and by N(s k ) the integer
represented by s k . Note that s k consists of one or more complete blocks.
Rule 1: (rule for computing counter bits): The counter bit sent with each message is sent so
that for each k, N(b k ))eg. In other words:
the counter bits sent in block b k are obtained by adding 1 to the binary number represented
by the messages received while this block is sent.
Rule 2: (rule for computing token color): When receiving a message whose color is equal to
the value of token color, the new value of token color, which is the color of the next block,
b k+1 , is determined as follows: color(b k+1
Note that Rule 1 can be implemented by a binary adder which is set to zero at the initiation
of each new block, and Rule 2 can be implemented by a counter (mod 2). Thus, both rules are
easily implemented by a finite state machine.
4.3 Correctness and Complexity Proofs of Protocol 3
Lemma 8: In every fair execution, E, the sender initiates an infinite number of blocks.
Proof: The sender initiates a new block whenever it receives a message whose color is equal
to the current value of token color. In every atomic step in which the sender receives a message
whose color is not equal to token color, it sends a message, say M whose color is token color.
Since the link carries messages in FIFO order, the message M is eventually received by the
sender and it initiates a new block not later than upon receipt of M . The lemma follows.
A configuration in an execution is called a limit configuration if in the next step of the sender
a new token color is computed; that is, the color of the next arriving message is equal to the
present value of token color. Observe that at a limit configuration c, the link contains a finite
(possibly zero) number of complete blocks, and one possibly incomplete block at the tail of the
link (this block may be incomplete since upon receipt of the next message the sender may send
one more message in this block, by executing line 5 of the code). The first block has the same
color as the last (possibly incomplete) block. For an execution E, we denote by i k the index of
the k-th limit configuration in E. In other words, c i k
is the limit configuration just before b k is
initiated.
Next we prove that the number of blocks in consecutive limit configurations does not increase.
Lemma 9: Let ' k be the number of blocks in the limit configuration c i k (including the possibly
incomplete block). Then ' k - ' k+1 , with equality only if s k is a single block.
be the number of blocks in s k . In the sub-execution starting with c i k and
ending with c i k+1
one block is added to the link (namely, b k ), and m k blocks of s k are removed
from it. Therefore '
Next we show that the number of blocks in the limit configurations must eventually get down
to one. First we need a technical Lemma:
Lemma 10:
(a) The sequence xor is aperiodic.
(b) Let (a 1 ; a \Delta) be an eventually periodic sequence, and let b . Then the
sequence \Delta) is also eventually periodic.
(c) Let (a 1 ; a \Delta) be an eventually periodic sequence. Then for each the sequence
\Delta) is also eventually periodic.
Proof:
(a) Assume in contradiction that the sequence xor = eventually periodic.
Then there exist i and ', s.t. q be a non-negative
integer such that 2 q let d be an integer satisfying d - q
Consider the following cases:
1: By the definition of d it holds that xor(2 d
Thus,
Thus, there exist a and b such that: (1) a ? i and b ? i, (2) a
xor(b), a contradiction.
(b) This claim is trivial.
(c) Let j and ' be such that j. Then for every p ? 1 and
holds that a k = a k+'p . Thus, the sequence A(i; p) is eventually periodic with
period length - '.
Lemma 11: In every fair execution E there exists a suffix in which the number of blocks in
the limit configurations is always one.
Proof: By Lemma 9 this number never increases, and hence it eventually remains L for some
constant L ? 0 forever. We shall assume that L ? 1 and derive a contradiction.
Call a limit configuration c i k
ultimate if ' k , the number of blocks in c i k
, is L. If c i k
is
ultimate then ' and hence, by Lemma 9, s k is a single block, which must be b k\GammaL .
Thus, the first block that follows s k is b k\GammaL+1 . By the protocol, b k is terminated when the
sender receives a message whose color is equal to the color of b k . Therefore, we have that
the color of (the messages in) the block b k\GammaL+1 is equal to the color of the messages in b k ,
Hence the sequence
eventually periodic with period length
By the way color(b k+1 ) is computed, we have that for an ultimate configuration c i k , xor(N(b
eventually
periodic so is BXOR. We shall derive a contradiction by showing that the sequence BXOR is
aperiodic.
implies that in order to show that BXOR is aperiodic, it is
sufficient to show that for some positive i and p, the sequence BXOR(i;
\Delta) is aperiodic. For this, observe that for an ultimate
configuration c i k , it must hold that N(b k 1. Hence, for
any integer i we have that
Thus, BXOR(i;L) is a suffix of the
sequence xor, which is aperiodic by Lemma 10 (a). Hence, BXOR(i;L) is also aperiodic. This
yields the desired contradiction.
Lemma 11 and its proof imply that properties (p1) and (p2) hold: Property (p1) holds since
the proof of Lemma 11 shows that the sequence COLORS is aperiodic. Property (p2) is proved
as follows: Let E 0 be a suffix of E satisfying Lemma 11, and let c i k
be any limit configuration
in E 0 . Then, by Rule 1, N(b easily implies (p2).
We now show that the space complexity of protocol 3 indeed matches the lower bound of
the previous section. Since both the number of states of a processor and the number of distinct
messages in our protocol are constants, the size of a configuration is proportional to the number
of messages in it. Therefore to bound the size of a configuration from above it is enough to
bound the number of messages in it. In the next lemma we show that for each execution
\Delta) of the protocol, the size of the i-th configuration of E, c i , is O(log 2 (i)). Let
denotes the k-th limit configuration of E, and let b k be the corresponding block. We shall
prove that jb k
Lemma 12: For every large enough k, the number of messages in the limit configuration c i k
is dlog 2
Proof: By Lemma 11 there exists a suffix E 0 of E such that every limit configuration in
contains one block. Clearly, it is suffices to prove the Lemma for E 0 . As observed above,
property (p2) eventually holds for every limit configuration in E 0 . The lemma follows.
Corollary 13: The number of messages in c ' , the th configuration of E, is O(log 2 (')).
Proof: Let E 0 be a suffix of E as in Lemma 12, and assume that ' is large enough so that
c ' belongs to E 0 . Then the number of messages in c ' is equal to the number of messages in the
next limit configuration, c i k
, which is O(log 2 k). The proof is completed by the
observation that, since i j - j for all j, and since configuration c i precedes c ' in E, we have
that
4.4 Larger Systems
Now, we describe how to use our protocols in directed rings with more than two processors.
The processors of the ring are denoted by P are
receivers. Whenever a processor P message M from P sends M to
Similarly, whenever P n receives a message M from P sends M to P 1 . Thus, the ring
behaves like a virtual link from the sender, P 1 , to itself. It is not hard to see that the existence
of a single message on the entire ring prevents communication deadlocks, thus, we assume
that there is a time-out mechanism that guarantees this condition (this time-out mechanism is
invoked only once to recover from initial deadlock configuration). It can be proved, in a way
similar to previous proofs, that our protocols guarantee that eventually there is exactly one
token that encircles the ring from the sender to itself. Actually, our protocols can be used in
any connected system by hardwiring a directed ring that spans the entire system.
4.5 Construction of a Token Controller
In this subsection we define queue machines and token controllers and interpret our results in
these terms.
A queue machine Q is a finite state machine which is equipped with a queue, which initially
contains a non-empty word from \Sigma + for some (finite) alphabet \Sigma. In each step of its computation
Q performs the following: (a) reads and deletes a letter from the head of the queue, (b) adds zero
or more letters from \Sigma to the tail of the queue, and (c) moves to a new state. The computation
terminates when Q halts or when its queue becomes empty, which prevents Q from performing
any further steps.
The main difference between queue machines and various types of Turing Machine is that
the input alphabet and the work alphabet of a queue machine are identical. For this reason, a
queue machine cannot perform simple tasks like deciding the length of the input word, or even
deciding whether the input word contains a specific letter 2 .
We now define token controller, which is a special type of queue machine. Assume that the
alphabet \Sigma contains a specified subset - of token letters. A queue machine is a token controller
if, starting with a nonempty queue of arbitrary content, eventually the queue contains exactly
one occurrence of a letter from - forever.
A priori, it is not clear that a token controller exists. Observe that if a token controller exists,
then its queue never becomes empty (since once the queue is empty it remains so forever). More
importantly, a token controller (if exists) can never halt, since it cannot guarantee that upon
halting, the queue contains exactly one occurrence of a token letter. The last two observations
imply that a token controller can be viewed as a special case of a token-passing system, in which
\Sigma is the set of messages sent by the protocol, and - is the set of messages that carry the token.
We show below how to transform the sender from protocol 3 to a token controller.
Define the alphabet \Sigma to be a set of triplets (color; bit; t), where color and bit are as in
protocol 3, and t is either T - in case the message carries a token (i.e., it is the first message
of some block), or nil, in case it does not. The set - is defined as the set of all possible triplets
whose third component is T . The two anti-parallel FIFO links between the sender and the
receiver are considered as a single queue. Receiving a message is regarded as deleting a letter
from the head of the queue, while sending a message is regarded as appending a message to the
end of the queue.
Since protocol 3 guarantees that eventually exactly one message in every configuration is
carrying a token, the queue machine described above is a token controller. Moreover, our lower
bound results imply that this token-controller is optimal with respect to the rate in which the
size of the queue grows.
Stabilizing Simulation of Shared Memory
In this section we present a method for simulating self-stabilizing, shared-memory protocols by
self-stabilizing, message-driven protocols. The simulated protocols are assumed to be in the
A variant of queue machine which can use arbitrary work alphabet is in fact an oblivious Turing machine,
which is as powerful as a standard Turing machine
shared-memory model defined in [DIM-90]. In this model, communication between neighbors,
carried out using a two-way link. The link is implemented by two shared registers
which support read and write atomic operations. Processor P i reads from one register and
writes in the other while these functions are reversed for P j . In the implementing system, every
link is simulated by two directed links: one from P i to P j and the other from P j to P i . The
heart of the simulation is a self-stabilizing implementation of the read and write operations.
The proposed simulation implements these operations by using a self-stabilizing, token-passing
protocol. For any pair of neighbors, we run the protocol on the two links connecting
them. In order to implement our self-stabilizing, token-passing protocol we need to define for
each link which of the processors acts as the sender and which of the processors acts as the
receiver. We assume that the processors have distinct identifiers. Every message sent by each
of the processors carries the identifier of that processor. Eventually each processor knows the
identifier of all its neighbors. In each link, the processor with the larger identifier acts as the
sender while the other processor acts as the receiver. Since each pair of neighbors uses a different
instance of the protocol, a separate time-out mechanism is needed for every such pair. In other
words: A correct operation of the simulation requires that for any pair of neighbors there exists
at least a single message on one of the two links connecting the neighbors.
We now describe the simulation of some arbitrary link e, connecting P i and In the shared
memory model, e is implemented by a register R i;j in which P i writes and from which P j reads,
and by a register R j;i for which the roles are reversed. In the simulating protocol, processor P i
local variable called r i;j ( r j;i ), which keeps the values of R i;j (R j;i respectively).
Every token has an additional field called VALUE. Every time P i receives a token from P j ,
the current value of r i;j in the VALUE field of that token. A write operation of P i
into R i;j is simply implemented by locally writing into r i;j . A read operation of P i from R j;i is
implemented by the following steps:
1. receives a token from P j and then
2. P i receives another token from P j . The value read is the VALUE attached to the second
token.
The correctness of the simulation is proved by showing that for every execution E whose
initial configuration contains at least one message on each link, it is possible to linearize all
the simulated read and write operations executed in E so that eventually every simulated
read operation from R i;j returns the last value that was written to it. (i.e., that the protocol
simulates executions in the shared-memory model in which the registers are eventually atomic,
see [La-86]). Define the time of a simulated write operation to R i;j to be the time in which
the local write operation to r i;j is executed. Define the time of a simulated read operation of
P j from R i;j to be the time in which P i sends the value of its local variable r i;j attached to the
token that later reaches P j in step (2) of the simulated read. Once each link holds a single
token, all the operations to register r i;j are linearized, and every read operation from r i;j returns
the last value written to r i;j .

Acknowledgments

We thank Alan Fekete for helpful remarks.



--R

"Self-Stabilization of the Alternating-Bit Protocol"
"A Self-Stabilizing Token system"
"Stabilization and Pseudo stabilization"
"Uniform Self-Stabilizing Rings"
"A Note on Reliable Full-Duplex Transmission over Half-Duplex Links"
"Self-Stabilizing Rings without Demons"
"Self-Stabilizing Systems in Spite of Distributed Control"
"self-stabilizing systems in spite of distributed control (EWD391)"
"Self Stabilization of Dynamic Systems Assuming Only Read/Write Atomicity"
"Resource Bounds for Self Stabilization Message Driven Protocols"
"Uniform Dynamic Self-Stabilizing Leader Elec- tion"
"Token Survival"
"Stabilizing Communication Protocols"
"Token Management Schemes and Random Walks Yield Self Stabilizing Mutual Exclusion"
"Self-stabilizing Ring Orientation"
"Self-stabilizing extensions for message-passing systems"
"Self-stabilization (in spite of distributed control) in tree-structured systems"
"Time, Clocks, and the Ordering of Events in a Distributed System"
"Solved problems, unsolved problems, and non-problems in concurrency"
"On Interprocess Communication. Part I: Basic Formalism"
"Toward a Theory for Self-stabilizing Protocols,"

--TR

--CTR
Rodney R. Howell , Mikhail Nesterenko , Masaaki Mizuno, Finite-state self-stabilizing protocols in message-passing systems, Journal of Parallel and Distributed Computing, v.62 n.5, p.792-817, May 2002
Kleoni Ioannidou, Transformations of self-stabilizing algorithms, Journal of High Speed Networks, v.14 n.1, p.85-105, January 2005
Bertrand Ducourthial , Sbastien Tixeuil, Self-stabilization with path algebra, Theoretical Computer Science, v.293 n.1, p.219-236, 3 February
Paolo Boldi , Sebastiano Vigna, Universal dynamic synchronous self-stabilization, Distributed Computing, v.15 n.3, p.137-153, July 2002
message passing;self-stabilization;token passing;shared memory