A speedup theorem for asynchronous computation with applications to consensus and approximate agreement

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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Π</mml:mi> </mml:math> and a given computational model M , we define a new task, called the closure of $$\Pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Π</mml:mi> </mml:math> with respect to M . The asynchronous speedup theorem states that if a task $$\Pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Π</mml:mi> </mml:math> is solvable in $$t\ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> rounds in M , then its closure w.r.t. M is solvable in $$t-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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&amp;set objects for $$n&gt;2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . 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&amp;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.