Eastern Great Lakes Theory Workshop Talk

Tight Bounds for Anonymous Adopt-Commit Objects

Faith Ellen, University of Toronto

Saturday, September 10, 1:30-2:30pm

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.

Joint work with Jim Aspnes (SPAA 2011).

Speaker Bio

Faith Ellen is a Professor of Computer Science at the University of Toronto. She received her B.Math. in Pure Mathematics and Computer Science in 1977 from University of Waterloo, followed by her M.Math. in Computer Science. In 1982, she received her Ph.D. in Computer Science from the University of California, Berkeley, and from 1983 to 1986, she was an Assistant Professor in the Computer Science Department at the University of Washington in Seattle. She joined the Department of Computer Science at the University of Toronto in 1986. Professor Ellen was the vice-chair of SIGACT from 1997 to 2001 and the chair of the steering committee for PODC from 2006 to 2009. Her main area of research is studying the complexity of problems in distributed computing, with the goal of understanding how parameters of various models affect their computational power.

< Schedule < EaGL-IV homepage