Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: A Probabilistically Correct Leader Election Protocol for Large Groups
Authors: Gupta, Indranil
van Renesse, Robbert
Birman, Kenneth P.
Keywords: computer science
technical report
Issue Date: 17-Apr-2000
Publisher: Cornell University
Abstract: This paper presents a scalable leader election protocol for large process groups with a weak membership requirement. The underlying network is assumed to be unreliable but characterized by probabilistic failure rates of processes and message deliveries. The protocol trades correctness for scale, that is, it provides very good probabilistic guarantees on correct termination in the sense of the classical specification of the election problem, and of generating a constant number of messages, both independent of group size. After formally specifying the probabilistic properties, we describe the protocol in detail. Our subsequent mathematical analysis provides probabilistic bounds on the complexity of the protocol. Finally, the results of simulation show that the performance of the protocol is satisfactory.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
2000-1794.pdf210.71 kBAdobe PDFView/Open
2000-1794.ps504.07 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us