Theory of Computing Systems manuscript No.(will be inserted by the editor)Tight Bounds for Adopt-Commit ObjectsJames Aspnes · Faith EllenOctober 3rd, 2012Abstract We give matching upper and lower bounds of Θminlog mlog log m, nfor the individual step complexity of a wait-free m-valued adopt-commit objectimplemented using multi-writer registers for n anonymous processes. While theupper bound is deterministic, the lower bound holds for randomized adopt-commitobjects as well. Our results are based on showing that adopt-commit objects areequivalent, up to small additive constants, to a simpler class of objects that wecall conflict detectors.Our anonymous lower bound also applies to the individual step complexityof m-valued wait-free anonymous consensus, even for randomized algorithms withglobal coins against an oblivious adversary. The upper bound can be used toslightly improve the cost of randomized consensus against an oblivious adversary.For deterministic non-anonymous implementations of adopt-commit objects,we show a lower bound of Ωminlog mlog log m,√log nlog log nand an upper bound ofOminlog mlog log m, log non the worst-case individual step complexity. For ran-domized non-anonymous implementations, we show that any execution containsat least one process whose steps exceed the deterministic lower bound.Keywords distributed computing · shared memory · anonymity · lower bounds ·covering argument · adopt-commit · randomized consensus1 IntroductionAn adopt-commit object [2,21] or ratifier [3] is a one-shot shared-memory objectthat represents the adopt-commit protocols of Gafni [15] and can be used toimplement round-based protocols for set-agreement and consensus. An m-valuedJames AspnesYale University, Department of Computer ScienceE-mail: [email protected] EllenUniversity of Toronto, Department of Computer Science.E-mail: [email protected] James Aspnes, Faith Ellenadopt-commit object supports a single operation, adoptCommit(u), where u is aninput from a set of m values. The result of this operation is an output of theform (commit, v) or (adopt, v), where the second component is a value from thisset and the first component is a decision bit that indicates whether the processshould decide value v immediately or adopt it as its preferred value in later roundsof the protocol. Improving the performance of adopt-commit objects can improvethe performance of consensus protocols that use them. Lower bounds on adopt-commit objects also yield immediate lower bounds on consensus.The requirements for an adopt-commit object are:1. Validity. The output value of an operation is the input of some (possiblydifferent) operation.2. Termination. With probability 1, each nonfaulty process produces an outputin a finite number of steps, where the probability is taken over the coin tossesperformed by the algorithm.3. Coherence.1If the output of some operation is (commit, v), then every outputis either (adopt, v) or (commit, v).4. Convergence. If all inputs are v, all outputs are (commit, v).These requirements are closely related to the validity, termination, and agree-ment requirements for consensus. The difference is that agreement (which requiresthat all outputs are the same) is replaced by the weaker requirements of coherenceand convergence. As observed in [3], this means that consensus objects satisfy therequirements of adopt-commit objects, if each process returns the decision bit com-mit together with its output value. It follows that lower bounds on adopt-commitobjects immediately give lower bounds on consensus objects.Until now, the best implementations of m-valued adopt-commit objects hadΘ(n) individual step complexity, for n processes [15], or Θ(log m) individual stepcomplexity, for any number of processes [3]. Both these implementations are de-terministic, but the latter is also anonymous. This means that all processes runthe same code. Differences between the behaviour of two different processes canarise only as a result of different input values, (different supplies of random bits,in the case of a randomized protocol), and when they are scheduled. A number ofadvantages of anonymity are discussed in [5].Here, we consider how much further we can improve the complexity of an im-plementation of an adopt-commit object without losing anonymity. We give twosimple, deterministic anonymous protocols for detecting multiple input values,from which we obtain implementations of m-valued adopt-commit objects. Oneof these has O(n) individual step complexity, given an upper bound, n, on thenumber of processes. The other has Olog mlog log mindividual step complexity, forany number of processes. While this is only a small improvement in complexity, weshow a matching lower bound on the individual step complexity of any anonymousimplementation (including randomized implementations against an oblivious ad-versary) of an m-valued adopt-commit object that supports at least Ωlog mlog log mprocesses. Our lower bound also implies a lower bound of Ωlog mlog log mon the1The definition of adopt-commit objects in [2] uses the term agreement for this property.We use agreement instead for the stronger unconditional agreement property of consensusobjects. The term coherence is from [3].Tight Bounds for Adopt-Commit Objects 3individual step complexity for randomized anonymous consensus with sufficientlymany processes, even against an oblivious adversary.We can extend our anonymous bounds to give a partial characterization of theworst-case individual step complexity for non-anonymous adopt-commit objects.We show that deterministic non-anonymous implementations have a worst-case in-dividual step complexity between Ωminlog mlog log m,√log nlog log nand Ominlog mlog log m, log n.2 Conflict detectorsWe introduce a simpler object, a conflict detector, and show that it can be imple-mented from an adopt-commit object. We also show that a conflict detector andregisters can be used to implement an adopt-commit object.An m-valued conflict detector supports a single operation, check(v), withinput v from a set of m values. It returns true (to indicate a conflict) or false (toindicate no conflicts), and has the following two properties:– In any execution that contains a check(v) operation and a check(v0) operationwith v 6= v0, at least one of these two operations returns true.– In any execution in which all check operations