Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement
Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Lewis Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira · 2025
Byzantine Agreement (BA) allows n processes to propose input values to reach consensus on a common, valid Lo-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from the protocol. Although strategies like randomization, adaptiveness, and batching have been extensively explored to mitigate the inherent limitations of one-shot agreement tasks, there has been limited progress on achieving good amortized performance for multi-shot agreement, despite its obvious relevance to long-lived functionalities such as state machine replication.