Optimal Leader Election Scheme for Peer-to-Peer Applications

Leader election is one of the most frequently encountered problems in peer-to-peer applications. However, choosing the best node is not a trivial problem and the obtained performance can dramatically vary depending on it. Another issue is what to measure in the evaluation and comparison of different leader election schemes. It is not clear yet what metrics best capture the performance objective. In this paper, we introduce two performance metrics, the worst link stress (WLS) and the degree of interference (DOI), for the leader election problem, and present a fully distributed, optimal scheme that elects a leader according to the DOI-minimizing criterion in a peer-to-peer network. Our scheme does not require network collaboration, and the communication/computation overhead is low. The only assumption is that the participating nodes can obtain a list of IDs of the nodes in the session through the underlying P2P substrates. After examining the correctness of the algorithm, we present simulation results demonstrating the benefits of the optimal leader election scheme. Through the simulation results, we conclude that the algorithm is simple yet effective in achieving the design goals, particularly in reducing (1) the worst link stress and balancing load in the network, and (2) the network bandwidth usage.