Distributed Leader Election on Chordal Ring Networks

Koji NAKANO, Toshimitsu MASUZAWA, Nobuki TOKURA

Summary :

A chordal ring network is a processor network on which n processors are arranged to a ring with additional chords. We study a distributed leader election algorithm on chordal ring networks and present trade-offs between the message complexity and the number of chords at each processor and between the message complexity and the length of chords as follows:For every d(1dlog^* n1) there exists a chordal ring network with d chords at each processor on which the message complexity for leader election is O(n(log^(d1)nlog^* n)).For every d(1dlog^* n1) there exists a chordal ring network with log^(d1)nd1 chords at each processor on which the message complexity for leader election is O(dn).For every m(2mn/2) there exists a chordal ring network whose chords have at most length m such that the message complexity for leader election is O((n/m)log n).

• Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.1 pp.58-63
• Publication Date: 1992/01/25
• Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)

Authors

Koji NAKANO
Toshimitsu MASUZAWA
Nobuki TOKURA

Keyword

distributed algorithm,  leader election,  chordal ring network,  message complexity