A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement

DOI10.1145/3519270.3538422arXiv2206.05356OpenAlexW4286210490MaRDI QIDQ6202204FDOQ6202204

Authors: Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum 

Publication date: 26 March 2024

Published in: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We study two fundamental problems of distributed computing, consensus and approximate agreement, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem. For a given $n$-process task $Pi$ and a given computational model $M$, we define a new task, called the closure of $Pi$ with respect to $M$. The asynchronous speedup theorem states that if a task $Pi$ is solvable in $tgeq1$ rounds in $M$, then its closure w.r.t. $M$ is solvable in $t-1$ rounds in $M$. We prove this theorem for iterated models, as long as the model allows solo executions. We illustrate the power of our asynchronous speedup theorem by providing a new proof of the wait-free impossibility of consensus using read/write registers, and a new proof of the wait-free impossibility of solving consensus using registers and test&set objects for $n>2$. The proof is merely by showing that, in each case, the closure of consensus (w.r.t. the corresponding model) is consensus itself. Our main application is the study of the power of additional objects, namely test&set and binary consensus, for wait-free solving approximate agreement faster. By analyzing the closure of approximate agreement w.r.t. each of the two models, we show that while these objects are more powerful than read/write registers from the computability perspective, they are not more powerful as far as helping solving approximate agreement faster is concerned.

Full work available at URL: https://arxiv.org/abs/2206.05356

zbMATH Keywords

lower boundscombinatorial topologyconsensusdistributed algorithmsapproximate agreement

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (1)

• The topology of local computing in networks

This page was built for publication: A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202204)