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 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 language | English |
|---|---|
| Title of host publication | 24th International Symposium on Fault-Tolerant Computing, FTCS 1994 |
| Place of Publication | Piscataway, NJ |
| Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| Pages | 392-401 |
| Number of pages | 10 |
| ISBN (Print) | 0818655224, 0818655208 |
| DOIs | |
| Publication status | Published - 1994 |
| Externally published | Yes |
| Event | Proceedings of the 24th International Symposium on Fault-Tolerant Computing - Austin, TX, USA Duration: 15 Jun 1994 → 17 Jun 1994 |
Other
| Other | Proceedings of the 24th International Symposium on Fault-Tolerant Computing |
|---|---|
| City | Austin, TX, USA |
| Period | 15/06/94 → 17/06/94 |