Efficient Algorithms for Elections in Meshes and Complete Networks

The problem of electing a leader in distributed networks of processors where the topology is fixed and known is studied. In the case of an n node complete network, an algorithm with message complexity O( n log n) and message delay time O( n) is given. These bounds are optimal to within constant factors. Also studied are meshes of processors. In the case of a square bidirectional mesh, an algorithm is given that has message complexity O(n) and message delay time 0(√ n), which are again optimal. The mesh algorithm can be generalized to give efficient algorithms for unidirectional and rectangular meshes. Both sets of algorithms use the same fundamental idea to achieve their efficiency. indicating that the technique is both powerful and general