RESILIENT DISTRIBUTED ALGORITHMS FOR LEADER ELECTION IN RING USING ROUGHLY SYNCHRONIZED CLOCKS

摘要

Two algorithms for leader election in unidirectional ring are presented using roughly synchronized clocks. It is assumed that each of the processors in the network has a physical clock which is roughly synchronized with all other processors' physical clocks. The election messages with timestamp are circulated around an unidirectional ring to elect the leader. The leader is elected even if the processors fail during the election process. The algorithms also work correctly even if the clock synchronization fails. The nodes in the ring initiate the election algorithm over a time period T and the different initiation times of the nodes are used as timestamp of election messages to obtain better average case message complexity. The average case message complexities of the proposed algorithms are better than that of Chang and Roberts' algorithm for most of the node arrangements in the ring. The two algorithms have O(n~2) and O(n log n) as the worst case message complexity respectively. The algorithms are simulated sequentially for different ring size by varying the initiation times as well as the arrangement of nodes. The worst case time taken by the algorithms is 2nσ, where n is the number of nodes in the ring and σ is the maximum communication delay between any two adjacent nodes.