Leader Election in Hyper-Butterfly Graphs

Leader election in a network is one of the most important problems in the area of distributed algorithm design. Consider any network of N nodes; a leader node is defined to be any node of the network unambiguously identified by some characteristics (unique from all other nodes). A leader election process is defined to be a uniform algorithm (code) executed at each node of the network; at the end of the algorithm execution, exactly one node is elected the leader and all other nodes are in the non-leader state [GHS83,LMW86,Tel93,Tel95a,SBTS01] In this paper, our purpose is to propose an election algorithm for the oriented hyper butterfly networks with O(Nlog N) messages.


Back