A Hierarchical Adaptive Leader Election Algorithm for Crash-Recovery Distributed Systems

• Luiz Antonio Rodrigues UNIOESTE
• Allan Edgard Silva Freitas IFBA
• Elias Procópio Duarte Jr. UFPR
• Vinicius Fulber-Garcia UFPR

Resumo

Leader election is one of the basic building blocks of distributed systems. Multiple different distributed applications employ a leader for decision making or as a coordinator. Traditional leader election algorithms are usually based on all-to-all communications and scales poorly. This work presents a hierarchical adaptive leader election algorithm for distributed systems under the crash-recovery fault model, which allows processes to maintain secondary non-volatile memory. The proposed solution is based on the vCube virtual topology, which presents multiple logarithmic properties, being scalable by definition. One of the contributions of the work is that it is the first to adapt the vCube to the crash-recovery model. The leader is the correct process with the smallest identifier, among those that are most stable, i.e. have failed and recovered the least number of times. The algorithm is adaptive in the sense that processes that change from stable to unstable receive a penalty in order to avoid slowing down the election. Simulation results comparing with the traditional approach show that the proposed solution significantly reduces the number of messages required for leader election, as well as the time to execute a single testing round.

Palavras-chave: Dependability, Fault-Tolerance, Unreliable Failure Detectors, Autonomic Systems, Distributed Algorithms