Title :
Optimal resilient distributed algorithms for ring election
Author :
Chan, M.Y. ; Chin, F.Y.L.
Author_Institution :
Dept. of Comput. Sci., Hong Kong Univ., Hong Kong
fDate :
4/1/1993 12:00:00 AM
Abstract :
The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that θ(n log n+kr) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where kr is the number of processor recoveries experienced
Keywords :
computational complexity; multiprocessing systems; system recovery; distributed algorithms; dynamic ring; message complexity; processor recoveries; ring election; Computer science; Distributed algorithms; Nominations and elections; Protocols; Relays; Switches; Telecommunication network reliability;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
