Distributed council election.
This paper studies the problem of electing a small number of representatives (council) out of a (possible large) group of anonymous candidates. The problem arises in scenarios such as multicast where, to avoid feedback implosion, a small subset of the receivers is chosen to provide feedback on network conditions.We present several algorithms for this problem and analyze the expected number of messages and rounds required for their convergence. In particular, we present an algorithm that almost always converges in one round using a small number of messages (for typical council size) when the number of hosts is known. In the case where the number of hosts is unknown (and too large to be polled), our algorithms converge in a small number of rounds that improves previous results by Bolot et al. (1994).
INTRODUCTION
In many distributed applications there is a need to distributively
elect a small group of hosts out of a potentially
large population. The elected group needs to be maintained
under dynamic network conditions that include new
members joining and leaving and network temporary partition

A typical application for this problem appears in multicast
protocols. Due to the feedback implosion problem,
there is a need to elect a small group of representatives
out of the (possibly) large set of receivers (multicast group
members). An election mechanism was proposed by Bolot
et al. [BTW94] to elect a small number of receivers and
collect from them feedback regarding loss rate and congestion
in the multicast group. Other applications that
require distributed group-election are electing hot back-up
servers, distributed databases, and distributed network
management.
A particular example where such algorithms are implemented
is the IDMaps project [JJJ As part of this
project, measurement stations (Tracers) are installed in
various locations in the Internet. These tracers measure the
distance among themselves and to other areas in the Inter-
net. The measurement results are then sent to (potentially
many) distance information servers by multicast. To reduce
measurement overhead, distance information servers
provide feedback for the usefulness of each measurement
to the Tracer. To avoid the feedback implosion problem at
Tracers there is a need to select one or a few representatives
out of the server population.
In both the multicast congestion control and the IDMaps
example, communication from some data transmitting entity
to a group of hosts is done using multicast while the
reverse direction is done using unicast transmissions. In
both examples the population size may vary over several
orders of magnitude, the population may change over time,
and the transmitting entity has no initial knowledge of the
population size. In the above examples, choosing a single
representative is usually undesirable both for redundancy
and better statistical representation (in the multicast exam-
ple). Thus, our algorithms are capable of electing a group
of any size in a predefined range, Note that if
the transmitting entity knows the ids of all the receivers it
can (deterministically) choose the representatives, but we
cannot assume this due to the feedback implosion problem.
We model this environment using a synchronous distributed
election process where the hosts do not communicate
among themselves but through a central entity that
sends a global feedback message to the entire population.
Two measures of interest in this environment are the expected
number of rounds for election, T , and the expected
number of unicast messages needed, N .
We present in this work several distributed randomized
algorithms and analyze their performance. The algorithms
explore the tradeoff between the two measures above and
the state maintained in the hosts. We first present a basic
algorithm that requires each host to maintain a single bit
state. This algorithm converges in a small constant number
of rounds regardless of n, the initial population size,
and in sub-linear (in n) number of messages (for typical
Rs). If the hosts can maintain the state from the previous
round, we present an improved algorithm that reduces T
by 10-15% (for typical Rs) and dramatically reduces N
to a constant factor of T , thus omitting N dependency on
n. We then present an algorithm that further reduces the
expected number of rounds, T , to be close to 1 (e.g., when
regardless of n). How-
ever, this last algorithm requires almost double the number
of messages of the previous algorithm (for the above
this is still only N  8 regardless of n).
The above algorithms assume that n is either known or
alternatively can be polled in a single round and n mes-
sages. We show the robustness of the suggested algorithms
to an inaccurate estimation of n. This leads to an efficient
algorithm for the case where n is unknown and maybe too
big to be polled. The algorithm searches for n in a way
similar to the one suggested by Bolot et al. [BTW94] but
achieves superior performance.
II. RELATED WORK
Our problem is similar to the collision resolution problem
in multiple access (MA) networks. In this type of net-work
hosts try to transmit packets via a shared medium. If
multiple transmissions overlap, usually the packet collides
and the targeted receiver cannot decode the signal. The
problem of collision resolution in MA networks had been
extensively studied during the 1970s and the 1980s, and
several sub-models that differ in the feedback the hosts receive
from the channel were analyzed. Here we emphasize
only the most relevant ones, and refer the interested reader
to a book by Rom and Sidi [RS90].
Most of the work in MA networks concentrated on two
feedback models. The binary model assumes hosts knows
whether a collision occurred or not. The ternary feed-back
model assumes hosts are aware of three channel con-
ditions: silence, no packets transmission; success, one
packet successfully transmitted; and collision, where more
than one packet was transmitted and none was successfully
received by the receiver. The host receives no feedback
about the number of the packets that collided.
Some works dealt with a model with richer feedback
from the channel. Tsybakov [Tsy80] examined a model
where the number of colliding hosts is known. Georgiadis
and Papantoni-Kazakos [GPK82] studied a channel
where the number of colliding hosts is known up to
some bound. Pippenger [Pip81] proved that the capacity
of a collision channel with full multiplicity feedback is
1, Ruszink-o and Vanroose [RV97] gave an algorithm that
achieves this bound.
A few works examined a model of a channel with multiple
reception capability, where up to k 1 simultaneous
transmissions may be decoded. Tsybakov et al. [TML83]
assumed that the channel has a ternary feedback. The hosts
know if the previous slot was idle; if it has some successful
transmissions, up to k 1; or if a collision of k or more
packets occurred. Likhanov et al. [LPS examined a
similar model but assumed that in the case of successful
transmissions the hosts are aware of the exact number of
successful transmissions.
It is important to note that even in the case where the
model in the MA literature is the same as the one used
here, the objective is different and thus the optimization
problem is different. This makes a solution that works
well for one of the problems perform badly in the other.
For example, the model where full multiplicity feedback
is given matches our model for host feedback. Thus, the
results by [Pip81], [RV97] might seem to suggest that as n
grows there exists an algorithm that elects a group (at least
in the case where R = [1::1]) with an expected number of
rounds that approaches one. However, an examination of
the algorithm structure in [Pip81], [RV97] reveals an initialization
phase which takes n= log n rounds whose cost
is amortized over the transmission of n packets. Such a
solution will not fit our goal since we are only interested
in the first successful transmission (in MA jargon).
Other (somewhat less) related line of work is the distributed
leader election. Many variants to this problem
were studied [Lyn97]. The closest model to our problem
is the case of anonymous cliques, i.e., network with full
connectivity but no unique identifiers for the processors.
For this a Monte-Carlo solution was given by Afek and
Matias [AM94], and we are not aware of a Las-Vegas solution
which better fits our model. Note, that in our model
there is a central entity that does not exist in the distributed
leader election literature.
Feedback suppression in multicast was studied extensively
in the recent years. The main two solution approaches
suggested are timer based and structural based
(cf. [NB98]). One exception is the work by Bolot et
al. [BTW94] that suggested a mechanism for feedback
control in a multicast video distribution. In their solution
each host is assigned a random 16 bit vector. The sender
polls the receivers by sending a bit mask to which only
receivers with a matching vector reply. By polling with
masks of decreasing size the sender can ensure a small
number of feedback messages, with high probability, but
the polling may take up to 15 rounds when the number of
receivers is small. Our solution for the unknown n case is
similar in nature, but as demonstrated in section VI-A can
be tuned to achieve faster convergence and any specific
target range of feedback messages.
III. MODEL
We have n hosts and wish to elect a subgroup in the
size range R = [L; U ]. For the election, the hosts communicate
only with a central trusted entity, C; no direct
communication among the hosts is allowed. Communication
is done is synchronous rounds. In each such a round,
C broadcasts a feedback message to all hosts and each host
may send a reply message. We distinguish between solutions
based on the amount of information in the feedback
message, F .
The following parameters are of interest. First we would
like to minimize the expected number of rounds needed
for the election process. Another important parameter we
would like to minimize is the election overhead, which is
the number of messages sent by the hosts through the en-
3basic algorithm
1. Init:
2. N c received feedback
3. if N c < L
4. send reply
5. s 1
6. else if
7. if N c  U
8. send reply
9. else
10. if (rnd() < c=N c )
11. send reply
12. else
13. s 0
Fig. 1. The basic algorithm for the host
basic algorithm
1. N c 0
2. while (N
3. Send Feedback(N c )
4. N c number of replies
Fig. 2. The basic algorithm for C
tire election process, excluding the first n messages.
IV. ALGORITHMS WITH NO HISTORY
We first study a simple algorithm that requires each host
to maintain only one bit of state, s (see Figure 1).
indicates that the host participates in the current election
process. At each round (see Figure 2), C sends the number
of reply messages it received in the previous round, N c ,
i.e., F size is log n bits. A host decides to reply (and suggest
itself as a representative) with probability p defined
below.
c=N c if N c > U and
(1)
where c is a pre-configured constant. The state bit s is set
when the feedback from C is less than L, and reset when
the host drops its candidacy (with probability 1 c=N c ).
The election process starts when C sends the value 0 as
feedback, and it ends when the number of active hosts is in
the desired range. Figures 1 and 2 give a pseudo-code of
the algorithm for the host and C, (rnd() returns a random
number uniformly distributed in [0.1]).
The value of the constant c is pre-determined. Next we
will evaluate the algorithm performance and in particular
show how to calculate the optimal value of c. For this end,
let us first define P rfijmg to be the probability that out
the m hosts that were active (have in the current
round exactly i hosts decide to remain active (not reset s)
c
basic algorithm
simulation
analysis
Fig. 3. A comparison of the simulation results to the analytical
results for T (500),
in the next round.

(2)
The expected number of messages, N(n), is given by
the following relation. In the formulation we omit the cost
of the first initialization round for reasons that will become
clear in section VI-A.
In the first line, we sum over all the possibilities that i hosts
stayed active after this round. We pay i messages for this
round and N n (i) for the rest of the election. The relation
for reflects the fact that the election ends
when the active host number reaches its target range. The
last relation is due to the fact that when we undershoot we
restart the algorithm.
Equation 3 defines a linear system of n
with the n. The
equation can be solved with c as a free parameter to minimize
the message overhead. Note that in the calculation
for a certain n we obtain but the rest of
the values N n (i); i < n cannot be used to obtain N values
A similar system can be defined if one wishes to minimize
the number of rounds it takes the system to elect a
number of representatives in the desired target range. In
this case, we pay a unit price per round.
Although the analysis can be easily used to produce numerical
results, we found out that running high confidence
simulations is much faster for large n values. Thus, most
of the graphs presented in the paper are driven by high
23number of users (n)
expected
number
of
rounds,
L=U=1, c=1.3
L=4, U=8, c=6.6
L=1, U=8, c=4.3
number of users (n)
expected
number
of
messages,
L=4, U=8, c=8.5
L=1, U=8, c=5.6
Fig. 4. The basic algorithm: T (n) and N(n) as a function of n
confidence simulations where each point is the average of
10,000 runs and in all cases the 1% confidence interval is
less than 1%. Figure 3 compares results achieved from
simulations and analysis for T (500) where
and 3  c  8. A simulation point is derived from 10,000
different runs. All the simulation points fall very close to
the analysis results. The simulation can be used both to
predict with high accuracy the value of the function, and
be used for the selection of the optimal c.

Figure

4 depicts the values of T (n) and N(n) for several
target ranges. For each graph we picked c to be a value
closer to the optimum. The most obvious fact from these
graphs is the fast converges of the algorithm, and the little
dependency of T (n) on n. Astonishingly, even for very
large values of n the expected number of rounds (after the
initialization round) is less than 2. The number of messages
needed for the algorithm is also well below n=10 for
a large enough n, and grows at a sub-linear rate.

Figures

show T and N dependency on c for
The dependency is fairly stable for a wide range of n val-
ues. Both functions are fairly flat around the optimum but
become quite steep farther away.
Next we present a simple observation that can help in
L=4, U=8, n=500
L=1, U=8, n=500
Fig. 5. The basic algorithm: T (n) and N(n) as a function of c
selecting c which is close to the optimal. The shape of
P rfijmg has a mode at rapidly drops on both
sides. Thus, by selecting L < c < U one can expect
that most likely an 'undershoot' of the range will be at
and an 'overshoot' at 1. For T
the penalty of undershoot is two rounds while the penalty
of overshoot is one round (T < 2 suggests that in most
cases no more than one additional round is needed), thus
selecting c at the 2/3 point between L and U , i.e.,
2(U L)=3 should most likely lay in the flat region around
the optimum. Similarly for N the penalty for overshoot is
thus the optimal c
can be approximated by U (U L)(U
A. Improved algorithm (Skip-Reset)
Although the basic algorithm performs well, there is still
room for improvement. For this, we use the observation
that when the feedback is less than L there is a wasted
round in which all the hosts suggest themselves as candi-
dates. The only purpose of this round is for the hosts to
learn the value of n, but this value can be advertised by C.
This saves a round and more significantly the n messages
Algorithm Skip-Reset
1. Init:
2. (N c ; r) received feedback
3. if
4. s 1
5. if N c < L
6. send reply
7. s 1
8. else if
9. if N c  U
10. send reply
11. else
12. if rnd() < c=N c
13. send reply
14. else
15. s 0
Fig. 6. Algorithm Skip-Reset for the host
Algorithm Skip-Reset
1. N c 0
2. N 0
3. while (N
4. if N c < L
5. Send Feedback(N; 1)
6. else
7. Send Feedback(N c ;
8. N c number of replies
9. N maxfN;N c g
Fig. 7. Algorithm Skip-Reset for C
that are transmitted in this round 1 .
A pseudo-code of the improved algorithm, called Skip-
Reset, is given in figures 6 and 7. As can be seen, the
addition to the host algorithm is only the ability to receive
a reset bit in the feedback message. The algorithm of C
needs to store in memory the population size (in variable
N ), and use it when a reset is required.
The change in the formulation for this enhancement is
simple. When m < L we can avoid payment for the
skipped round (which is m for N and 1 for T ). Thus,
Equation 3 and Equation 4 should be written as
Our observation is similar in spirit to the one made by Massey for
the binary tree collision resolution protocols [RS90, Section 5.2.1]
number of users (n)
expected
number
of
rounds,
basic
improved
number of users (n)
expected
number
of
messages,
improved
Fig. 8. The improved algorithm vs. the basic algorithm: T (n)
and N(n) for

Figure

8 shows the improvement in the algorithm performance
for 8. While the improvement
in T (n) is modest (a fifth of a round or about 13%) the
improvement in N(n) is dramatic. The almost linear dependency
of N in n is eliminated and we get N(n)  9:2
for n > 100. For other parameter selection similar improvement
is achieved.
B. The power of choice
We've seen above that in most cases the election is done
in one round. To increase the chances of succeeding in
the first round one can use the following technique. At
each round, the host draws two coins with probability p,
and sends an election message containing both drawings
if at least in one of the draws it remains active. This requires
two more bits to be sent with the election message.
When C receives the election messages from the hosts it
can choose to use either of the two rounds of drawing,
whichever optimizes its operation 2 . In particular, this al-
This technique is similar in spirit to the one used by Azar et al. for
the balanced allocation of balls into bins [ABKU99].
1.21.4
number of users (n)
expected
number
of
rounds,
skip-reset
choice
number of users (n)
expected
number
of
messages,
skip-reset
choice
Fig. 9. Algorithm Skip-Reset vs. the choice algorithm: T (n)
and N(n) for
gorithm will take one round if either of the two drawings is
within the target range. For example, if the probability of
success in one round is 1=3 then by using the free choice
of two rounds the probability to succeed in one round increases
to 1 (1
In the feedback C sends, it must include a bit indicating
which of the two election rounds have been used. This
requires the hosts to maintain additional two bits as part
of their state. Figure 9 shows the gain from the algorithm
when combined with the previous improvement of Skip-
Reset. As one can see the number of rounds for the appropriate
choice of c is almost always 1. However, there is a
penalty in an increase in the number of messages (almost
a factor of two). Note however that if we use this improvement
with the basic algorithm it will improve both T and
N .
V. ALGORITHMS WITH HISTORY
In this section we present an algorithm that requires the
hosts to remember their state in the previous round. The
motivation for this type of algorithm is that once less than
Algorithm Skip-Reset with history
1. Init:
2. (N c ; r) received feedback
3. if
4. s 1
5. if N c < L
6. send reply
7. s 1
8. else if
9. if N c  U
10. send reply
11. else
12. if rnd() < c=N c
13. send reply
14. else
15. s 0
16. else if s
17. s h 0
Fig. 10. Algorithm Skip-Reset with history for the host
Algorithm Skip-Reset with history
1. N c 0
2. N 0
3. while (N
4. if N c < L
5. Send Feedback(N; 1)
6. else
7. Send Feedback(N c ;
8. N N c
9. N c number of replies
Fig. 11. Algorithm Skip-Reset with history for C
L hosts are left active it is better to return to the pervious
round which may have less active participants than the initial
number of active hosts. This should potentially reduce
the number of messages of Algorithm Skip-Reset without
adding to the number of rounds.

Figures

show a pseudo-code for Algorithm
Skip-Reset with one round history. The host maintains its
previous state in the variable s h and returns to an active
mode if it receives a reset notification and was active in
the previous round. C maintains the smallest number (that
is still larger than L) of active hosts it learned, and sends it
with a reset upon receiving less than L replies.
Equations 3 and 4 seem to change only slightly to
However, the change is more substantial. By introducing
history of the last state, the algorithm never rolls back, and
the equation becomes oblivious to the initial host popu-
lation. The main advantage of this is the ability to solve
the equations iteratively, and obtain in O(n 2 ) all the N(i)
values for L  i  n. The same holds for T .
The iterative form of equations 7 and 8 (for i > U ) is
Note that at every round during the election the expected
number of messages C receives is c regardless of the number
of active hosts. This means that
all (these functions are not defined for m < L). Of
course this does not mean that for each election the number
of messages sent is c times the number of election rounds.
This fact can be easily proved by induction. For m  U
Assuming the hypothesis holds for
some m 1 we have
which proves the hypothesis.
It is clear, that holds also for Algorithm
Skip-Reset since there also at every round the number
of messages is expected to be c. However, finding
an algebraic proof for Algorithm Skip-Reset is still open
(though the logical proof is suffice). For the basic algorithm
and the constant factor relation
does not hold. The reason is that in some rounds, namely
after the feedback message shows less than L active hosts,
the number of active hosts is n with probability 1 (and not
expected to be c).

Figure

12 depicts the improvement in Algorithm Skip-
Reset when history is used. The gain in T (n) is 5-6%
while the gain in N(n) is around a quarter of a percent.
For reference, we also plot algorithm choice that improves
T by roughly 40% but increases N by about 5%.
VI. ROBUSTNESS
In the previous sections we assumed that either n is
known, or that C can poll all nodes for their number. In
some applications, like multicast feedback, such polling
number of users (n)
expected
number
of
rounds,
skip-reset
choice
history
41.11.14number of users (n)
expected
number
of
messages,
skip-reset
choice
history
Fig. 12. A performance comparison of Algorithm Skip-Reset
the choice algorithm and Algorithm Skip-Reset with history
for 'leader election' scenario
values
may cause feedback implosion, in other applications the
number of hosts may dynamically change as a result of
hosts joining/leaving, or network partitioning. For such
cases it is important to check the robustness of the algorithms
presented in the previous section to an inaccurate
estimation of n. Figure 13 presents the performance of Algorithm
Skip-Reset when used with an estimation of the
total number of hosts (n), instead of the real value. One
can see that a factor of 10 mistakes in the value of n, does
not increase T (n) by more than one round, but it may generate
times more messages if the estimation is an un-
dershot. Another fact that is clear from Figure 13 is that it
always pays to overestimate. This is due to the fact that underestimation
may cause to generate many messages since
the nodes are using a much too big overestimation
will cause additional round(s) in which no message
is transmitted since
A. Estimating n
The robustness of the algorithms with respect to n, indicates
that there will be a very small degradation in per-
5log2(initial guess / true n)
T(with
T(n
n=5000
N(with
N(n
n=5000
Fig. 13. Relative performance of Algorithm Skip-Reset under
different estimations of n where
formance in a scenario where a small number of nodes are
either joining or leaving the system. However, in applications
like multicast, the number of hosts may vary sig-
nificantly, and it is important to keep the estimation always
bigger than the actual n value to avoid feedback implosion.
We suggest a family of algorithms that starts with a very
high estimation (say 100000 to compare with 2 16 that is
used in [BTW94]), and reduces it every time the number of
responses is smaller than L. The rate at which the estimation
is reduced is given by a function
In this work we used a family of functions defined in the
following way
The second condition ensures that the estimation is not in
the range [1.U ]. When the estimated value of n
decreases by a constant factor of  > 1. However, when
< 1 the estimated value of n decreases much faster.
The latter, has a shorter convergence time but may result
in more messages.
Algorithm Skip-Reset with estimating n
1. N c 0
2. N MAXGUESS
3. Send Feedback(MAXGUESS; 1)
4. while (N
5. N c number of replies
6. if N c < L
7. N f(N)
8. Send Feedback(N; 1)
9. else
11. N maxfN;N c g
Fig. 14. Algorithm Skip-Reset with estimating n for C
Let f(^n) be the function used to decrease the estimate
when the feedback is below L. Denote by
n fijng the
probability that exactly i out of n hosts will be elected in a
round given an estimate of ^
hosts.

We analyze the performance of the estimation algorithm
assuming Algorithm Skip-Reset is used, and write expressions
for the expected number of messages and rounds
to elect a council given an initial estimation ^
hosts. Note that here (unlike in the previous analysis) we
do count all rounds including the initialization round.
Following the previous formulation, let ^
be the expected number of messages sent and
round (correspondingly) given n hosts and
We can thus write the recursive relations (for
Where N n (i) are the ones calculated from the linear system
in (5). If For
(^n) is not defined since
f(^n) does not return values in this range (see Equation 11).
since each host will suggest
itself as a candidate in the next round.
In the same way we can write equations for
U
number of users, n
l=1, u=8, c=5.6
conservative
aggressive
number of users, n
l=1, u=8, c=5.6
conservative
aggressive
Fig. 15. Performance of algorithm Skip-Reset where n is unknown

Figure

15 shows the performance of the algorithm in a
typical scenario, where the target range is
we are willing to elect up to 8 members (compare to the
responders bound in [BTW94]). We selected two sets
of parameters: a conservative set where
and an aggressive set where
compare these two with the algorithm in [BTW94]. 3 Even
when the actual population is very small (10), our conservative
search takes only about 10 rounds to elect represen-
3 Bolot et al. did not calculate the expected number of messages, instead
they showed that the probability that this number is greater than
is small. We calculated the expected number of messages in their
algorithm by
m.
algorithm section host C feedback
name number memory memory size (bits)
Skip-Reset IV-A 1 bit log n bits 1
choice IV-B 3 bits log n bits


I


OF THE ALGORITHMS PRESENTED
tatives. Compare this with the over 13 rounds required by
the [BTW94] algorithm. Both algorithms reduce their approximation
by a factor of 2. Ours performs better since
the probability of a host to become a candidate is
and when the estimate reaches 60 we get p  1=10. Thus,
with high probability one representative will be elected
much faster convergence is achieved
using the aggressive parameter set. Every time there is
no response the estimation is reduced to ^ n 0:7 , and therefor
four rounds are sufficient for all the n. The reduction in
the number of rounds comes with a penalty of an increase
in the expected number of messages. However, the maximum
of 15 messages the aggressive algorithm achieves is
well within the tolerable. The number of local maxima in
the aggressive algorithm graphs corresponds to the maximal
number of steps.
VII. CONCLUDING REMARKS

Table

I summarizes the algorithms presented in the pa-
per. Note that all these algorithms can work continuously
if we change the while condition in C's algorithm to
true. This way, if the representative group size decreases
over time below L a new election process automatically
restarts. In this context, an interesting research direction
is to design an efficient election algorithm that increases
the group size when it is close to (but still above) L, thus
avoiding the reactivation of the election.



--R

Balanced allocation.
Elections in anonymous networks.
Scalable feed-back control for multicast video distribution in the inter- net
A collision resolution protocol for random access channels with energy detectors.
Lixia Zhang.

Distributed Algorithms.
Optimal multicast feedback.
Bounds on the performance of protocols for a multiple access broadcast channel.
Multiple Access Protocols: Performance and Analysis.
How an Erd-os- R-enyi-type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback
Bounds for packet transmission rate in a random-multiple-access system
Resolution of a conflict of known multi- plicity
--TR
Multiple access protocols: performance and analysis
Elections in anonymous networks
Scalable feedback control for multicast video distribution in the Internet
A reliable multicast framework for light-weight sessions and application level framing
Balanced Allocations
IDMaps
Distributed Algorithms
Control Message Aggregation in Group Communication Protocols
multicast;leader election