A fault‐tolerant algorithm for election in complete networks with a sense of direction
Toshimitsu Masuzawa, Naoki Nishikawa, Kenichi Hagihara, Nobuki Tokura · Systems and Computers in Japan · 1991
Abstract Consider a directed Hamilton cycle H on a complete network. If each processor can distinguish its incident links by the distance on H, the Hamilton cycle is said to have the sense of direction. It is known that the communication complexity of the leader election problem can be reduced by using the sense of direction when there exists no failure in the network. This paper considers the complete network with the sense of direction where at most fp processors (fp < n/2, where n is the total number of processors in the network) are in the fail‐stop condition and presents an algorithm which solves the leader election problem with the communication complexity O(n + k.fp) (k is the number of initiating processors). The result implies that the sense of direction can be used to reduce the communication complexity of the leader election problem also in the complete network with fail‐stop processors. It is shown also that the communication complexity of the presented algorithm is optimal within a constant factor.