Optimality of Simultaneous Consensus with Limited Information Exchange (Extended Abstract)

Work on the development of optimal fault-tolerant Agreement protocols using the logic of knowledge has concentrated on the "full information" approach to information exchange, which is costly with respect to message size. Alpturer, Halpern, and van der Meyden (PODC 2023) introduced the notion of optimality with respect to a limited information exchange, and studied the Eventual Agreement problem in the sending omissions failure model. The present paper studies the Simultaneous Agreement problem for the crash failures model, and a number of limited information exchanges from the literature. In particular, the paper considers information exchanges from a FloodSet protocol (Lynch, Distributed Algorithms 1996), a variant of this in which agents also count the number of failures (Castañeda et al, NETYS 2017), and a variant in which agents associate each agent with a value (Raynal, PRDC 2002). A new information exchange is also introduced that enables decisions to be made at worst one round later than the optimal protocol of Dwork and Moses (I&C 88), but with lower computation cost and space requirements. By determining implementations of a knowledge based program, protocols are derived that are optimal amongst protocols for each of these information exchanges.