Loading...
Please wait, while we are loading the content...
Similar Documents
Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks (1991)
| Content Provider | CiteSeerX |
|---|---|
| Author | Afek, Yehuda Gafni, Eli |
| Abstract | This paper addresses the problem of distributively electing a leader in both synchronous and asynchronous complete networks. We present O(n log n) messages synchronous and asynchronous algorithms. The time complexity of the synchronous algorithm is O(log n), while that of the asynchronous algorithm is O(n). In the synchronous case, we prove a lower bound of \Omega\Gamma n log n) on the message complexity. We also prove that any message-optimal synchronous algorithm requires\Omega\Gammaqui n) time. In proving these bounds we do not restrict the type of operations performed by nodes. The bounds thus apply to general algorithms and not just to comparison based algorithms. 1 Introduction In the election problem, a single node, called the leader, is to be selected from a set of nodes which initially differ only in their identifiers (ids), with no node being aware of any other id. An arbitrary subset of nodes wakes up spontaneously at arbitrary times and starts the A preliminary version... |
| File Format | |
| Volume Number | 20 |
| Journal | SIAM Journal on Computing |
| Language | English |
| Publisher Date | 1991-01-01 |
| Access Restriction | Open |
| Subject Keyword | Asynchronous Complete Network Message Bound Asynchronous Algorithm Arbitrary Time Synchronous Algorithm Omega Gammaqui Arbitrary Subset Message Complexity Synchronous Case Preliminary Version General Algorithm Message-optimal Synchronous Algorithm Omega Gamma Time Complexity Single Node Election Problem |
| Content Type | Text |
| Resource Type | Article |
