Optimal fault-tolerant leader election in chordal rings

Bernard Mans*, Nicola Santoro

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

3 Citations (Scopus)


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 O(n log n) messages in the worst-case, where n is the number of processors. Moreover, 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 network, a distinctive element will be determined in each active component and will detect that a partition has occurred; depending on the application, these distinctives elements can thus take the appropriate actions.

Original languageEnglish
Title of host publication24th International Symposium on Fault-Tolerant Computing, FTCS 1994
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Print)0818655224, 0818655208
Publication statusPublished - 1994
Externally publishedYes
EventProceedings of the 24th International Symposium on Fault-Tolerant Computing - Austin, TX, USA
Duration: 15 Jun 199417 Jun 1994


OtherProceedings of the 24th International Symposium on Fault-Tolerant Computing
CityAustin, TX, USA


Dive into the research topics of 'Optimal fault-tolerant leader election in chordal rings'. Together they form a unique fingerprint.

Cite this