TR-245: Optimal Fault-Tolerant Leader Election in Chordal Rings

Abstract

Chordal rings ( or circulant graphs) are a popular class of fault-tolerant network topologies which include rings and complete graphs. For this class, the fundamental problem of Leader Election has been extensively studied assuming either a fault-free system or an upper-bound on the number of link failures.
We consider chordal rings where an arbitrary number of links has failed and a processor can only detect the status of its incident links.
We shows that a Leader Election protocol in a faulty chordal ring requires only 0( n log n) messages in the worst-case, where n is the number of processors. More­over, we show that this is optimal. If the network is not partitioned, the algorithm will detect it and will elect a leader. In case the failures have partitioned the net­work, a distinctive element will be determined in each active component and will detect that a partition has occured; depending on the application, these distintives elements can thus take the appropriate actions.