IMADA - Department of Mathematics and Computer Science |
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. Host: Joan Boyar SDU HOME | IMADA HOME | Previous Page Daniel Merkle |