Loading...
Please wait, while we are loading the content...
Similar Documents
Leader election in complete networks (1992).
| Content Provider | CiteSeerX |
|---|---|
| Author | Singh, Gurdip |
| Abstract | . Leader election is a fundamentalproblem in distributed computing and has a number of applications. This paper studies the problem of leader election in complete asynchronous networks. We present a message optimal protocol that requires O(N log N) messages and O(N= log N) time, where N is the number of nodes in the system. The time complexity of this protocol is a significant improvement over currently known protocols for this problem. We also give a family of protocols with message and time complexities O(Nk) and O(N=k) respectively, where log N k N . Many problems such as spanning tree construction and computing a global function are equivalent to leader election in terms of their message and time complexities and therefore, our result improves the time complexity of these problems also. Key words. Distributed Algorithms, Leader Election, Time Complexity, Complete Networks. AMS subject classifications. 68Q22, 68Q25, 68N25 1. Introduction. In the leader election problem, there ar... |
| File Format | |
| Publisher Date | 1992-01-01 |
| Access Restriction | Open |
| Subject Keyword | Leader Election Time Complexity Complete Network Distributed Computing Am Subject Classification Global Function Leader Election Problem Key Word Complete Asynchronous Network Message Optimal Protocol Tree Construction Many Problem Paper Study Significant Improvement |
| Content Type | Text |
| Resource Type | Article |
