A near-optimal multistage distributed algorithm for finding leaders in clustered chordal rings (Q1328564)

In a distributed computer system, each processor has an identity number known only to the processor itself. The processor that has the highest identity is the leader of the network. The problem of finding the leader is called an election algorithm. Chordal rings are a class of networks with a ring topology and with additional edges (chords) connecting processors with distances of more than two along the ring. A new nearly optimal in number of messages and links multistage electron algorithm for a clustered chordal ring is proposed in this paper. An upper complexity bound in the author's algorithm are \(O(G(n),n)\) for messages and \(G(n)\) chords at each processor. The function \(G(n)\) is defined recursively and has a very low speed of increasing. For all \(n < 2 60536\) the value \(G(n) < 5\). This result enhances many previous results by other authors.