Loop networks (or Hamiltonian 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 loop networks where an arbitrary number of links has
failed and a processor can only detect the status of its incident
links.
We show that a Leader Election protocol in a faulty loop network
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.
The proposed algorithm also detects network partitions. We also show
that it provides an optimal solution for arbitrary non-faulty networks
with sense of direction.