Research Article
A Self-Stabilizing Leader Election Algorithm In OneHop DHT
@INPROCEEDINGS{10.1109/CHINACOM.2009.5339815, author={Guang-ji WANG and Hai-qiang XUE and Bing WEI}, title={A Self-Stabilizing Leader Election Algorithm In OneHop DHT}, proceedings={ChinaCom2009-Frontiers on Communications and Networking Symposium}, publisher={IEEE}, proceedings_a={CHINACOM2009-FCN}, year={2009}, month={11}, keywords={OneHop DHT; Leader; Election; Self-stabilization}, doi={10.1109/CHINACOM.2009.5339815} }- Guang-ji WANG
Hai-qiang XUE
Bing WEI
Year: 2009
A Self-Stabilizing Leader Election Algorithm In OneHop DHT
CHINACOM2009-FCN
IEEE
DOI: 10.1109/CHINACOM.2009.5339815
Abstract
OneHop[1] was the first DHT protocol providing the feature which enables DHT to be applied in HLR/HSS that a high fraction of the lookups are solved within only one hop. In this protocol the event in overlay(node joins and leaves)will be disseminated in a hierarchical fashion from slice leader to unit leader and unit leader to normal node. There is little concern about the situation that the leader leaves unexpectedly. Our contribution is introducing a self-stabilizing leader election algorithm to solve the problem, and we will analyze its feature self-stabilization in detail, and prove that leader can be elected even the network is churning(nodes leave and packet lost ).The election algorithm is highly efficient with low cost，the time complexity is O(n)，communication complexity is O(1). All the conclusions are verified by a simulation based on Planetsim[13]