Adaptive Consensus: Enhancing Robustness in Dynamic Environments

Despite being one of the most researched subjects, there are still decades-long gaps in understanding regarding consensus. In particular, a basic concern about the communication complexity of fast randomised Consensus against a (strong) adaptive adversary who crashes processes arbitrarily online remains unresolved in the classic message-passing situation where processes fail. It dates back to the groundbreaking works of B. Joseph and Ben-Or [PODC 1998] and Aspnes and Waarts [JACM 1998, SICOMP 1996]. Later, Hajiaghayi, Kowalski, and Olkowski created an algorithm against adaptive adversary that maintains nearly optimal (up to factor \(O(log^3n))\) time complexity \(O(\sqrt{n} \times log^{5/2} n)\) while reducing the communication gap a nearly linear factor to \(O(\sqrt{n} \times polylog n)\) bits per process. The algorithm worked in three phases namely Phase 1, Phase 2 and Phase 3. In this paper we will focus mainly on the Phase 1 part of the algorithm. The previous algorithm utilized a fixed threshold value to determine whether to broadcast a message containing 1 or to stay silent. We propose a new algorithm that adapts to this threshold dynamically based on the current state of the system to improve responsiveness and efficiency.