How fast can you converge towards a consensus value?
In their recent work, Matthias Fuegger (LMF), Thomas Nowak (LISN), and Manfred Schwarz (TU Wien) study this question in distributed systems where nodes start from an initial value and seek to converge towards a common consensus value. The paper shows that deceptively simple algorithms are optimal and provides tight lower bounds.
Out now in JACM: https://dl.acm.org/doi/10.1145/3485242