IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 3, JUNE 2004 483Distributed Council ElectionDanny Raz, Member, IEEE, Yuval Shavitt, Senior Member, IEEE, and Lixia Zhang, Senior Member, IEEEAbstract—This paper studies the problem of electing a smallnumber of representatives (council) out of a (possible large) groupof anonymous candidates. The problem arises in scenarios such asmulticast where, to avoid feedback implosion, a small subset of thereceivers is chosen to provide feedback on network conditions.We present several algorithms for this problem and analyze theexpected number of messages and rounds required for their con-vergence. In particular, we present an algorithm that almost alwaysconverges in one round using a small number of messages (for typ-ical council size) when the number of hosts is known. In the casewhere the number of hosts is unknown (and too large to be polled),our algorithms converge in a small number of rounds that improvesprevious results by Bolot et al. (1994).Index Terms—Leader election, multicast.I. INTRODUCTIONIN MANY distributed applications, there is a need to dis-tributively elect a small group of hosts out of a potentiallylarge population. The elected group needs to be maintainedunder dynamic network conditions that include new membersjoining and leaving and network temporary partition. In thispaper we concentrate on the special case where all the grouphosts are members of a multicast group. This enables the sourceof the multicast group to convey information to all the nodes“for free” by piggybacking control information in the multicastdata messages.There are many applications for this problem in multicast pro-tocols. Due to the feedback implosion problem, there is a need toelect a small group of representatives out of the (possibly) largeset of receivers (multicast group members). An election mech-anism was proposed by Bolotet al. [1] to elect a small numberof receivers and collect feedback from them regarding loss rateand congestion in the multicast group.A particular example where such algorithms are implementedis the IDMaps project [2]. As part of this project, measurementstations (Tracers) are installed in various locations in the In-ternet. These tracers measure the distance among themselvesand to other areas in the Internet. The measurement results arethen sent to (potentially many) topology servers by multicast. Toreduce measurement overhead, topology servers provide feed-back for the usefulness of each measurement to the Tracer. ToManuscript received November 26, 2001; revised April 18, 2003; approvedby IEEE/ACM TRANSACTIONS ON NETWORKING Editor S. Paul. The work ofY. Shavitt was supported in part by the Israel Science Foundation.D. Raz is with the Computer Science Faculty, Technion—I.I.T., Haifa, Israel(e-mail: [email protected]).Y. Shavitt is with the Department of Electrical Engineering-Systems, Tel AvivUniversity, Tel Aviv 69978, Israel (e-mail: [email protected]).L. Zhang is with the Computer Science Department, University of California,Los Angeles 90095-1596 USA (e-mail: [email protected]).Digital Object Identifier 10.1109/TNET.2004.828945avoid the feedback implosion problem at Tracers, there is a needto select one or a few representatives out of the topology serverpopulation.In both the multicast congestion control and the IDMaps ex-ample, communication from a data transmitting entity (a multi-cast source or a Tracer in IDMaps) to a group of hosts is doneusing multicast while the reverse direction is done using unicasttransmissions. In both examples the population size may varyover several orders of magnitude, the population may changeover time, and the transmitting entity has no initial knowledgeof the population size. In the above examples, choosing a singlerepresentative is usually undesirable both for redundancy andbetter statistical representation (in the multicast example). Thus,our algorithms are capable of electing a group of any size ina predefined range,. and are input to thealgorithm and should be selected by the application based ontradeoffs between redundancy (pushing for higher values) andoverhead (pushing for lower values). Note that if the transmit-ting entity knows the IDs of all the receivers it can (determin-istically) choose the representatives, but we cannot assume thisdue to the feedback implosion problem.We model this environment using a synchronous distributedelection process. In this process hosts do not communicate di-rectly to each other, but rather they communicate through a cen-tral entity that sends a global message to the entire population.Two measures of interest in this environment are the expectednumber of rounds for election,, and the expected number ofunicast messages needed,. It is important to note that whenthe target council size is smallthe solution presentedin this paper and previous solutions, perform the election witha very small, between 1 and 14. For all practical matters thedifference between solutions in this range is marginal. However,the duration of a round with the current Internet round trip de-lays is in the order of a second, thus improvingeven by oneexpected round has significance to the convergence time of thealgorithm.We present in this paper several distributed randomized al-gorithms and analyze their performance. The algorithms ex-plore the tradeoff between the two measures above and the statemaintained in the hosts. We describe a naive algorithm to estab-lish a baseline for our research. We present several algorithmthat attempt to improve both measures, using some state. Weshow trade-offs between the amount of state kept at the hostsand the expected number of rounds and messages. In particularone of our algorithms further reduces the expected number ofrounds,, to be close to 1 (e.g., when we achieveregardless of ), but is not optimal with respect tothe number of messages.The above algorithms assume thatis either known or al-ternatively can be polled in a single round andmessages.1063-6692/04$20.00 © 2004 IEEE484 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 3, JUNE 2004We use these algorithms as building blocks for algorithms thatdo not know. We first show the robustness of the suggestedalgorithms to an inaccurate estimation of. This leads to anefficient algorithm for the case whereis unknown and maybetoo big to be polled. The algorithm searches forin a way sim-ilar to the one suggested by Bolot et al. [1], but achieves su-perior performance, by