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

Mohammed Refai1, Ahmad Sharieh2, and Fahad Alshammari3
1Sciences and Information Technology Collage, Zarqa Private University, Jordan
2King Abdullah II School for Information Technology, University of Jordan, Jordan
3Information Technology and Computer Science College, University of Malaya, Malaysia

Abstract: 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( ) 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).

Received May 13, 2008; accepted November 25, 2008