Crash Resilient Communication in Dynamic Networks.
AbstractAn end-to-end data delivery protocol for dynamic communication networks is presented. The protocol uses bounded sequence numbers and can tolerate both link failures and (intermediate) processor crashes. Previous bounded end-to-end protocols could not tolerate crashes.We present a self-stabilizing version of the algorithm that can recover from crashes of the sender and the receiver as well as of intermediate processors. Starting with the network in an arbitrary state, the self-stabilizing version guarantees proper transmission of messages following a finite convergence period.
Introduction
A basic communication task in any network is end-to-end communication, that is,
delivery in finite time of data items generated at a designated sender processor,
to a designated receiver processor, without duplication, omission or reordering
of data items. End-to-end communication is easy to achieve in a reliable net-
work, where links never fail and processors do not crash. However, in existing
communication networks both link failures and processor crashes are possible.
A network that is subject to such failures is called a dynamic network.
One approach to constructing end-to-end protocols for dynamic networks is
to use unbounded sequence numbers to uniquely identify the data items sent
by the sender. Such an approach is used in the protocol of [AE86]. The use of
unbounded sequence numbers implies that both message size and the amount of
memory needed will grow with the number of data items transmitted. Therefore,
much effort has been spent in designing end-to-end protocols that use bounded
sequence numbers.
An important aspect of an end-to-end communication protocol is the type
of faults that it can tolerate. Clearly the end-to-end task is unsolvable when
there is a permanent sender-receiver link cut of the network such that all of its
This work was supported by NSF Presidential Young Investigator Award CCR-91-
58478 and funds from the Texas A&M University College of Engineering. Contact
author: Jennifer L. Welch, e-mail: welch@cs.tamu.edu, Phone: 409-845-5076, Fax:
links are down forever. Thus, some assumption on the behavior of faulty links is
necessary. Three common assumptions in the literature are:
infinitely frequent stability: Infinitely often the network topology stabilizes
for a period of time and there is no sender-receiver link cut in this stabilized
topology (e.g. [AAG87, AS88]).
infinitely frequent path stability: Infinitely often there is a period of time
during which links forming at least one path between the sender and the
receiver are operating (e.g. [AGH90, H92]).
eventual connectivity: The only assumption is that there is no permanent
sender-receiver link cut (e.g. [AG88, AMS89, AG91, AGR92]).
Almost all existing end-to-end protocols depend on having physical links
that are, or can be made to be, "well-behaved" in that the sequence of messages
delivered is always a prefix of the sequence sent, i.e., no messages are lost in
the middle. If processors do not crash, then this behavior can be ensured by
running the alternating bit protocol [BSW69]. But if processors can crash, then
this good behavior cannot be achieved without keeping information, including
the message currently being transmitted, in stable storage. 2 . (Even if only a
weaker behavior of the physical links is required, namely that once there are no
more crashes of the end points, the sequence delivered is a prefix of the sequence
sent, either stable storage is required [FLMS91] or a bound on the capacity of
the link must be known [ADW93].) Unfortunately, in existing dynamic networks
processors may repeatedly crash and recover with corrupted memory. Even if
the only problem for one of these end-to-end protocols caused by a crash is
that the message currently being transmitted is lost, the probability of the data
item being delivered could be exponentially small in the length of the path over
which the data item travels (assuming the probability of a processor not crashing
during the delivery of some data item is bounded by some constant).
We would like to have a protocol that is resilient to crashes of the intermediate
processors, i.e., those processors in the network other than the designated sender
and receiver, and does not rely on stable storage. We exclude the possibility of
the sender and receiver failing, since if they do, stable storage would be required
by the same argument alluded to above for a physical link. Obviously in actual
systems the sender and receiver could crash, but the recovery techniques to
be used in this case are application dependent and beyond the scope of this
paper. In the presence of processor crashes the previous definition of eventual
connectivity is not sufficient for the existence of a protocol, since a permanent
cut of any combination of crashed processors and crashed links could eliminate
the connection between the sender and the receiver. Thus, we make the weakest
assumption possible, namely that there exists at least one "viable" path between
the sender and the receiver, a path that contains no permanently faulty link and
2 The only known end-to-end protocol that can withstand processor crashes (without
stable storage) is the randomized protocol presented in [H92]. However, this protocol
has a bounded probability of failure and uses headers that are not strictly bounded.
no processor that is permanently crashed (for this path), i.e., at least one path
along which communication is possible.
A elegant approach to designing a communication protocol is to view the net-work
on which it will run as a black box that provides a message transfer service
in which messages can be lost, reordered and duplicated, but not corrupted. 3
However this approach has limitations: [WZ89] show that no bounded sequence
number protocol can tolerate reordering and duplication, while [AA+92] show
that although there is a bounded sequence number protocol that can tolerate
reordering and loss, any such protocol must have the property that the number
of messages needed to transmit a data item increases without bound.
These impossibility results hinge on the assumption that the black box net-work
can reorder messages arbitrarily. This assumption models the situation
when the user of the network does not know how the network layer protocols
(which implement the black box) route messages or even what the network topology
is. An alternative approach, which avoids arbitrary reordering, is to use
knowledge of the network topology and explicitly control the retransmissions on
the routes. A packet can indeed be lost while it is traveling over a (physical)
link. However, duplications are caused by protocols that retransmit packets under
certain circumstances; if no packet is retransmitted by a protocol, then no
duplication exists. Reordering is also a protocol property. If the protocol uses only
a single path from the sender to the receiver and a single path from the receiver
to the sender, the FIFO property in each direction is preserved by the network.
Thus our protocol is designed to work on top of the "bare" network, consisting
of nodes connected by FIFO non-duplicating links that can lose messages. Although
our protocol does retransmit and uses multiple paths, and thus messages
are duplicated, reordered, and lost, these activities are carefully coordinated.
In this paper, we present an end-to-end protocol for dynamic networks that
can tolerate crashes of nodes and failures of the links in the communication
network without requiring any stable storage or knowledge of the link capacities.
To the best of our knowledge our protocol is the first crash resilient end-to-end
protocol that uses only bounded sequence numbers. The space complexity of the
protocol, i.e., the maximum amount of space used by any processor's program,
is O(P 2 log P), where P is the number of simple paths in the network. The
message size is O(P log P) bits. The time complexity is O(L), where L is the
length of a viable path, and the message complexity is O(nP(1+L=T )), where n
is the number of processors in the system, and T is the retransmission parameter.
Roughly speaking the time and message complexity are measured only for runs in
which the time for a message to travel over a viable link is 1; this is comparable to
the complexity measures in [AGR92] (which assumes a reliable data link layer).
The number of possible paths P between two processors in the system is
theoretically exponential in jEj, the number of links in the system. This could
be a drawback for our protocol. However, most practical communication schemes
3 In practice, there is a non-zero probability of a message being corrupted, however
due to error detection schemes it is assumed that those messages are identified and
discarded.
are based on sending messages along a single route from source to destination
(see [H92] for a nice discussion of practical protocols). Thus our protocol is not
only of theoretical interest but could be used to improve existing protocols by
using a constant number of paths from the source to the destination; as long as
at least one of them is viable then the data items will be delivered. Moreover,
the delivery time during each time interval will be due to the fastest and most
reliable path during that period.
Another application of our protocol is to the case of parallel physical links
between two processors. Such application would provide an implementation of
a very reliable (non-parallel) link. In this situation, the number of paths would
obviously be extremely small.
2 The Bare Network
We model a communication network as a graph G(V; E), jV
where the nodes are processors and the edges are undirected communication
links. Each undirected link consists of two directed links, delivering messages
in opposite directions. Each communication link connects two processors. Two
processors that are connected by a link are called neighbors. The communication
over the links obeys the FIFO discipline, and no bound on the transmission delay
is known.
Each processor in the system is viewed as a state machine executing a pro-
gram. An execution of a program consists of a sequence of steps. Each step
consists of (1) one receive operation, during which zero or one message is re-
ceived, (2) internal computations, and (3) zero or more send operations. The
internal computation of the sender can include the input of data items, while
the internal computation of the receiver can include the output of data items.
We assume that the sender and receiver are not subject to crashes. Any
other processor is called an intermediate processor. Intermediate processors are
subject to crashes. Following a crash, a processor reenters its initial state and
it may continue executing. The crash of an intermediate processor could occur
in the middle of a step, modeled as a partial step, in which only a subset of the
messages that should have been sent are actually sent.
We model the link between processors P and Q as two FIFO queues, one
holding the messages in transit from P to Q and the other holding the messages
in transit from Q to P . Links are subject to failures; a link failure causes one or
more messages to be eliminated from the component queues.
A configuration of the system is the set of states of the processors and the
contents of the messages in the links. A run is a sequence of configurations
is an initial configuration (each processor is in its initial
state and all the links are empty), and for each i, in going from c i to c i+1 , one
of the following holds.
- Some processor P takes the next step (possibly a partial step) according to
its program: the message received, if any, is at the head of the relevant queue
in c i and is dequeued in c i+1 , P changes state accordingly (enters its initial
state if this is a partial step), and the messages sent are enqueued in c i+1 .
Nothing else changes.
- A link fails: the only change is that one or more of the messages that are in
the queues of a particular link in c i are no longer there in c i+1 .
We are only going to be concerned with runs that satisfy certain basic con-
ditions, as given now. A run is admissible if
- the sender takes an infinite number of steps,
- the receiver takes an infinite number of steps,
there exists at least one viable path between the sender and the receiver.
It remains to define a viable path. Assume an infinite run satisfying the first
two admissibility conditions. An intermediate processor P is viable provided
whenever P receives a message m infinitely often, it succeeds in sending m infinitely
often 4 . A link is viable provided whenever an infinite number of messages
is sent on that link, then an infinite number of messages is received by the receiving
processor. We assume this is true in both directions of the link. (Note
that our definition of a viable link implies that the receiving processor must take
an infinite number of steps or partial steps.) A path is viable if every intermediate
processor and every link on the path is viable. Our definition of viability is
weaker than that in [AGR92] since the latter does not consider processor crashes.
If there is no viable path in the network between the sender and receiver, then
every path between them either has a nonviable processor or a nonviable link,
and thus there is a sender-receiver cut.
Note that there are no restrictions concerning relative ordering of processor
steps or the number of steps between the sending of a message and its receipt.
Thus we have an asynchronous system.
We assume that whatever entity supplies the data items to the sender provides
one when and only when the sender requests one.
3 Problem Statement
An algorithm solves the end-to-end communication problem if in every admissible
run the following properties are satisfied:
Safety: In any prefix of the run, the sequence of data items output by the
receiver is a prefix of the sequence of data items input by the sender.
4 This definition restricts the behavior of the intermediate processor in ways that are
not compatible with some systems, such as those that are supposed to strip off part
of the header or send m on more than one link. A more general definition of a viable
processor would be: upon receiving a message m infinitely often P executes infinitely
often a (complete) step that starts with receiving m. However, for our protocol the
weaker condition of infinite execution of a partial step that succeeds in forwarding
m is sufficient.
Liveness: The receiver does an infinite number of outputs.
We are interested in these complexity measures:
- space: the maximum amount of space required by any node's program,
message size: the maximum number of bits in any message.
message number: the maximum number of messages sent to transfer a data
item, in any ideal run 5 , between two successive inputs.
- time: the maximum length of time between two successive inputs, in any
ideal run.
The time and message complexity are only discussed for ideal runs, which we
now define. Processors send messages either in response to receiving messages or
based on some timeout parameter (in order to guard against message loss). We
say a message is retransmitted if it sent based on a timeout expiring; otherwise
it is new. The time between retransmissions is only due to the speed of the
processor. Naturally, the frequency of retransmission influences the total time
and number of messages needed to deliver a data item. At each processor there
is a procedure responsible for sending messages. The Send procedure keeps track
of the number of steps, k, that the processor has taken in order to estimate when
real time has elapsed, where T is some system-dependent value (that depends
on, say, the probability of loss and the distribution of message delays on links).
We want this estimate based on k to be a good one; this is the rationale for
condition 1 of the definition of ideal. The goal of retransmitting every T units of
time is to ensure that a message will be delivered within one time unit, assuming
the link is viable. This is the rationale for condition 2 of the definition of ideal.
An admissible run is ideal if
1. Whenever a processor has taken k steps, at least T real time has elapsed.
2. If processor P receives message m at time t which is addressed to travel
through a viable path Path, then its neighbor Q on Path, receives m at time
4 The Protocol
The main problem for our protocol is how to keep track of the set of sequence
numbers that label messages in transit in the network. The key observation is
that the FIFO property of the links can be used to ensure FIFO delivery in
every path from the sender to the receiver (and vice versa). If each message is
sent with the description of the path it should take, then messages that are sent
through the same path obey the FIFO order. Note that two different paths might
have some shared links. Thus, the set of messages in transit in some link could
be related to more than one path. The order of two messages within one link
does not necessarily imply anything about the relative order of their sending or
receipt, unless the two messages have the same path.
5 Defined below.
The sender and receiver use a set of 2P sequence numbers (shortly it is
explained why this number is sufficient). Both the sender and receiver remember
the sequence number of the most recent message sent and received on each path.
The sender uses the arrays Sent SR and RecvRS , with an entry for each possible
path. Whenever the sender sends a message with sequence number SeqNum on
path Path, the sender assigns Sent SR [Path]:=SeqNum. Similarly, whenever the
sender receives a message with sequence number SeqNum the sender assigns
RecvRS [Path]:=SeqNum. The receiver uses the arrays Sent RS and Recv SR for
its bookkeeping.
The sender uses only clean paths to send a new data item with a new sequence
number. A path, Path, from the sender to the receiver is considered clean when
Sent SR [Path]=Recv SR [Path]. That is to say, the sequence number that is currently
being repeatedly sent through that path has arrived at its destination.
The use of clean paths ensures that the set of sequence numbers on the messages
in any particular sender-receiver path, Path, is contained in (Sent SR [Path]
[Path]). Moreover, in case there are two sequence numbers in some
path, Path, then the messages are ordered in that path such that the ones with
sequence Sent SR [Path] are closer to the sender than any message with sequence
number Recv SR [Path].
Unfortunately, the array Recv SR is updated by the receiver and thus the value
of Recv SR [Path] is not known to the sender. Consequently, the receiver sends the
array Recv SR to the sender. However, the sender has to be able to distinguish
old values of Recv SR from more current values. This is done by implementing
independent alternating bit protocols [BSW69], one for each entire path from
S to R (not for individual physical links). For a given path, the protocol keeps
track of the number of alternating bit tokens (i.e., the number of times the
sender receives an acknowledgement for the same bit it is currently trying to
send) that have arrived at the sender over that path since the sender input
the last data item. The sender uses the information concerning Recv SR that
arrives through some path only if it comes after the second token has arrived
through the same path since the last data item was input. This rule ensures that
the information received reflects the current state of the path. Whenever such
information concerning Recv SR arrives, the sender updates its view of Recv SR
in an array called VRecv SR . The sender uses the information in Sent SR and
VRecv SR to determine whether a sender-receiver path is clean or not. Similarly,
the receiver uses Sent RS and VRecvRS to determine whether a receiver-sender
path is clean or not.
We view a run of the protocol as a sequence of alternating stings. At the
beginning the sender uses sequence number 1 to sting the receiver with the
first data item. The sender repeatedly sends a message with sequence number
1 through all possible paths. Eventually such a message arrives at the receiver,
which uses sequence number 1 to sting the Sender with an acknowledgment. At
the same time the receiver sends the next sequence number, called the sting-tag,
that will be used by the sender to sting the receiver with the second data item.
The receiver chooses this sequence number to be the minimal sequence number
that does not appear either in Recv SR or in VSent SR ; thus a sequence number set
of size 2P+1 is big enough. In this case, both Recv SR and VSent SR include only
the sequence number 1, and thus the receiver chooses 2 to be the next sequence
number to be used by the sender to sting the receiver. The sender eventually
is stung with an acknowledgment from the receiver when the first message with
sequence number 1 arrives at the sender. Now the sender calculates the next
sting-tag that will be used to sting itself (with an acknowledgment) by similar
arguments as above; this sequence number will be 2.
When the sender is ready to send the i'th data item (after getting the acknowledgment
for the 1'st data item), the sequence numbers in the entries
of Sent SR could all be distinct. Roughly speaking, each entry contains the last
sequence number that was sent and has not yet cleaned its path (i.e., arrived
at the other side). However, since there is at least one viable path Path, this
path is eventually cleaned (by the sequence number Sent SR [Path]). The sender
eventually gets two tokens through this path and updates its VRecv SR so that
VRecv SR [Path]=Sent SR [Path]. Then the sender uses Path for sending the i'th
data item. The i'th data item is sent with SeqNum SR that was chosen by the
receiver during the 1'st acknowledgment.
Until the i'th acknowledgment arrives, the sender continues to update the
clean/dirty status of the sender-receiver paths by the use of the information
concerning Recv SR that arrives with the messages from the receiver. When a
sender-receiver path changes status to clean before the i'th acknowledgment
arrives, the sender uses this path also to send the i'th data item with SeqNum SR .
The receiver uses a similar scheme to deliver the i'th acknowledgment.
Unlike most other end-to-end protocols, ours is not based on flooding. In-
stead, each message sent has its entire path specified by S.
The formal description of the protocol appears in Figures 2, 3, and 4. The
variables used by the sender and their initial values appear in Figure 1. The
variables of the receiver are similar except the order of the subscripts S and
R is reversed. When no confusion is possible we use the name of an array, e.g.
Sent SR , to represent the set of sequence numbers yielded from its entries.
4.1 Correctness Proof
Throughout this section we assume an admissible run
the step that causes the transition from c i\Gamma1 to c i step i. We denote by Var(i)
the value of variable Var in configuration c i .
The correctness proof is by induction on the number of stings in R. The
sender is stung whenever the sender executes line 02. The execution of line 02
occurs either during the first atomic step, which ends with line 10, or during an
atomic step that starts with the message receive in line 11 and ends with the
message send in line 10. The receiver is stung whenever the sender executes line
or line 24. The execution of line 02 occurs only during the first atomic step,
which ends with line 12. The execution of line 24 occurs only during an atomic
step that starts with line 13 and ends in line 12.
Variable Name Type Initial Value
set of paths ; empty
arbitrary
Fig. 1. The Variables of the Sender
do forever
repeat
06 8 Path
07 if Path 2 CleanPathsSR or
13 RecvRS[Msg.Path] := Msg.SeqNum
14 if
19 VRecvSR[Path] := Msg.RecvSR[Path]
22 VSentRS := Msg.SentRS
od
Fig. 2. The Program of the Sender
do forever
if Msg 6= nil then
04 Pending[Msg.Path]:=Msg
07 od
Fig. 3. The Program of an Intermediate Processor
RecvSR[Msg.Path] := Msg.SeqNum
04 do forever
07 repeat
else Send(Path,nil,SentRS [Path],BitRS [Path],nil, SentRS ,RecvSR)
14 if Msg 6= nil then
22
26 SeqNumRS := Msg.StingTag
28 od
Fig. 4. The Program of the Receiver
Each copy of the alternating bit protocol is implemented for a distinct undirected
path. Consider a single such copy of the alternating bit protocol for undirected
path Path. The token of the alternating bit protocol arrives at the sender
when the sender receives a message with the same bit as the sender is currently
sending. The token arrives at the receiver when the receiver receives a message
with the opposite bit to the last bit the receiver sent. Given a configuration
we denote for a path Path the sequence of messages from the sender to the receiver
(i - 0 messages) and the sequence of messages from the receiver to the
sender (j - 0 messages) together with the current values of Bit SR [P ath] and
Bit RS [P ath] in the following
RS ,
It is well known (e.g. [BSW69]) that if messages are only lost or duplicated
then in any configuration of the alternating bit protocol if BitSeq contains more
than a single value (either 0 or 1) then there exists a single border in BitSeq
between those values. Furthermore, if there is no such border then the sender
eventually changes the value of Bit SR so that a border is produced. If there is
a border and we look at the sequence BitSeq in successive configurations of the
run, then this border "travels" towards the end of BitSeq.
The important property of the alternating bit, used by the protocol, is that
between any two successive token arrivals at the sender there is one token arrival
at the receiver. This ensures the property in the following lemma.
Lemma 1. Suppose i and j are such that a message Msg arrives at the sender
over path P in step j ? i with the token for P , and this is not the first token for
P that the sender has received since step i. Then there exists k,
that (k). The analogous
property is true for the receiver as well.
The next lemma states that between consecutive stings at the sender (resp.,
receiver), the set of values in fSeqNum SRg[ Sent SR (resp., fSeqNumRSg[ Sent RS )
either remains the same or decreases. It can be seen to be true by inspecting the
code, since the sender only changes an entry in Sent SR by sending a message
with sequence number equal to SeqNum SR .
Lemma 2. For any i such that step i is not a sting at the sender, fSeqNum SR (i)g
1). The analogous property is
true for the receiver as well.
Now we prove the correctness of the protocol.
Theorem 3. The above protocol is a crash resilient end-to-end protocol.
Proof. Both the safety and liveness properties are proved by induction on the
number of stings in R. We will prove the following.
For all
1. There are i stings.
2. If i is even then
a. The i-th sting occurs at the receiver and causes the i=2-th data item to
be output; the data of this output is equal to the data of the previous
input.
b. In every configuration between the (i \Gamma 1)-st and i-th stings, if message
Msg is in transit from the sender to the receiver and
Sting SR , then Msg.Sent SR ' Sent SR .
3. If i is odd then
a. The i-th sting occurs at the sender and causes the 1)-st data
item to be input.
b. If i ? 1 then in every configuration between the (i \Gamma 1)-st and i-th
stings, if message Msg is in transit from the receiver to the sender and
Sting RS , then Msg.SentRS ' Sent RS .
4. In any configuration up to the i-th sting, for every sender-receiver path P ,
the sequence of sequence numbers in the messages in transit along P , in
order starting with those closest to the sender, has the form x j y k for some
5. In any configuration up to the i-th sting, for every receiver-sender path P ,
the sequence of sequence numbers in the messages in transit along P , in
order starting with those closest to the receiver, has the form x j y k for some
We now prove this statement.
Basis: 1). Obvious from the code or initialization, or else vacuously true.
Induction: Assume for all j - i and show for i + 1. We'll show it for i odd
(the case for i even is similar and left to the reader). Then even. For
be the index of the step when the i-th sting in R occurs (if it exists).
To show 4: Consider any step t of the sender after step t i . Assume the statement
is true in all preceding configurations. We'll show it's true in configuration
t. Pick any path P . If the message sent on P during step t has the same sequence
number as in Sent SR [P ](t \Gamma 1), then clearly 4 is true.
Suppose the message sent on P has a different sequence number. Then P is
in CleanPaths SR (t) and Sent SR [P 1). Let S equal this
value of Sent SR [P ]. Since P is in CleanPaths SR , Sent SR [P
the code, this is the first time the sender has changed Sent SR [P ] since step t i .
Now look at the step between steps t i and t when VRecv SR [P ] was updated,
causing P to be put in CleanPaths SR . This was when the second token for P was
received since t i . By Lemma 1, this information reflects the value of Recv SR [P ] at
the receiver in some configuration t t, the inductive hypothesis
holds and all the messages in path P have the same sequence number, namely
S. As long as that is the only sequence number in P , Recv SR [P ] will continue to
be S. Thus in configuration
on P have sequence number S. So assertion 4 holds in configuration t.
To show 5: Similar to 4.
To show 2a: We must show that the sender is never stung after step t i as
long as the receiver is not stung. I.e., we must show that every message received
by the sender after step t i has sequence number not equal to Sting RS (t i ).
(Note that Sting RS is only changed when the sender is stung.) S is chosen to be
not in VSentRS (t i ) and not in RecvRS (t i ). Note that when the i-th sting arrives,
the sender sets VSentRS according to the information in the sting message M .
By the inductive hypothesis (3b), since M is in transit just before the sting,
M.SentRS is a superset of Sent RS
of Sent RS By the inductive hypothesis (5) any message in
transit in configuration t sequence number that is in either Sent RS
though RecvRS is changed for M 's path during the
sting, any message on that path following M has a sequence number that is
already included in Sent RS or has the same sequence number as M and
thus is included in RecvRS (t i ). So no message that is in transit in configuration
sting the sender.
Now we must show that no message that is sent by the receiver after step t i
can sting the sender. This follows from Lemma 2 and assertion 5, just proved.
So the (i 1)-st sting, if it occurs, occurs at the receiver. By the inductive
hypothesis (2a) for would be the (i output.
It is straightforward to check that the data is correct.
To show 2b: Immediately before the i-th sting, no message in transit from the
sender to the receiver has Sting because when the receiver
chose S as its next sting-tag back at sting i \Gamma 1, no message with SeqNum S was
in transit from the sender to the receiver.
Any message sent after sting i with SeqNum S has the current value of
Sent SR attached to it and by Lemma 2, the current set of elements in Sent SR
can only shrink relative to what was sent in the message.
To show 3: Vacuous since
To show 1: We must show that eventually the receiver is stung after t i . I.e.,
the receiver receives a message with sequence number equal to Sting SR . Suppose
this is not true. First, note that Sting SR is only changed when the receiver is
stung. After t i , the sender gets at least two tokens over a viable path P , then
puts P in CleanPaths SR , and sends the current message on P (by Lemma 1).
This current message has Sting SR . Eventually a copy of this message
will get through to the receiver, a contradiction.
The message length is O(P log P) since each message consists of a constant
number of components, the largest of which are the Sent and Recv arrays, each
of which consists of P entries of size log P (assuming the data items are no bigger
than this). The space complexity, due to the intermediate processors' storing a
message for each path, is O(P 2 log P).
Recall that the time and message complexity are defined for ideal runs. First
we explain in more detail when messages are retransmitted by the Send proce-
dure. The Send procedure keeps track, in Pending, of the most recent message
that it has sent for each path. Whenever the Send procedure is executed, it does
the following. First, consider the message that is the input to the procedure.
The message is fresh if the last message sent on that path, which is stored in
the Pending array, differs from this one in a component other than the Sent and
Recv arrays. The message is stored in Pending (actually this has already been
done in the intermediate nodes, but needs to be done here for the sender and
receiver). If the message is fresh, then it is immediately sent onwards on its path.
Otherwise, it is only sent if at least k steps have elapsed since it was last sent.
(This can be determined by counting steps modulo k.)
Consider viable path P of length LP and what can happen in between the
input of two successive data items. In the worst case, the path needs to be
cleaned, costing O(LP ) new messages and O(LP ) time; then the sender has
to receive two alternating bit tokens, costing O(LP ) new messages and O(LP )
time; and finally the new sting-tag must sting the receiver, costing O(LP ) new
messages and O(LP ) time. A similar analysis holds for the acknowledgment to
come back to the sender.
Thus the time complexity is O(L), where L is the length of the shortest viable
path.
We now discuss the message complexity. The number of retransmitted messages
sent between two successive data item inputs is O(nPL=T ). (Recall that
T is the retransmission parameter.) The reason is that during the O(L) time
between the inputs, each of the n processors retransmits for each of the P paths
O(L=T times. Now we consider the new messages. For each path P with length
LP , the discussion above shows that O(LP ) new messages are used. Since LP
is at most n and there are P paths, the number of new messages is O(nP).
Thus the message complexity is O(nP (Note that some cost due to
retransmissions is implicitly, but not explicitly, there for protocols that assume
a reliable data link layer.)
Concluding Remarks
We have presented a crash resilient end-to-end protocol. The protocol ensures
reliable data transfer (even in the present of processor' crashes) as long as there
is at least one viable path between the sender and the receiver.
Although we bypassed the data-link layer, our protocol will still work if the
links are running a data-link protocol, even in the presence of crashes. A crash
can affect the correct functioning of a data-link protocol in one of two ways: either
a message is lost, which the link could do even without the data-link protocol, or
a message is duplicated. However, this duplication is tolerable by our protocol,
because it could have happened at the same point with our intermediate node
protocol as well - the duplicate immediately follows what it is a duplicate of,
and is not inserted later in some malicious way.
Our protocol can be easily modified to work in the case that viability in one
direction does not imply viability in the other direction. Let P SR be the number
of paths from the sender to the receiver and PRS be the number of paths from
the receiver to the sender. One possibility is to virtually implement P SR \Theta PRS
alternating bit protocols, one for each possible combination of sender-receiver
path with receiver-sender path. Since there is at least one combination that
is viable in both directions, current information about the Recv SR array will
reach the sender and current information about the RecvRS array will reach the
receiver.
Several optimizations are possible. One is to update VRecv when a sting
arrives, in addition to when more than one token has arrived. This change will
cause paths to be placed in CleanPaths earlier. Another possible optimization
concerns reducing the message size by only sending array elements that have
changed since last time. A third optimization would be for every node to periodically
send one large message to each neighbor, containing all the individual
messages for paths that go through that neighbor, instead of sending the messages
separately and immediately. This change would decrease the total number
of messages (but would increase the message length and time). However, for
simplicity of presentation we have not incorporated such optimizations.
Our protocol could also be made self-stabilizing; some details on the self-stabilizing
version appear in [DW93].

Acknowledgment

We thank Reuven Cohen and Amir Herzberg for helpful
discussions. Amir also gave us useful comments on a written draft.



--R

Reliable Communication Over Unreliable Channels.
Applying Static Network Protocols to Dynamic Networks.
Memory Requirements for Connection Management.
Reliable Broadcast Protocols in Unreliable Net- works

Bootstrap Network Resynchronization: An Efficient Technique for End-to-End Communication
A Quantitative Approach to Dynamic Networks.
The Slide Mechanism with Applications in Dynamic Networks.
Polynomial End to End Com- munication
Dynamic Networks are as Fast as Static Networks.
A Note on Reliable Full-Duplex Transmission over Half-Duplex Links
Crash Resilient Communication in Dynamic Networks
Resynch Procedures and a Fail-Safe Network Protocol
The Impossibility of Implementing Reliable Communication in the Face of Crashes

Tight Bounds for the Sequence Transmission Problem.
--TR

--CTR
Micah Adler , Faith Fich, The complexity of end-to-end communication in memoryless networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.239-248, May 04-06, 1999, Atlanta, Georgia, United States
Pierre Fraigniaud , Cyril Gavoille, Header-size lower bounds for end-to-end communication in memoryless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1630-1638, 14 July 2006
Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September
dynamic networks;communication networks;self-stabilization;crash failures;end-to-end protocols