Distributed Leader Election on Chordal Ring Networks

Koji NAKANO  Toshimitsu MASUZAWA  Nobuki TOKURA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.1   pp.58-63
Publication Date: 1992/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
Category: 
Keyword: 
distributed algorithm,  leader election,  chordal ring network,  message complexity,  

Full Text: PDF>>
Buy this Article




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).