### Abstract

An efficient protocol for leader election in an asynchronous complete network is presented. The time complexity of the protocol is better than the currently known protocols for this problem. A message optimal protocol is presented that requires O(N/log N) time, where N is the number of nodes in the network. Also given is 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, computing a global function, etc., are equivalent to leader election in terms of their message and time complexities, and therefore the author's results also improve the time complexity of these problems.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - International Conference on Distributed Computing Systems |

Editors | Anon |

Publisher | IEEE Computer Society |

Pages | 472-479 |

Number of pages | 8 |

ISBN (Print) | 0818621443 |

State | Published - May 1 1991 |

Externally published | Yes |

Event | Proceedings of the 11th International Conference on Distributed Computing Systems - Arlington, TX, USA Duration: May 20 1991 → May 24 1991 |

### Publication series

Name | Proceedings - International Conference on Distributed Computing Systems |
---|

### Other

Other | Proceedings of the 11th International Conference on Distributed Computing Systems |
---|---|

City | Arlington, TX, USA |

Period | 5/20/91 → 5/24/91 |

### ASJC Scopus subject areas

- Software
- Hardware and Architecture
- Computer Networks and Communications

## Fingerprint Dive into the research topics of 'Efficient distributed algorithms for leader election in complete networks'. Together they form a unique fingerprint.

## Cite this

*Proceedings - International Conference on Distributed Computing Systems*(pp. 472-479). (Proceedings - International Conference on Distributed Computing Systems). IEEE Computer Society.