A fault-tolerant protocol for election in chordal-ring networks with fail-stop processor failures

Summary & Conclusions -In a distributed computer system, a group of processors is connected by communication links into a network. Each processor (node) of the network has an identity (a unique integer value) that is not related to its position in the network (its address). A processor's identity is known only to the processor. In the problem of leader election, exactly one processor among a network of processors has to be distinguished as the leader. Previously, many efficient election protocols have been proposed for networks with a sense of direction. In particular, the sequential search is used for election in a reliable complete network, and a multi-token search method is used in a faulty complete network. However, election protocols on a faulty ChRgN (chordal ring network) have not been investigated by other researchers. This paper addresses this issue by: studying the problem of leader election in asynchronous ChRgN with a sense of direction and with the presence of undetectable fail-stop processor failures; proposing a new election protocol which a) combines the concept of sequential search and multi-token search techniques, and b) uses an efficient routing algorithm to reduce the total number of messages used. presenting a protocol, for a ChRgN of n processors with / chords/processor and at most/fail-stop faulty processors, with message complexity O(n + (n/l)-log(n) + k-J), where k is the number of processors starting the election process spontaneously and at most f < I processors are faulty; showing that the message complexity of the protocol is optimal within a constant factor when l > log(n). This paper considers only processor failures with fail-stop failures only. Key Words -Distributed algorithm, fault-tolerance, leader election, message complexity, reliable protocol