Leader election algorithm in 2D torus networks with the presence of one link failure

Abstract EN

Leader election algorithms solve the instability problem in the network which is caused by leader failure.

In this paper, we propose a new leader election algorithm in two dimensional torus networks.

The algorithm aims to elect one node to be a new leader.

The new leader is identified by some characteristics not in the other nodes in the network.

When the process is terminated, the network is returned to a stable state with one node as leader where other nodes are aware of this leader.

The new algorithm solves this problem despite the existence of one link failure.

In a network of N nodes connected by two dimensional torus network, the new algorithm uses O (N) messages to elect a new leader in O (√N ) time steps.

These results are valid for both cases : simple case (when the leader failure is detected by one node) and in the worst case (when the failure is discovered by up to N-1 nodes).