Leader Election Algorithm in 3D Torus Networks with the Presence of One Link Failure

Leader election is the process of choosing a leader for symmetry breaking where each node in the network eventually decides whether it is a leader or not. This paper proposes a new leader election algorithm to solve the problem of leader failure in three dimensional torus networks. The proposed algorithm solves the election problem despite the existent of link failure. In a network of N nodes connected by three dimensional torus network, the new algorithm needs O(N) messages to elect a new leader in time steps. These results are valid for two cases: the simple case where the leader failure is detected by one node, and the worst case where the failure is discovered by N-1 nodes.