Latency-aware leader election

ABSTRACT

Experimental studies have shown that electing a leader based on measurements of the underlying communication network can be beneficial. We use this approach to study the problem of electing a leader that is eventually not only correct (as captured by the Ω failure detector abstraction), but also optimal with respect to the transmission delays to its peers. We give the definitions of this problem and a suitable model, thus allowing us to make an analytical analysis of the problem, which is in contrast to previous work on that topic.

REFERENCES

• 1: Marcos Kawazoe Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Stable Leader Election, Proceedings of the 15th International Conference on Distributed Computing, p.108-122, October 03-05, 2001
• 2: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, On implementing omega with weak reliability and synchrony assumptions, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.306-314, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872081]
• 3: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Communication-efficient leader election and consensus with limited link synchrony, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011816]
• 4: M. Hutle, D. Malkhi, U. Schmid, and L. Zhou. Brief announcement: Chasing the weakest system model for implementing Ω and consensus. In Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS '06), 2006.
• 5: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 6: D. Malkhi, F. Oprea, and L. Zhou. Ω meets paxos: Leader election and stability without eventual timely links. In Proceedings of the 19th International Conference on Distributed Computing (DISC'05), pages 199--213, 2005.
• 7: Livia Sampaio , Francisco Brasileiro, Adaptive Indulgent Consensus, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.422-431, June 28-July 01, 2005 [doi>10.1109/DSN.2005.16]
• 8: L. Sampaio, R. C. Nunes, F. Brasileiro, and I. Jansch-Pôrto. Efficient and robust adaptive consensus services based on oracles. Journal of the Brazilian Computer Society (JBCS), Special Issue on Dependable Computing (2005), 2005.
• 9: L. M. R. Sampaio, F. V. Brasileiro, W. Cirne, and J. C. A. Figueiredo. How bad are wrong suspicions? towards adaptive distributed protocols. In Dependable Systems and Networks (DSN 2003), pages 551--560, Los Alamitos, CA, USA, 2003. IEEE Computer Society.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Keywords:
analytical analysis, distributed algorithms, leader election