Efficient leader election using sense of direction.
This paper presents a protocol for leader election in complete networks with a sense of direction. Sense of direction provides nodes the capability of distinguishing between their incident links according to a global scheme. We propose a protocol for leader election which requires <i>O(N)</i> messages and <i>O</i>(log <i>N</i>) time. The protocol is message optimal and the time complexity is a significant improvement over currently known protocols for this problem.
Introduction
Leader election is a fundamental problem in distributed computing and has been
studied in various computation models. In the leader election problem, there are
N processors in the network, each having a unique identity. Initially all nodes are
passive and are unaware of the identity of any other node. An arbitrary subset of
nodes, called the candidates, wake up spontaneously and start the protocol. On the
termination of the protocol, exactly one node announces itself the leader. In this
paper, we consider the problem of electing a leader in an asynchronous complete
network, where each pair of nodes is connected by a bidirectional link.
For a complete network in which a node is unable to distinguish between its incident
links, [4] showed
log N) messages are required for electing a leader.
However, [5] showed that the lower bound of \Omega\Gamma N log N) messages does not hold
* This work was supported by NSF grants CCR-9211621 and CCR-9502506. Some of the results
on this paper appeared in the ACM Symposium on Principles of Distributed Computing, 1992.
for complete networks with sense of direction [8] and gave a protocol which requires
O(N) messages and O(N) time (assuming that the transmission delay for each message
is at most one time unit, the computation time is negligible and the processes
start asynchronously). network has a sense of direction if there exists a directed
Hamiltonion cycle and each edge incident at a node is labeled with the distance of
the node at the other end of this edge along this Hamiltonion cycle. Figure 1 shows
a complete network containing six nodes with a sense of direction. In this figure, for
example, the edge (b; d) is labeled 2 and 4 at nodes b and d respectively (because d
is at distance 2 from b along the cycle and b is distance 4 from d along the cycle).
A protocol with O(N) time complexity and O(N) message complexity is also given
in [6].
In the protocols in [5] and [6], a node captures at least a majority of nodes
before it declares itself as the leader. We observe that in the presence of sense of
direction, a node does not have to capture a majority of nodes in order to be elected
the leader. We use this idea to obtain a protocol which requires O(N) messages
and O(log N) time. The protocol proceeds in two phases. In the first phase, we
reduce the number of candidates to approximately N= log N . This is accomplished
by logically dividing the ring into N= log N interleaved subrings, each with log N
nodes, and electing at most one leader in each subring. To elect itself the leader of
its subring, a node must capture all nodes in its subring. In the second phase of
the protocol, the remaining candidates compete with one another to elect a single
leader. The problem is that a candidate i may not know which nodes in the other
subrings are candidates. However, all other subrings have a representative among
the set of nodes which are within distance and each node knows
the identity of the candidate in its subring. Node i uses these representative nodes
to capture other candidates. Using this process, the second phase elects a single
leader among the leaders of the subrings.
There are many problems such as spanning tree construction and computing a
global function, which are equivalent to leader election in terms of message and time
complexities. Our protocol, therefore, leads to improvement in the time complexity
of these problems as well. Protocols for chordal networks (a basic ring with additional
chords) have been proposed in [2, 3, 7]. A complete network with a sense of
direction is the extreme case of chordal networks (a ring with all possible chords).
Although complete networks are not practical, they have been studied extensively
as they provide bounds for more practical networks (with less connectivity).
This paper is organized as follows. In the next section, we present our model of
a
c
d
e
Figure

