Optimal Elections in Faulty Loop Networks and Applications.
AbstractLoop networks (or Hamiltonian circulant graphs) are a popular class of fault-tolerant network topologies which include rings and complete graphs. For this class, the fundamental problem of Leader Election has been extensively studied, assuming either a fault-free system or an upper-bound on the number of link failures. We consider loop networks where an arbitrary number of links have failed and a processor can only detect the status of its incident links. We show that a Leader Election protocol in a faulty loop network requires only O(n log n) messages in the worst-case, where n is the number of processors. Moreover, we show that this is optimal. The proposed algorithm also detects network partitions. We also show that it provides an optimal solution for arbitrary nonfaulty networks with sense of direction.
Introduction
1.1 Loop Networks
A common technique to improve reliability of ring networks is to introduce link redun-
dancy; that is, to have each node connected to two or more additional nodes in the
network. With alternate paths between nodes, the network can sustain several nodes and
links failures. Several ring networks, suggested in [3, 8, 27, 34, 40] are based on this prin-
ciples. The overall topological structure of these redundant rings is always highly regular;
in particular, the set of ring edges (regular) and additional edges (bypass) form a Loop
Network (since they have at least one hamiltonian cycle).

Figure

1: #2, 4# Loop Network (a) with Faulty Links (b)
Loop Networks are particular cases of Circulant Graph. Because of an uncoordinated
literature, numerous terms have been used to name this topology depending on the model;
Circulant Graph, Chordal Ring, or Distributed Loop Computer Networks are the more
common. A detailed survey of these topologies is presented in [5]. For sake of simplicity,
we will use the term loop network in the remaining of this paper.
A loop network C n #d 1 , d 2 , ., d k # of size n and k-chord structure #d 1 , d 2 , ., d k # is a
ring R n of n processors {p 0 , each processor is also directly connected
to the processors at distance d i and n - d i by additional incident chords. The link
connecting two nodes is labeled by the distance which separates these two nodes on the
ring, i.e., following the order of the nodes on the ring: the node p i is connected to the
node p i+d j mod n
through its link labeled d j (as shown in Figure 1(a)). In particular, if a
link, between two processors p and q, is labeled by distance d at processor p, this link is
labeled by n - d at the other incident processor q, where n is the number of processors.
Note that both rings and complete graphs are circulant graphs, denoted as C n # and
respectively. It is worth pointing out that some designs for redundant
meshes and redundant hypercubes are also circulant graphs, [7].
The distinction between regular and bypass links is purely a functional one. Typically,
the bypass links are used strictly for reconfiguration purposes when faults are detected;
in the absence of faults, only regular links are used. Special classes of loop networks have
been widely investigated to analyze their fault-tolerant properties [3, 7, 8, 9, 27, 33] and
solutions have been proposed for reconfiguration after links and/or node failures [30, 39].
In some applications (e.g., distributed systems), all the links (or chords) of a circulant
graph are always used to improve the performance of a computation.
1.2 Election
In distributed systems, one of the fundamental control problem is the Leader Election
[29]. Informally, election is the problem of moving the system from an initial situation
where the nodes are in the same computational state, to a final situation where exactly
one node is in a distinguished computational state (called leader) and all others are in the
same state (called defeated). The election process may be independently started by any
subset of the processors. The election problem occurs, for instance, in token-passing when
the token is lost or the owner has failed; in such a case, the remaining processors elect a
leader to issue a new token. Several other problems encountered in distributed systems
can be solved by election; for example: crash recovery (a new server should be found
to continue the service when the previous server has crashed), mutual exclusion (where
values for election can be defined as the last time the process entered the critical section),
group server (where the choice of a server for an incoming request is made through an
election among all the available servers managing a replicated resource), etc.
Following failures, the network might be partitioned into several disconnected components
(as shown in Figure 1(b)). With respect to the election process, a component will
be called active if at least one processor in that component independently starts the election
process. A leader election protocol must determine a unique element in each active
component; such distinguished elements can then determine any additional information
(e.g., size of component, etc.) which is needed for the particular application. The nature
of such applications is irrelevant to the election process.
It is assumed that every processor p i has a distinct id i chosen from some infinite totally
ordered set ID; each processor is only aware of its own identity (in particular, it does not
know the identities of its neighbours). The processors all perform the same distributed
algorithm. A distributed algorithm (or protocol) is a program that contains three types of
executable statements: local computations, message send and message receive statements.
We assume that the messages on each arc arrive with no error, in a unbounded but finite
delay and in a FIFO order. The complexity measure is the maximum number of messages
sent during any possible execution.
1.3 Election in a Faulty Loop Network
The Leader Election problem in loop networks has been extensively studied assuming that
there are no failures in the systems [4, 18, 23, 24, 32]. The problem becomes rather more
di#cult if there are failures in the system. In asynchronous systems, in particular, the
election problem is unsolvable (i.e., no deterministic solution protocol exists) if failures
are undetectable and can occur at any time; this impossibility result holds even if just
one processor may fail (in a fail-stop mode) and follows from the result of [10].
The research has thus focused on studying the problem in more restricted environments

. (r1) failures are detectable,
# Faults (r3) (r1) (r2)
Graph Links Nodes Detectability Occurrence Termination
Arbitrary Loop Network
Complete
Complete
Complete (r5) < N/2 per node 0 No intermittent Possible [2, 38]
Ring
Arbitrary Loop Network unbounded unbounded Yes Prior Possible (this paper)

Table

1: Impossibility versus Possibility Results (k and t are constants bounding the
number of Fail-Stop Faults).
. (r2) failure occurs prior to the execution of the election protocol,
. (r3) the number of failures is bounded by some constant,
. (r4) failures are fail-stop,
. (r5) every processor is directly connected to every processor.
All the existing results for Election in faulty loop networks have been developed under
assumptions (r2), (r3), (r4) and further assuming that the network is either a complete
graph (r5) [1, 16, 28, 31, 37] or a ring [14, 41, 42] (see table 1). So far, without detectability,
algorithms breaking free of the bounded number of failures assumption (r3) generate an
expensive communication complexity (O(n 2 ) messages of O(n) bits, [19]).
In this paper, we consider the Election Problem in asynchronous arbitrary loop networks
where an arbitrary number of links has failed and a processor can only detect the
status of its incident links. That is, we make assumptions (r2) and (r4), and a relaxed
version of assumption (r1). Thus, unlike all previous investigations, we do not restrict to
complete graphs; we do not make any a priori restriction on the number of failures; we
do however assume that a processor can detect the failure of its incidents links. Note that
this assumption, the detectability assumption (r1), is required to cope with an unbounded
number of faulty components (see table 1). We prove that, under these assumptions, a
Leader Election protocol in a faulty loop network requires only O(n log n) messages in
the worst-case, where n is the number of processors. Moreover, we show that this is
optimal. In case the failures have partitioned the network, the algorithm will detect it
and a distinctive element will be determined in each active component; depending on the
application, these distinctive elements can thus take the appropriate actions.
Both processors and links may fail. In the following, we will assume that if a processor
fails all its incident links fail. Thus, without any loss of generality, we can just consider
link failures. We emphasize the fact that both regular and bypass links can fail (as shown
in

Figure

1(b)). A processor can only detect the failure of its incident links. Knowledge
that a link is faulty can be either o# line or on line. In the o# line case, the hardware
subsystem provides directly such a knowledge to the processors; thus, this information is
a priori respect to the execution of the protocol. In the on line case, this knowledge can
only be acquired upon an attempt to transmit on a link; if the link is operational, the
message will be transmitted, otherwise an error signal will be issued by the system (see

Figure

2).
From a computational point of view, the on line case is more di#cult than the o# line
one. In particular, to transform it into a priori knowledge case (e.g., by a pre-processing
phase where each active processor tests its incident links) would cost an additional m
messages where is the number of non-faulty links. Thus, our O(n log n) so-
lution, for the case where faults are only detected upon transmission attempt, is all the
more important since fault-detection is performed only on these links which are used by
the computation. Furthermore, this solution can obviously be applied with the same
complexity to the case where there is a priori knowledge on the faulty links. Thus, in
following, we will only concentrate on the more di#cult case.
The algorithm presented here combines known techniques for election in non-faulty
networks ([13, 17, 21]) and original routing paradigms based on structural information [12]
in order to avoid the faulty components. The algorithm uses asynchronous promotion
steps to merge rooted spanning trees.
Election Algorithm
We present an Election algorithm in loop network, where an arbitrary number of links
have failed and where failure of a link is detectable only if an incident node attempts to
transmit on it. The full algorithm is given in the Appendix (see also [26]). Any node can
independently and spontaneously start the election process (we will model this by having
such a node receive a WAKEUP message). If the network is not partitioned, the algorithm
will detect it and will elect a leader. In case the failures have partitioned the network, a
distinctive element will be determined in each active component and will detect that a
partition has occurred; depending on the application, these distinctive elements can thus
take the appropriate actions. We will now describe the algorithm as executed in each
active component.
2.1 Description
In each active component, the algorithm builds a Rooted Spanning Tree or Kingdom by
repeatedly combining smaller spanning trees; the final root of the spanning tree is the
distinctive element of that component. In the following, we describe the algorithm as
executed in one component.
The algorithm proceeds in phases and rounds. Initially, each node is a king, and does
not know which of its links have crashed. At the end, all nodes are citizen except one
which is still a king. During each intermediate phase of the algorithm, each king tries to
expand its kingdom (a rooted directed tree) by attacking another kingdom. The attack
is carried out by a particular node: the warrior.
Each kingdom is a tree with two distinguished nodes: the king and the warrior. Each
king is assigned a level, initialized at zero. Each node p stores the identity king p and the
level level p of its king, as well as the label of the outgoing chord to its king and to its war-
rior. If a node is attacked, it stores the label of the incoming chord from which the attack
came. In the algorithm, each warrior p maintains a local view List p of all the others processors
with the indication of which of them belong to the kingdom. An attack message is
a request message defined by a request status ReqStatus = (reqking, reqlevel, reqList)
which contains such a local view reqList.
Informally, the attack is carried out only by a warrior; the warrior will select randomly
an outgoing link which leads to another kingdom (one connected to a processor which does
not belong to its kingdom). It then attempts to transmit a REQUEST message on that
link. If the link is faulty, a failure detection signal will notify the warrior of such a situation
and the appropriate action (see below) will be taken; otherwise, the REQUEST message
will carry the attack to the other kingdom, as shown in Figure 2.
Failure
ALGORITHM
SYSTEM
Attempt
Request
TRANSMISSION

Figure

2: Local Failure Detection
The attacks by a kingdom follow a Depth First Search strategy. A state S r for
each chord is defined to specify if the chord is unused (initially), branched (is part of the
spanning tree) or failed (determined after an attempt of transmission). For each branched
chord a substate SubS r is introduced to specify if the chord is closed (is faulty or does
not lead to another kingdom), or still opened (the incident node has not been completely
explored and thus can lead to nodes which have not been reached yet). Initially, all non-faulty
chords are opened. It is used to control the backtracking by closing a subtree whose
visit has been completed. If a warrior j cannot reach any node outside the kingdom
(this is locally determined by the state of its incident links and the local view List j ),
then the state of warrior, together with List j , is backtracked to its parent and the chord
between them became closed. This strategy has the main advantage to limit the amount
of backtracking after a combination compared to a Breadth First Search strategy. A
state transition diagram of a chord is shown in Figure 3(a). Each node saves the label
{W out , W in , K out } of the incident chord leading to warrior p , the warrior attacking p, and
king p respectively.
Define the status p of node p as (level p , king p , List p ). Following a lexicographic total
order, we say that status p > status j i#:
- either (a) level p > level j
- or (b) level king p > king j .
Our algorithm obeys two main rules:
Promotion Rule. A warrior p can only successfully attack a kingdom with status
less than its own. Let the attack by warrior p be successful. In case (a), each node in
the kingdom which lost is informed of the identity of the new king king p and updates its
level to level p (note that the value of level p is unchanged in the attacking kingdom). In
case (b), each node in the attacked kingdom receives the identity king p of the new king
and all nodes in both kingdoms increases their level by one (the level of a kingdom never
decreases). After a successful attack by a warrior p to a warrior j, the warrior of the new
kingdom is warrior j . We say that a processor enters a new round when its level changes,
(i.e., when its kingdom has been defeated or when its kingdom successfully attacked a
kingdom of an identical level).
Asynchronous Rule (controls the number of messages during each phase): three
di#erent cases are theoretically possible when an attack from a warrior p reaches a node
in another kingdom:
1. status p < status j : the warrior is not strong enough to attack this kingdom and,
thus, its attack fails: the message is killed and the attacking kingdom is just waiting
to get attacked.
2. status p > status j : the attack from p must be forwarded to warrior j . Any subsequent
attack by other kingdoms, if not killed, is delayed until this attack is resolved
at j (i.e., until j receives a new status).
When forwarding an attack, if node i on the path to warrior j has a greater status
(i.e., status i > status p ), the request is killed. This situation occurs when the
previously visited nodes have not yet been informed that they have become part of
a greater kingdom (i.e., the level has increased).
When the attack reaches warrior j, if it still has a lower status, then a surrender
message is sent back to warrior p and each node on the path waits for the new status.
3. status proved later, this case (i.e., an attack within the same king-
dom) cannot occur during the execution of the algorithm.
If warrior p receives a message of surrender, it broadcasts the new status to the absorbed
kingdom or to both kingdoms, depending on the promotion rule. The new local
view List is obtained by merging the two Lists. The initial local view is a list of bits
the list is initialized to 10 # (i.e., all bits are set to 0 except List[0] which is set to 1).
Concurrency. The number of concurrent incoming attacks in a kingdom must be
limited in order to guarantee a message complexity of O(n) for each round. A substate
Substate p for each node p is introduced to specify if the node is WaitingForSurrender (has
forwarded an attack message), is WaitingForStatus (has forwarded a surrender message
and is waiting for its new level), or is Regular (is ready to receive an attack). The state
transition diagram of a processor is shown in Figure 3(b).
Some substates are introduced to deal with two specific situations which may occur
due to the inherent concurrency of the model.
First of all, if a citizen j has forwarded an attack to warrior j a subsequent attack
with a greater status will be delayed (wait at j), but not killed (asynchronous rule 2).
Secondly, an incoming attack can be received before knowing that the kingdom has
already absorbed (or been absorbed by) another kingdom: the level may have increased.
In both cases, the citizen knows afterwards (when it receives the new status) if the
forwarded attack was successful. At this time, if the status of the forwarded attack is
smaller than the new received status, the attack will be killed; thus, the citizen can go
Branched
opened
closed
Branched
Failed
(a) CHORDS
Unused Regular
Status
WaitingFor
Surrender
WaitingFor
(b) NODES

Figure

3: State Transition Diagrams
back to regular substate. Otherwise, the current attack status is still legal; thus, the
inhibition waiting substate must be kept.
Progress. The problem occurs if a warrior q receives a surrender message from a warrior
when it is already engaged in a wait for status process from a warrior w (q has been
attacked by w while attacking p). Consistently with the asynchronous rule, the warrior
q has to wait for the new status of warrior w before it can send the new status to the
warrior p. The extreme case occurs if - a more complicate scenario involving more nodes
can be deduced - w is waiting for p (p has attacked w): a deadlock situation. As proved
later in Theorem 2.1, the total lexicographic order on the status forbids the creation of
such a waiting cycles.
Structural Information. The knowledge of the size of the network, the topology, a
globally consistent assignment of labels (or, labelings) to interconnection nodes and communication
links is used to reduce the communication cost. Since the loop network is a
node-symmetric graph (all its nodes are similar to one another), each node can represent
the other nodes by their relative distance along the cycle. This is actually available with
the edge labeling and can be used to pass the knowledge of the processors (represented by
their distances) that have been already reached: when node p 1 receives a message from
node p 2 by the incident chord labeled d 1 , it can unambiguously "decode" the information
about other nodes contained in the message. Namely, if the message contains information
about the node linked to p 2 by a chord d 2 , then this information refers to the node at
distance (d 1 +d 2 ) mod n from p 1 in the ring ordering. This fact will be used to determine
whether an unused chord (i.e., on which no messages have been sent) is outgoing or not
(that is connected to a di#erent kingdom or not). This function combined with the local
view of a processor provides the message with a consistent representation of the kingdom
which can be passed from processor to processor. This decoding function corresponds to
a circular bit shift by the length of the chord, denoted as transpose (the exact code of
the function is given at the end of the algorithm).
Termination and Partitioning. The algorithm terminates when the kingdom includes
all nodes in its connected non-faulty subgraph. The determination of this event may
di#er depending on whether the network is disconnected or not. Consider first the case
of a partitioned network. Once all reachable nodes have become part of the kingdom, the
king will become warrior (because of the bactracking inherent to the depth first search
strategy) and all its incident chords will be closed (there is no outgoing link towards a
node which does not belong to the kingdom). At this point, it will detect termination;
from its local view, it will also determined the size of its kingdom and that a disconnection
has occurred.
If the network is not disconnected, the termination detection can occur earlier: as
soon as a warrior determines, by its local view, that the kingdom includes all the nodes
in the network (the list is full, i.e., set to 1 # ).
In both cases, the warrior (which is possibly the king) broadcasts along the tree the termination
message. Since this message contains the view of the warrior upon termination,
every node in the component can determine whether or not the graph is disconnected as
well as which other nodes are in this component. In the case of a disconnection, depending
on the application, the king can take the appropriate action.
An example of an attack is shown in Figure 5, where the kingdom K has a greater status
than the kingdom K # (the corresponding loop network C 16 #3, 8# is shown in Figure 4).
The result of the successful attack is shown in Figure 6.
Messages Used:
. (REQUEST,Status): it is an attack by a warrior, and is forwarded to its adversary.
This message is also considered as the first ATTEMPT on the chord, and provides
the failure detection if the chord is faulty,
. (SURRENDER,Status): it is sent by a defeated warrior to inform the winner of its
success,
. (NEWSTATUS,Status): it is broadcast by the winner on the appropriate tree (de-
pending on promotion rule),
. (BRANCH): it is sent by a successful warrior on the chord connecting the two trees,
. (BACKTRACK,Status): it is sent by the warrior to its parent when all its chords
have been closed, that is when all the nodes reachable through this chord are part
of the kingdom or are faulty,
. (MOVEWARRIOR,Status): it is sent by the warrior to one of its opened chords
after a backtracking,
. (TERMINATION): it is broadcast by the sole remaining warrior of the connected
component to terminate the execution of the algorithm.
Any number of processors can spontaneously start the execution of the algorithm;
this is modeled by the reception of a WAKEUP message. The active components are
those where at least one processor spontaneously start the algorithm (i.e., it receives a
WAKEUP message).
KING REQUEST BRANCHED
a
l
c
e
d
f

Figure

4: Kingdoms in C
2.2 Correctness
The protocol is fully asynchronous, the messages received by each processor and the
order in which each processor receives its messages depends on the initial input but is
non-determinist. However the algorithm is event-driven with messages processed in first-
in-first-out order, the order in which each processor processes its communication relies on
tree structures and on the asynchronous and progress rules.
The correctness follows after establishing the safety (a warrior never attacks a node of
its kingdom), the progress (eventually a tree spans all the nodes of a connected compo-
nent), and the appropriate termination (there is exactly one elected node in a connected
component of the network). In the following, numbers between parentheses refer to corresponding
sections of the algorithm in the Appendix.
Lemma 2.1 A request message is initiated by a warrior through an unused opened chord.
The request message only traversed citizen nodes and branched chords leading to the warrior
of the kingdom traversed.
Proof The warrior sends the request (if the attempt is successful) through an unused
opened arc (4, 5, 7, and procedure attempt at the end of the description of the algorithm).
A citizen (or king) can send a request only upon receipt of a request (1) to forward it to
its warrior through links labeled W out , that is, a used chord of a citizen. 2
G
C O
A
J O
I
K'
F
A
A
O
C A G L
request
branched
warrior
king
G

Figure

5: Two Kingdoms in C
Corollary 2.1 The status of a chord becomes used if a warrior has previously sent a
request through it, or if the chord has been detected as faulty.
Lemma 2.2 The local view List p at a warrior p represents exactly the list of processors
which belong to the kingdom of the warrior p.
Proof By induction. Clearly, this is true at the initialization when the local view is
set to 10 # . Assuming the local view List p at a warrior w is correct and complete before
an attack, the warrior modifies its view either after a successful attack (while receiving a
surrender message (8): the warrior becomes a citizen, combines the two views, and pass
the warrior privilege of the new combined kingdom to the defeated warrior) or after being
defeated (while receiving a newstatus message (7): it receives the view of the winning
kingdom, and by combination obtains the complete view of the merged kingdom). In
both cases, the new local view contains the exact list of processors of the new kingdom,
which proves the induction. 2
Lemma 2.3 (Safety.) A warrior never attacks a node of its kingdom.
Proof As shown in Lemma 2.2, an attack can only be done upon receipt of a new
status which creates the new list of all the nodes which belong to the kingdom (7). All
the chords linked to these nodes are closed, any remaining unused chord, even randomly
chosen, leads to a processor of a di#erent kingdom. Therefore, no cycle can be created in
the kingdom. 2
Several facts and properties can be observed to clarify the correctness.
Fact 2.1 From (1) and the asynchronous rule, a waiting citizen, or king, does not process
request messages.
A
A
O
C A L
G
A
I
F
request
branched
warrior
king
G

Figure

of Attack in C
Fact 2.2 Eventually each node in a kingdom receives the status of its kingdom. Indeed,
at the end of any phase or after being defeated (8), the designated warrior broadcasts the
new status along the traversed chords.
waiting cycle of requests may be created.
Proof Immediate since sending a request does not change the regular state of the warrior
(7). Therefore, all the requests which wait on a non regular node do not block the warrior
which has initiated them. 2
Theorem 2.1 (Progress.) A deadlock may not be introduced by the waiting which arises
when some nodes must wait until some condition holds.
Proof The message sending is non-blocking. The only case for which a node is blocked
waiting for an event is when a warrior waits for a new status message after sending
a surrender (1). Similarly, such a surrender message can be deferred at the successful
warrior node if it has surrendered to another warrior attack (8). Repeating this setting, a
chain of waiting (on surrender) processors can occur. However, this chain cannot become
a circular wait: a surrender message is initialized only on a successful attack, that is when
the status of an attacking warrior j is strictly lexicographically larger than the status
of a defending warrior p. The total ordering on the status defined by the promotion
rule forbids such a waiting cycle of processors: status j < . < status p < . < status j
contradicts the definition. 2
Corollary 2.2 Eventually, no node is in a waiting substate.
Theorem 2.2 A kingdom is a rooted directed tree.
Proof By induction. Initially, each kingdom is a one node tree (0). The kingdom is
defined by the subgraph composed by the chords marked K out and their incident nodes,
and is rooted by the king. It can also be defined by the subgraph composed by the chords
marked W out and their incident nodes: in this case the tree is rooted at the warrior.
Following a successful attack, the chord connecting the two trees (the absorbing and
the absorbed ones) becomes part of the kingdom upon receipt of a NEWSTATUS message
initiated by the winner warrior and broadcast through the absorbed kingdom.
The outgoing chord to the king is stored in the K out label. The king has a nil value for
K out (0). A node (citizen and/or king (3), warrior (7)) changes its label K out only after
receiving a new status message announcing the absorption by another kingdom; in this
case K out is set to the incoming arc from which such a message is received. This change
of orientation guarantees that the tree is rooted at the new king. Note that a similar
observation can be repeated for the tree rooted at the warrior. 2
Lemma 2.5 (Appropriate Termination.) The algorithm terminates with a forest of,
at most, one rooted spanning tree for each connected components.
Proof By the safety Lemma 2.3, the progress Theorem 2.1, and Theorem 2.2. In each
connected component where at least one processor initiated the Election protocol, the
algorithm builds a rooted spanning tree. 2
The main Theorem is deduced:
Theorem 2.3 The algorithm correctly elects a leader.
Proof By Theorem 2.1, Theorem 2.2, and Lemma 2.5, the theorem holds. The Election
protocol is independently started by any subset of processors electing a particular node
in each active connected component (the king (10)). Each group of processors in a (par-
titioned or not) active component forms a consistent view (containing the exact list of
reachable processors) with a single elected node: the king. Depending on the application,
these distinctive elements can thus take the appropriate actions: e.g., promote themselves
leader on a majority basis, wait for the recovery of the faulty components, simulate the
non-faulty topology by embedding it into the active connected group, form a restricted
(connected) working group,. 2
2.3 Analysis
The measure of e#ciency analyzed here is the communication complexity (the number
and size of messages sent).
Lemma 2.6 The number of rounds is at most log k for each kingdom, if k independent
nodes start the algorithm.
Proof By the promotion rule, based on a tournament, at most n/2 i nodes enter phase i,
in fact k/2 i if k independent nodes start the algorithm. The maximum number of rounds
is the maximum value of the level of the winning kingdom, i.e., log k. 2
Corollary 2.3 The number of surrender messages sent by a warrior during a particular
execution is at most log k, if k independent nodes start the algorithm.
Lemma 2.7 For a given round and a given non-faulty chord l in a kingdom, at most two
requests will be transmitted through the chord l.
Proof For a given round and a given non-faulty chord l in a kingdom, a request passing
through this chord will face several possible outcomes:
1. The request is successful with an identical level: it will cause the round to increase in
both kingdom. Any forthcoming requests with this previous level will be discarded
at the incident node.
2. The request is successful with a di#erent (i.e., larger) level: the level value is updated
only in the absorbed kingdom. By Lemma 2.3, only requests sent by a di#erent
kingdom may occur. Another request with the same level will behave as described
in the case 1 limiting the number of such occurrences to two.
3. the request is unsuccessful: that is, the message has been killed further on the path
to the warrior. This implies that the level has been increased by another attack,
but the nodes incident on this chord does not know it yet. By the concurrency rule
enforcing delay, only one other request can wait at the incident node and will be
discarded when the newstatus arrives.
A similar argument can be used for a branched chord between two kingdoms. 2
Corollary 2.4 For a given round and a given non-faulty chord l in a kingdom, at most
two surrender (resp. new status) messages will be transmitted through the chord l.
More precisely,
Theorem 2.4 The total number of messages used by the algorithm does not exceed
Proof The number of messages of each kind is the following:
sent, at a given round, through at most n - 1 non-faulty chords (see
Lemma 2.7). Hence, the total number of such request messages sent during the
whole execution is bounded by 2 n log k.
sent through a path in a kingdom only before a modification of its
level. Hence, the total number of such messages sent during the whole execution is
also bounded by 2 n log k.
broadcast in the kingdom only to increase its level. Hence, the total
number of such messages sent during the whole execution is also bounded by
sent on each branched chord of the kingdom, i.e., at most n - 1 messages.
sent on a branched chord of the kingdom if the subtree cannot reach
further nodes. Hence, the total number of such messages is bounded by the size of
the spanning tree, i.e., at most n - 1.
sent on each opened-branched chord of the kingdom if the node
cannot reach further nodes. Hence, the total number of such messages is also
bounded by the size of the spanning tree, i.e., at most n - 1.
TERMINATION : at most n - 1 messages.Only seven di#erent types of message exists. The status is composed of: the identity of
the king which value is at most m, the level which takes at most log n values, and the List
which is a n bits array. Therefore, the size of each message is at most n
bits.
Theorem 2.5 The algorithm has an optimal worst-case message complexity.
Proof Given a loop network C, let F (C) denote the set of the possible combination
of links failures in C; clearly the cardinality of F (C) is 2 |E| where E is the set of chords
of C. Given f # F (C) denote by M(C, f) the number of messages required to solve the
election problem in C when the failures described by f have occurred. Then, the worst
case complexity WC(C) to solve the election problem in C after an arbitrary number of
link failures is
where n is the number of processors, and R n is the ring without bypass; the last equality
follows from the lower bound by [6] on rings. 2
2.4 Sensitivity to Absence of Failures
The algorithm we have presented uses O(n log n) messages in the worst case, regardless
of the amount of faults in the system.
Consider now the case where no faults have occurred in the system and an Election is
required. If all the nodes had a priori knowledge of this absence of failures, then they could
execute an optimal Election protocol for non-faulty networks. In this case, depending on
the chord structure, a lower complexity (in some cases, O(n)) can be achieved [4, 18, 23,
24, 32]. However, to achieve this complexity, it is required that the absence of failures is
a priori known (more specifically, it is common knowledge [15]) to all processors.
Now we show how to achieve the same result without requiring this common-knowledge.
First observe that the existing optimal algorithms for election in non-faulty loop networks
use only a specific subset of the chords to transmit messages. The basic idea is quite sim-
ple. A processor "assumes" that its specific incident arcs are non-faulty. Based on this
assumption, it starts the corresponding topology-dependent optimal election algorithm
A. If a processor x detects a failure when attempting to transmit a message of protocol
A, x will start the execution of the algorithm proposed in section 2. Thus, if there is no
failures, algorithm A terminates using MA messages; if there are failures, the overall cost
of this strategy is MA +O(n log n) which is O(n log n) since MA # O(n log n).
The approach actually leads to a stronger result. To obtain the topology-dependent
optimal bound MA for the non-faulty case is su#cient that the chords used by A are
fault-free.
3 Extensions and Applications
We will consider in this section the election problem in a di#erent setting. In fact, we
study arbitrary networks with sense of direction in absence of faults. We show how the
previous results presented in this paper can be immediately used to prove the positive
impact that the availability of "sense of direction" has on the message complexity of
distributed problems in arbitrary fault-free networks.
3.1 Sense of Direction
The sense of direction refers to the capability of a processor to distinguish between
adjacent communication lines, according to some globally consistent scheme [12, 36]. For
example, in a ring network this property is also usually referred to as orientation, which
expresses the processor's ability to distinguish between ''left'' and ''right'', where ''left''
means the same to all processors. In oriented tori (i.e., with sense of direction), labelings
"up" and "down" are added. The existence of an intuitive labeling based on the dimension
provides a sense of direction for hypercube, [11]: each edge between two nodes is labeled on
each node by the dimension of the bit of the identity in which they di#er. Similarly, the
natural labeling for loop networks discussed in the previous section is a sense of direction.
For these networks, the availability of sense of direction has been shown to have some
impact on the message complexity of the Election problem.
In an arbitrary network, we define a globally consistent labeling on the links by extending
in a natural way the existing definitions for particular topologies. Fix a cyclic
ordering of the processors. The network has a distance sense of direction if at each processor
each incident link is labeled according to the distance in the above cycle to the
other node reached by this link. In particular, if the link between processors p and q is
labeled by distance d at processor p, this link is labeled by n - d at processor q, where n
is the number of processors. An example of sense of direction for an arbitrary network is
shown in Figure 7. Note that such a definition intrinsically requires the knowledge of the
size n of the network, and it includes as special cases the definition of sense of direction
for the topologies referred above: the oriented ring ("left" and "right" correspond to 1
and n - 1, respectively), the oriented complete networks (n set to the number of links
plus one), and the oriented loop network or circulant graph. Furthermore, in hypercubes,
this sense of direction is derivable in O(N) messages from the traditional one [11].
3.2 Election in Fault-Free Arbitrary Networks
We now consider the impact of sense of direction on the message complexity of the Election
problem.
A
G
F
(a) (b)177A
F
G

Figure

7: Arbitrary Network (a) with Sense of Direction (b)
It is obvious that every graph is a subset of the complete graph; that is, any arbitrary
network is an "incomplete" complete graph. Less obvious is the fact that:
Every arbitrary network with sense of direction is an "incomplete" loop network.
That is, every arbitrary network is a loop network where some edges have been removed.
This simple observation have immediate important consequences. It implies that an
arbitrary graph with sense of direction is just a faulty loop network (compare Figure 1
and

Figure

7): the missing links correspond to the faulty ones. Moreover, in this setting,
every processor already know which links are faulty (i.e., missing).
As a consequence, the algorithm described in Section 2 is also a solution to the election
problem in fault-free arbitrary graphs with sense of direction [25].
By theorem 2.4, it follows that if there is sense of direction, a solution with O(n log n)
messages exists for the Election problem.
log n) is a lower bound on the
message complexity for the election problem in bidirectional ring with sense of direction
[6], it follows
log n) is also a lower bound on the general case. Thus, the bound
is tight. In contrast, in arbitrary networks of n processors where the links have no globally
consistent labeling (no sense of
log n) messages are required to elect
a leader [35], and such a bound is achievable [13].
The importance of the result is that it shows the positive impact of sense of direction on
the communication complexity of the Election problem in arbitrary network, confirming
the existing results for specific topologies. An interesting consequence of our result follows
when comparing it to those obtained assuming that each processor knows all the identities
of its neighbours [20, 22]. Namely, it shows that it is possible to obtain the same reduction
in message complexity requiring much less information (port labels instead of neighbour's
name).
Concluding Remarks
In this paper, we have presented a #(n log n) solution for the Election problem in loop
networks where an arbitrary number of links have failed and a processor can only detect
the status of its incident links. If the network is not partitioned, the algorithm will detect
it and will elect a leader. In case the failures have partitioned the network, a distinctive
element will be determined in each active component and will detect that a partition
has occurred; depending on the application, these distinctive elements can thus take the
appropriate actions. Moreover, the algorithm is worst-case optimal.
All previous results have been established only for complete graphs and have assumed
an a priori bound on the number of failures. No e#cient solution has been yet developed
for arbitrary circulant graphs when failures are bounded but undetectable.
Our result is quite general. In fact, our algorithm can be easily modified to solve the
Election problem with the same complexity for fault-free arbitrary networks with sense
of direction.



