TY - GEN

T1 - The space complexity of the leader election in anonymous networks

AU - Ando, Ei

AU - Ono, Hirotaka

AU - Sadakane, Kunihiko

AU - Yamashita, Masafumi

PY - 2008

Y1 - 2008

N2 - It is known that the leader election in anonymous networks is not always solvable, and solvable/unsolvable cases are characterized by the network topologies. Therefore a distributed leader election algorithm is required to elect a leader when it is possible, otherwise recognize the impossibility and stop. Although former studies proposed several leader election algorithms, the space complexity of the problem is not considered well. This paper focuses on the space complexity, that is, the necessary or sufficient number of bits on processors to execute a leader election algorithm. First we show that only one bit memory is sufficient for a leader election algorithm which is specific to a fixed n. We then show that a general algorithm can solve the leader election for arbitrary n if each processor has O(n log d) bits memory where d is the maximum degree of a processor. Finally, we give a lower bound Ω(log n) on the space complexity, that is, we show that it is impossible to construct a leader election algorithm if only log n bits are available for a processor.

AB - It is known that the leader election in anonymous networks is not always solvable, and solvable/unsolvable cases are characterized by the network topologies. Therefore a distributed leader election algorithm is required to elect a leader when it is possible, otherwise recognize the impossibility and stop. Although former studies proposed several leader election algorithms, the space complexity of the problem is not considered well. This paper focuses on the space complexity, that is, the necessary or sufficient number of bits on processors to execute a leader election algorithm. First we show that only one bit memory is sufficient for a leader election algorithm which is specific to a fixed n. We then show that a general algorithm can solve the leader election for arbitrary n if each processor has O(n log d) bits memory where d is the maximum degree of a processor. Finally, we give a lower bound Ω(log n) on the space complexity, that is, we show that it is impossible to construct a leader election algorithm if only log n bits are available for a processor.

UR - http://www.scopus.com/inward/record.url?scp=51049103570&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51049103570&partnerID=8YFLogxK

U2 - 10.1109/IPDPS.2008.4536128

DO - 10.1109/IPDPS.2008.4536128

M3 - Conference contribution

AN - SCOPUS:51049103570

SN - 9781424416943

T3 - IPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM

BT - IPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM

T2 - IPDPS 2008 - 22nd IEEE International Parallel and Distributed Processing Symposium

Y2 - 14 April 2008 through 18 April 2008

ER -