1: A complete network with a sense of direction.
distributed computation. In Section 3, we present a protocol for leader election in a
complete network with sense of direction. We present the conclusions in Section 4.
Model
We model the communication network as a complete graph (V; E), where V and E
represent the processors and communication links respectively. We use N to denote
jV j. We assume that each node has a unique identity and the network has a sense
of direction. Messages sent over a link arrive at their destination within finite but
unpredictable time, in the order sent and are not lost. The message complexity of
a protocol is the maximum number of messages sent during any possible execution
of the protocol. The time complexity of a protocol is the worst case execution time
assuming that each message takes at most one time unit to reach its destination
and the computation time is negligible. Furthermore, inter-message delay on a link
is at most one time unit. These assumptions are made only for the purpose of
computing the time complexity (the correctness of the protocol is not impacted by
these assumptions). All additions in the paper are assumed modulo N.
In the rest of the paper, unless specified otherwise, we will consider a complete
network with sense of direction. For simplicity, we assume that node identities are
positive integers. We will use (l; d) ! (l
Finally, let i[d] denote the node at distance d from i (note that
and i[x::y] denote the set fi[x]; i[x i[y]g. For example, in Figure 1,
c and eg.
3 An election protocol
[5] and [6] have proposed leader election protocols which require O(N) messages
and O(N) time. The main idea in these protocols is as follows: Each node i tries
to extend its set of captured nodes along the cycle in a sequential manner. Thus, if
i has already captured nodes in the set i[1::x] then it tries to capture i[x 1]. The
protocol ensures that if i has captured nodes in i[1::x] then there is no candidate
in i[1::x]. Therefore, if node i is able to capture nodes in the set i[1::N=2] (which
including i forms a majority) then it can declare itself as the leader. The capturing
of nodes is based on node identities. Each node includes its identity in the messages
sent to capture other nodes. If j receives a message with identity i and i ? j then
j is captured.
The protocols in [5] and [6] use sense of direction to avoid multiple capturing of
nodes. As shown in Figure 2, if j has captured nodes in the set j[1::y] and i captures
extends its set of captured nodes to i[1::x does not
capture nodes already captured by j; it just inherits these nodes). Using sense
x y

Figure

2: i inherits the nodes captured by j
of direction, i can determine the edges leading to nodes in the set j[1::y] and can
avoid sending messages to capture these nodes. In the absence of sense of direction,
even though j may have captured some nodes, i cannot determine the edges leading
to these nodes and may send messages on these edges for capturing (in the worst
case, it may send messages to all already captured nodes and an execution requiring
log N) messages can be constructed [4]).
In any protocol, let S i denote any set of nodes which i can capture and become
the leader. If the sets of nodes captured by different candidates at any time are
disjoint then it is sufficient that for any two candidates i and j,
OE (this ensures that i and j will both try to capture a common node and only
one of them will be successful). We observe that in the presence of a sense of
direction, S i does not have to contain a majority of nodes. For example, if S
j. By capturing
i[N=2], for example, i knows that nodes in i[N=4 + 1::N=2] will have to contest with
i via node i[N=2] to become the leader. In general, for any k, if i is able to capture
nodes in the set i[1::k \Gamma 1] and fi[k];
the leader. We combine this idea with those in [5] to obtain a new protocol which
is described in the following.
We assume that N is a power of 2 (we later discuss the modifications needed
when N is not a power of 2). Let . The protocol proceeds in two
phases. In the first phase, we reduce the number of candidates to at most k. This is
accomplished by logically dividing the ring into k subrings as follows: The subring
which node i belongs to consists of nodes in the set fi[0]; i[k]; k]g.
We will use R i to denote the subring of i. In the first phase, we elect at most one
leader in each subring. To elect itself the leader of its subring, i must capture all
nodes in R i . Note that since i 2 R j nodes in a subring will contest
with one another in the first phase.
In the second phase of the protocol, the remaining candidates compete with one
another to elect a single leader. The problem is that a candidate i may not know
which nodes in the other subrings are candidates. However, all other subrings have
a representative in the set i[1::k \Gamma 1] and each node in knows the identity of
the candidate in its subring (if one exists). Node i uses these representative nodes
to capture other candidates (informally, if i attempts to capture j, j informs i of its
candidate). Using this process, the second phase elects a single leader among the
leaders of the subrings.
The two phases are described in detail in the following. Each node maintains
the following variables:
Initially, state i is passive. When i wakes up spontaneously to initiate the
protocol, it changes state i to candidate. If node i has been captured then state i
captured. If i has been elected then state i is elected.
Initially, level i is 0. At any other time, level i denotes the number of nodes
i has captured in the first phase.
Initially, step i is 0. The election in the second phase proceeds in a sequence
of steps. For a candidate, step i denotes the current step number of i in the second
phase.
For a candidate node i, owner For a captured node, i[owner i
denotes the edge leading to the leader of R i (which is updated at the end of the
first phase).
(either spontaneously or on receiving a message), it sets
phase i to 1. phase i is 2 if i has entered the second phase as a candidate or has
received a message of the second phase.
The following is the list of messages used by the protocol. Each message carries
O(log N) bits.
This message is sent by i to capture another
node. If phase i is 1 then the second argument is level i , else it is step i .
ffl INFORM(dist): In the second phase, a node using this message to inform the
sender of a CAPTURE message regarding the distance to its owner.
This message is sent in response to a CAPTURE message
and indicates that i was captured as a result of the CAPTURE message. The
second argument is omitting if phase i is 2.
ffl OWNER(id): This message is sent by the leader to all members of its subring
at the end of the first phase to announce the fact that it has been elected in its
subring.
ffl ACK: This message is sent to acknowledge the receipt of the OWNER message.
ffl ELECTED: This message is sent at the end of the second phase by a node to
announce that fact that it has been elected as the leader in the network.
First Phase: In the first phase, the election proceeds within each subring sepa-
rately. Figure 3 gives the protocol executed when node j is a candidate and Figure 4
gives the protocol executed by j if it is passive or captured (in the figures, we have
1 state := candidate; level := 0; phase :=
2 while state = candidate and phase = 1 do
3 if level - n=k then
send OWNER(j) to all nodes in R j ; Response := 0
5 else send CAPTURE(1; level; j) to j[(level
6 Received := false
7 while state = candidate and phase = 1 and :Received
receive M on edge j[e]
Case M of
send ACCEPT(level) over j[e]; state := captured
phase := 2;
17 ELECTED(i): state := captured
candidate and phase = 2 do
20 while state = candidate and :elected do
to j[k=2 step
22 Received := false; Response := 0;
23 while state = candidate and :elected and :Received do
receive M over j[e]
Case M of
26
28 send ACCEPT(2) over e; state := captured
elected := true else Received := true

Figure

3: Protocol for a candidate node j
34 done := false;
while :done do
receive M on edge j[e]
if M is the first message received then
38 state := captured; owner := 0; phase := 1
Case M of
42 send ACCEPT(2) over j[e]; phase := 2
43 else send INFORM(owner) over j[e];
44
phase := 2; send ACK(i) over j[e]
48

Figure

4: Protocol for a captured node j
omitted index j from the variables for clarity). We will explain the actions in the
following. On waking up spontaneously, a candidate node i tries to capture nodes
in R i in a sequential fashion. A passive node may wake up on receiving a message
of the protocol. However, a passive node is not allowed to become a candidate if it
wakes up on receiving the message of the protocol. A node i uses its identity and
level i to contest with other nodes.
On waking up spontaneously, i sets state i to candidate and sends a message
to i[k]. When any other node j receives a CAPTURE(1; l; i)
message over edge j[e], it behaves as follows:
ffl If state j 6= candidate and phase responds with an ACCEPT(1;
message. If j is passive then j changes state j to captured.
ffl If state
owner j and responds with ACCEPT(1; level j ) message. Otherwise, it ignores
the message.
If phase j is 2 then the CAPTURE message is ignored. If i receives ACCEPT(1; l)
and it is still a candidate, then it adds l + 1 to level i (and therefore the set of
captured nodes is extended to include the nodes captured by j). If level
then i continues its conquest by sending a CAPTURE message to i[(level
If level i - N=k then i sends a message, OWNER(i), to each node j in R i to inform
these nodes of its identity. Note that a node in R i may not know that i has captured
it because it may have been inherited by i.
On receiving OWNER(i) message over edge j[e], j behaves as follows: if j has
already been captured by a node in the second phase then j ignores the message.
Otherwise, j sets owner j to e and sends an ACK(j) message over j[owner j ]. If i
receives an ACK message in response to each of its OWNER messages, and it is still
a candidate then i enters the second phase.
Second Phase: In this phase, we have k subrings and at most one candidate in
each subring, and we have to elect a leader among them. In [1], a protocol for leader
election in synchronous complete networks without sense of direction was proposed.
In this protocol, the capturing of nodes proceeds in log N steps. In the first step, a
candidate i sends a message to capture one node. In the l th step, i send messages
to capture 2 nodes. Hence, in log N steps, i sends messages to capture all nodes.
We employ this method of capturing in the second phase. Let i be any candidate
in the second phase. The execution of a candidate in this phase is logically divided
into steps (with the variable step i indicating the current step of i). The variable
step i indicates the progress i has made in the second phase (which is similar to
the use of level i in the first phase). Informally, if two nodes compete with one
another, then the node with the larger (step; id) pair wins. In the following, by
node i entering step l, we will mean that step i is assigned the value l.
On entering the second phase, candidate i assigns step sends a message
to capture the candidate in R i+k=2 (assuming that the nodes are numbered
one can view the subrings as arranged in a cycle as shown in Figure
5). In general, if step sends messages to 2 l\Gamma1 candidates in the subrings
g. If i is able to capture all nodes to which it sent
a message in step l, then it increments step i . If step i ? log k then i can declare itself
the leader. However, if i wants to capture the candidate in R i+x , it may not know

Figure

5: Arrangement of subrings for
which node is the candidate in R i+x . Therefore, to contest with other candidates, i
actually attempts to capture the nodes in i[1::k \Gamma 1]. Capturing node i[x] will force
i to contest with the candidate in R i+x as explained in the following (note that
i[x] belongs to R i+x receive a CAPTURE message from i. If i[x] is the
candidate of R i+x then i and i[x] contest with one another. Otherwise, i[x] informs
i of its subring's candidate identity (if there exists a candidate in R i+x then i[x]
would have received an OWNER message from it in the first phase). On receiving
this information, i sends a message directly to the candidate. More specifically, if j
(= i[x]) receives a CAPTURE(2; l; i) message, we have the following cases:
ffl If state sends an AC-
CEPT(2) message to i and changes state to captured. If state
ignores the message.
ffl If state candidate and phase (j is a candidate still in the first phase) or
state j 6= candidate and owner (j has not received the OWNER message of
the first phase) then there is no candidate in R j which has captured all nodes in R j
and informed them of its identity. In this case, j sends an ACCEPT message to i.
If state j 6= candidate and owner j 6= 0 then j sends the message INFORM(owner j )
to i.
On receiving the INFORM(y) message over i[x], node i sends a
message to i[x
This method of capturing leads to the following structure. When step
sends a message to capture the candidate in R i+k=2 . If there is a candidate, say
j, in R i+k=2 then j, on entering the second phase, will send a message to capture
i (because R i is the same as R j+k=2 ). It is possible that i's message to capture
reaches before step (j has not entered the second phase) in which case i
will capture j. Hence, one of i and j will capture the other and increment its step
variable. If step send messages to capture the candidates in R i+k=4
and R i+3k=4 . If one of the candidates, say j, from R i+k=4 and R i+3k=4 has step
(only one of them can enter step 2), then j will send messages to capture i and
the candidate in R i+k=2 . Hence, i and j will contest with one another. Again, it
is possible that i 0 s messages reach the candidates in R i+k=4 and R i+3k=4 before any
of them increment their step variable to 2 (in which case i will capture them) or
vice-versa. In any case, only one candidate among those from subrings R i , R i+k=4 ,
R i+k=2 and R i+3k=4 will capture the others and increments its step variable to 3.
As shown later, with this method of capturing, at most k=2 l\Gamma1 nodes can enter step
l. Therefore, at most one node will proceed to step log k + 1, which is elected the
leader.
We will now prove the correctness and determine the complexity of the protocol.
The line numbers in the following lemmas refer to code in Figure 3 and Figure 4.
k]g. In the following lemmas, we assume that the
execution of the protocol starts at time 0. Given any execution, we assume that
the maximum time taken by a message to reach its destination in that execution as
one time unit (computation time is assumed negligible), and therefore, all messages
in that execution are delivered in at most one time unit. Hence, if node i sends a
message m over edge e at time t and there are no messages in transit on e then m
is received and processed by time t + 1.
Lemma 3.1 At any time, if level i ? 0 and phase
(1) there exist no other candidate in cap(level i ; i), and
(2) for all nodes j in cap(level
Proof: We will prove this by induction on level i . If level (base case) then
cap(level is empty and the property holds trivially. Assume that for any node x, if
level there exists no other candidate in cap(level x ; x) and
for all nodes j in cap(level x ; x), cap(level level x .
Let i be a node with level must have received an ACCEPT message
from a node, say j, which resulted in level i being assigned the value m+ 1. Assume
that i sent a CAPTURE message to j at time t 1 and received an ACCEPT(1; l)
message from j at time t 2 . Then, state candidate at time t 2 (otherwise, i will
not increment level i to m+ 1). Since i received an ACCEPT response, level
and phase when the ACCEPT message is sent. Then, from the induction
hypothesis, there exists no other candidate in cap(level j ; j). Since j also changes
state to captured, there exist no candidate in cap(level . Also, from the
induction hypothesis, for all nodes p in cap(level
and level p ! level
level i to level i level j at time t 2 ), for all nodes x in cap(level
cap(level level i at time t 2 . 2
Since a node enters the second phase only when its level reaches N=k, Lemma 3.1
ensures that at most one candidate from each subring will enter the second phase.
The following lemma shows that at least one node will enter the second phase within
time.
Lemma 3.2 Within O(N=k) time of the first node waking up, some node will enter
the second phase.
Proof: We first show that it takes at most 3 time units for one node to capture
another node in the first phase. Assume that i is successful in capturing j. To
capture node j, node i sends a CAPTURE message. Since i is successful in capturing
send an ACCEPT message (lines 10-11 and line 40). This message will reach
units (as there may be a CAPTURE message in transit from j to
i). Therefore, capturing of a node requires at most 3 time units.
At any time t, let i be the candidate node in the first phase with the largest
(level; id) pair. Let i send a CAPTURE message to j. By time t we have the
following possibilities:
1. i captures j: In this case, i will increase its level number (lines 10-11).
2. i is blocked: In this case, either j has a larger level number or the same level
number as i but a larger id (lines 10-11 when the if condition evaluates to false).
3. i is captured by a node in the first phase: Again, this node must have a larger
level number or the same level number as i but a larger id.
4. i is captured by a node in the second phase.
Therefore, if no node has entered the second phase by time t 3, then there exists
a candidate with a larger (level; id) pair during the interval [t; t 3] than at time t.
Thus, every 3 time units, the largest (level; id) of a candidate node (not a captured
node) increases provided no node has entered the second phase. Consider
time slots of 3 time units each. At most N=k\Gamma1 of these slots can be associated with a
node in a subring being blocked or captured (since a candidate is blocked or changes
state to captured at most once). The remaining N=k slots must be associated with
level number increases. Therefore, some node will reach level N=k after
time slots after the first node wakes up unless a message is received from a node
in another subring (this node must be in the second phase). After reaching level
N=k, a node sends an OWNER message simultaneously to all nodes and will receive
response within a constant amount of time. Hence, within O(N=k) time of the first
node waking up, some node will enter the second phase. 2
Lemma 3.3 In the second phase, there can be at most k=2 l\Gamma1 candidates which
enter step l.
Proof: Let S i;m denote the set of nodes to which i sends a CAPTURE message
when step i becomes m, and R i;m denote the set of rings to which nodes in S i;m
belong. Then, S
. The set S i;1::m contains all nodes at distances which are multiples
of k=2 m from i. Thus, if the distance of a node from i is a multiple of k=2 l , then i
will not send a message to capture this node until it enters step l.
Consider any two candidates i and j such that j 2 R i[x(k=2 y )] . That is, the node,
say p, in i[1::k] belonging to the same subring as j is at a distance from i which
is a multiple of k=2 y . Then, i will not send a message to p (and hence to
step i is y. Similarly, j will not send a message to i until step j is y. Since i must
capture j to enter step y only one of them will increment its
step variable to y + 1. In addition, from the definition of R i;1::m and the fact that
p is at a distance which is multiple of k=2 y , for all m ! y, R i;1::m and R j;1::m are
disjoint and R j 2 R i;y and R i 2 R j;y . That is, the set of subrings whose candidates
will attempt to capture while step i ! y is disjoint from the set of subrings whose
candidates j will attempt to capture while step y.
In any execution, consider two candidates i and j such that step i - l and
y. Then, only one of i and j will increment
its step variable to y. Since both step i and step j are greater than or equal to l,
l - y and therefore, the set of subrings captured by i before step i becomes l is
disjoint from the set of subrings captured by j before step j becomes l. Thus, in
an execution, if two candidates have their step variables greater than or equal to
l, then the sets of subrings captured by them before they enter step l are disjoint.
Since jS any execution, there will be at most k=2 l\Gamma1 nodes
that enter step l. 2
From Lemma 3.3, only one node will successfully complete step log k and enter
step log k + 1, and therefore, at most one node will announce itself the leader. The
following lemma shows that within O(N=k) time of the first node entering the second
phase, some node will declare itself the leader.
Lemma 3.4 Within O(log time of the first node entering the second phase, some
node will declare itself the leader.
Proof: Let i be the first node to enter step m, say at time t.
Since step i is m, i sends messages simultaneously to capture nodes in S i;m (line 21).
Consider any node j in S i;m . The CAPTURE message from i will reach j by time
is not a candidate and phase (which implies there exists a candidate
in R j ) then j will send an INFORM message to i which will then send a CAPTURE
message to owner j . Thus, the CAPTURE message will reach the candidate in R j
within a constant amount of time. If the candidate, say p, in R j has step
will capture it and prevent p from entering step m. Therefore, all candidates in
R i;m which enter step m enter within constant time of the first candidate in R i;m
entering this step.
Assume that when step sends a CAPTURE message to j and is successful
in capturing the candidate, say x, in R j (note that x may be j). As shown above, the
message from i will reach x within a constant amount of time. Since we assume that
captures x, x will send an ACCEPT message to i which will reach i within
units (as there may be a CAPTURE message in transit from x to i). Thus, if i is
successful in capturing the candidate in R j then it will receive an ACCEPT message
within a constant amount of time. Otherwise, it will get blocked at a process with
a larger (step; id) pair.
If i is the first node to enter step m at time t, then all candidates in R i;m which
enter step m will do so within a constant amount of time. Let p be the node with
the largest id among the candidates in R i;m with their step variable as m. This
node will send messages to capture candidates in R i;m simultaneously, say at
(where constant). Within a constant amount of time after t 0 , either p will
capture all candidates in R i;m and enter step m+ 1 (because p is the node with the
largest id and it takes a constant amount of time to capture a node) or it will be
captured (p cannot be blocked as it is the node with the largest id). If p is captured,
say by q, then q must be in step greater than m (because all candidates which send
messages to capture p in step m belong to R i;m ). Thus, for any m, within constant
time of the first node entering step m, some node will enter step m+ 1. Since there
are log k steps, at most one node will enter step log k
the first node entering the second phase. 2
We now evaluate the message complexity of the protocol. We say that j is
directly captured by i in the first phase if i sends a CAPTURE message to j and
receives an ACCEPT response while it is still a candidate.
Lemma 3.5 Each node is directly captured at most once in the first phase.
Proof: Assume, by way of contradiction, that a node j is directly captured more
x
y

Figure

directly captured by both p and i
than once. Let p be the first node to directly capture j, say at time t. Then
t. Let i be the next node to directly capture j. Assume that
the CAPTURE message from i reaches j at time t 0 . Let i[k
shown in Figure 6. Then, y ? x (because, from Lemma 3.1, all nodes in cap(level
are captured at time t 0 ). Since i sent a CAPTURE message to j, level
at time t 0 (line 5). Also, since p has already directly captured j, level p - x at
time t 0 . Then, at time t 0 , there exists a node p such that p in cap(level
cap(level which is a contradiction to Lemma 3.1. Hence, each
node is captured at most once. 2
Lemma 3.6 The message complexity of the first phase is O(N=k) in each subring.
Proof: The messages in the first phase are CAPTURE messages, OWNER messages
and the messages generated in response to these messages. When a CAPTURE
message is sent by i, we have the following three possibilities:
(1) The message results in a direct capturing of a node. From Lemma 3.5, each
node is directly captured at most once. Therefore, there can at most O(N=k) such
messages.
(2) The CAPTURE message is ignored. In this case, i will be blocked. Since i sends
message sequentially in the first phase, each node can be blocked on at most one
CAPTURE message. Since a blocked node does not send messages, there can at
most O(N=k) such CAPTURE messages.
(3) The CAPTURE message is responded to by an ACCEPT message but i is
captured by the time the ACCEPT message is received. In this case, i changes
state of captured. Since each node can change state to captured at most once, there
can be O(N=k) such CAPTURE messages. Hence, there can be total of O(N=k)
messages.
Since each CAPTURE message is responded to by at most one ACCEPT message,
there are at most O(N=k) ACCEPT messages. The candidate which captures all
other nodes sends N=k OWNER messages, each of which is responded to by at
most one ACK message. Hence, election in each subring in phase 1 requires O(N=k)
messages. 2
Lemma 3.7 The message complexity of the second phase is O(k log k).
Proof: In the second phase, there are at most k candidates. From Lemma 3.3,
there can be at most k=2 l\Gamma1 candidates in step l. A node in step l sends 2
messages to capture nodes. Each of these messages generate a constant number of
messages. Hence, the total number of messages generated in the second phase is
Theorem 3.1 The protocol satisfies the following properties:
1. The time complexity of the protocol is O(log N).
2. The message complexity of the protocol is O(N).
3. Assuming that a node identity can be encoded using O(log N) bits, all messages
carry O(log N) bits of information.
Proof: The time complexity of the first phase is O(N=k) (Lemma 3.2) and that
of the second phase is O(log
complexity of the protocol is O(log N ). From Lemma 3.6, the message complexity
of election in each subring R i is O(N=k). Since there are k subrings, the first phase
requires O(N) messages. From Lemma 3.7, the number of messages in the second
phase is O(k log Hence, the message complexity of the protocol is O(N ).
Finally, the fact that all messages carry O(log N) bits of information is evident from
the format of the messages. 2
In the protocol presented above, we assume that N is a power of 2. If N is not
a power of 2, then the protocol has to be modified. Let M be the smallest number
greater N such that M is a power of 2. Let We have defined R i as
consisting of nodes fi; i[k]; g. If N is not a power of 2, then it may be that
case the i 2 R j but j 62 R i . For example if 4. Assume that nodes
have identities 9 and are arranged in the given order in the ring. Then,
4g. We modify the algorithm as follows: In the
first phase, i attempts to capture nodes in R i as described before. After capturing
these nodes, it sends a CAPTURE message simultaneously to all nodes j such that
can determine this set of nodes as N is known to i). After capturing this
set of nodes, i can enter the second phase. In the second phase, a similar strategy
is used. In the l th step, i sends message to all nodes which are at distances that are
multiples of k=2 l (except those nodes which i has already captured). In addition, it
also sends messages to all nodes j such that i is at distance which is a multiple of
k=2 l from node j. This modification ensures that at most one node will announce
itself the leader. The number of messages and the time required is only increased
by a constant factor.



--R

Time and message bounds for election in synchronous and asynchronous complete networks.
Efficient elections in chordal ring networks.
Towards optimal distributed election on chordal rings.
Optimal lower bounds for some distributed algorithms for a complete network of processors.
Election in complete networks with a sense of direction.
Optimal fault-tolerant distributed algorithms for election in complete networks with a global sense of direction

Sense of direction
--TR
Election in a complete network with a sense of direction
Optimal lower bounds for some distributed algorithms for a complete network of processors
Towards optimal distributed election on chordal rings
Time and message bounds for election in synchronous and asynchronous complete networks
A near-optimal multistage distributed algorithm for finding leaders in clustered chordal rings
Optimal Fault-Tolerant Distributed Algorithms for Election in Complete Networks with a Global Sense of Direction
Sense of direction, topological awareness and communication complexity

--CTR
Synnve Kekkonen-Moneta, Torus orientation, Distributed Computing, v.15 n.1, p.39-48, January 2002
Paola Flocchini , Alessandro Roncato , Nicola Santoro, Computing on anonymous networks with sense of direction, Theoretical Computer Science, v.301 n.1-3, p.355-379, 14 May
Paola Flocchini , Alessandro Roncato , Nicola Santoro, Backward consistency and sense of direction in advanced distributed systems, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.189-198, May 04-06, 1999, Atlanta, Georgia, United States
Paola Flocchini , Bernard Mans , Nicola Santoro, Sense of direction in distributed computing, Theoretical Computer Science, v.291 n.1, p.29-53, 4 January
complete networks;leader election;distributed algorithm;message complexity