(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Tight Bounds for Anonymous Adopt-Commit Objects

Faith Ellen
Department of Computer Science
University of Toronto, Canada

Tuesday, 21 June, 2011 at 14:15
Auditorium U49E

ABSTRACT

Most known distributed algorithms for randomized consensus from multi-writer registers proceed in rounds, each of which performs two tasks. The first is to ensure agreement with some nonzero probability. The second is to detect whether agreement has been reached. An adopt-commit object is a formal specification of this second task. We give matching upper and lower bounds of min{log m / log log m, n}, to within constant factors, for the space and individual step complexity of a wait-free m-valued adopt-commit object implemented using multi-writer registers for n anonymous processes.While the upper bound is deterministic, the lower bound holds for randomized adopt-commit objects as well.

It follows that the same lower bound holds on the individual step complexity of m-valued wait-free anonymous consensus, even for randomized algorithms with global coins against an oblivious adversary. The upper bound can also be used to slightly improve a previous upper bound on the cost of randomized consensus.

This work is joint with James Aspnes and will appear at SPAA 2011.

Host: Joan Boyar


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle