000104306 001__ 104306 000104306 005__ 20190316233956.0 000104306 02470 $$2DAR$$a11616 000104306 02470 $$2ISI$$a000249690800003 000104306 037__ $$aARTICLE 000104306 245__ $$aThe Time-Complexity of Local Decision in Distributed Agreement 000104306 269__ $$a2007 000104306 260__ $$c2007 000104306 336__ $$aJournal Articles 000104306 520__ $$aAgreement is at the heart of distributed computing. In its simple form, it requires a set of processes to decide on a common value out of the values they propose. The time-complexity of distributed agreement problems is generally measured in terms of the number of communication rounds needed to achieve a global decision; i.e., for all non-faulty (correct) processes to reach a decision. This paper studies the time-complexity of local decisions in agreement problems, which we de¯ne as the number of communication rounds needed for at least one correct process to decide. We explore bounds for early local decision, that depend on the number f of actual failures (that occur in a given run of an algorithm), out of the maximum number t of failures tolerated (by the algorithm). We ¯rst consider the synchronous message-passing model where we give tight local decision bounds for three variants of agreement: consensus, uniform consensus and (non-blocking) atomic commit. We use these results to (1) show that, for consensus, local decision bounds are not compatible with global decision bounds (roughly speaking, they cannot be reached by the same algorithm), and (2) draw the ¯rst sharp line between the time-complexity of uniform consensus and atomic commit. Then we consider the eventually synchronous model where we give tight local decision bounds for synchronous runs of uniform consensus. (In this model, consensus and uniform consensus are similar, atomic commit is impossible, and one cannot bound the number of rounds to reach a decision in non-synchronous runs of consensus algorithms.) We prove a counter-intuitive result that the early local decision bound is the same as the early global decision bound. We also give a matching early deciding consensus algorithm that is signi¯cantly better than previous eventually synchronous consensus algorithms. 000104306 700__ $$0241834$$g126985$$aDutta, Partha 000104306 700__ $$g105326$$aGuerraoui, Rachid$$0240335 000104306 700__ $$aPochon, Bastian 000104306 773__ $$tSIAM Journal on Computing 000104306 8564_ $$uhttps://infoscience.epfl.ch/record/104306/files/dgp.pdf$$zn/a$$s344884 000104306 909C0 $$xU10407$$0252114$$pDCL 000104306 909CO $$ooai:infoscience.epfl.ch:104306$$qGLOBAL_SET$$pIC$$particle 000104306 937__ $$aLPD-ARTICLE-2007-002 000104306 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL 000104306 980__ $$aARTICLE