--R


Election in asynchronous complete networks with intermittent link failures.
Analysis of chordal ring.

Distributed loop computer networks: a survey.
New lower bound techniques for distributed leader finding and other problems on rings of processors.

Doubly link ring networks.
Designing fault-tolerant systems using automorphisms
Impossibility of distributed consensus with one faulty process.
Optimal elections in labeled hypercubes.
Sense of direction: formal definition and properties.
A distributed algorithm for minimum spanning tree.
Electing a leader in a ring with link failures.
Knowledge and common knowledge in a distributed environ- ment
Optimal distributed t-resilient election in complete networks
A distributed spanning tree algorithm.
Towards optimal distributed election on chordal rings.
A distributed election protocol for unreliable networks.
A modular technique for the design of e
Tight lower and upper bounds for a class of distributed algorithms for a complete network of processors.
A fully distributed (minimal) spanning tree algorithm.
Election in complete networks with a sense of direction.
Optimal distributed algorithms in unlabeled tori and chordal rings.
On the impact of sense of direction in arbitrary networks.
Optimal fault-tolerant leader election in chordal rings
Tolerance of double-loop computer networks to multinode failures
Optimal fault-tolerant distributed algorithms for election in complete networks with a global sense of direction
Distributed Systems.
On reliability analysis of chordal rings.


Comments on tolerance of double-loop computer networks to multinode failures
Reliable loop topologies for large local computer networks.
On the message complexity of distributed problems.
Sense of direction
Optimal asynchronous agreement and leader election algorithm for complete networks with byzantine faulty links.
Leader election in the presence of link failures.
A multiple fault-tolerant processor network architecture for pipeline computing
Design of a distributed fault-tolerant loop network
Faults and Fault-Tolerance in Distributed Systems: the Election problem
Election on faulty rings with incomplete size information.
--TR

--CTR
Paola Flocchini , Bernard Mans , Nicola Santoro, Sense of direction in distributed computing, Theoretical Computer Science, v.291 n.1, p.29-53, 4 January
fault tolerance;loop networks;interconnection networks;leader election;sense of direction;distributed algorithms