Dynamic system is a recent hot research topic in theoretical distributed computing. The dynamicity caused by process join and leave bring new challenges in fundamental distributed computing problems, such as eventual leader election. In this paper, we consider leader election in dynamic systems with cluster-based hierarchy. Clustering based hierarchy has been used in fundamental distributed algorithms to achieve scalability and low communication cost, but, to the best of our knowledge, it is not considered in eventual leader election, especially in eventual leader for dynamic systems. We firstly define new system models to describe the dynamicity of clusters, and then based on these models, we design an algorithm to elect an eventual leader. With cluster hierarchy, leader election is basically conducted in two layers. In the lower layer, cluster-heads are elected with each cluster. Then, in the upper layer, election is conducted among cluster-heads so as to elect the eventual leader of the whole system. Several key challenging issues caused by cluster dynamicity have been addressed in our design, including blocking in election within a cluster and multiple cluster-heads in election of upper layer. The proposed algorithm is proved to be correct rigorously.
展开▼
