Research On The Problems For Leader Election And Clock Synchronization In Distributed Computing

Leader election algorithm and clock synchronization algorithm are two fundamental algorithms in distributed computing. This paper mainly places focus on self-stabilizing leader election algorithm and Ad Hoc networks-based clock synchronization algorithm.Nowadays, Election problem has been studied extensively, but less papers involve its self-stabilization, and existing self-stabilizing election algorithms don't perform well. We analyze two classical self-stabilizing leader election algorithms—AG algorithm and DIM algorithm. The former is for the ID-based network and simple, but it assumes having knowledge about the network's size and its time complexity is O(n~2), where n denotes the number of nodes. Although the latter doesn't assume the network's size, its time complexity is O ( ?D log n) yet, where ? and D denote the maximal degree among all nodes and depth of the tree respectively. We utilize the idea of DIM algorithm and propose a self-stabilizing leader election algorithm for the ID-base network. The new algorithm assumes no knowledge about the network's size and its time complexity is O (δ)(δdenotes the diameter of the network). Furthermore, current self-stabilizing leader election algorithms don't consider real network structure—the real network structure is hierarchical(the hosts connect to the subnets, which connect to backbone networks), and is not"general diagram". Designing real network protocols may utilize the facts, such as hierarchical DNS, NTP and hierarchical routing, etc. We need more flexible algorithm, and these algorithms can adapt the variety of networks. In order to design such algorithms, this paper uses additional structure, which makes distributed algorithms adapt to different networks, improves the time efficiency of original self-stabilizing leader election algorithms, and allows the system to include faults.The clock synchronization algorithms in the wired networks have developed more...