View Full Document

Tight Bounds for Adopt-Commit Objects



View the full content.
View Full Document
View Full Document

5 views

Unformatted text preview:

Theory of Computing Systems manuscript No will be inserted by the editor Tight Bounds for Adopt Commit Objects James Aspnes Faith Ellen October 3rd 2012 Abstract We give matching upper and lower bounds of min log m log log m n for the 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 Our results are based on showing that adopt commit objects are equivalent up to small additive constants to a simpler class of objects that we call conflict detectors Our anonymous lower bound also applies to 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 be used to slightly improve the cost of randomized consensus against an oblivious adversary For deterministic non anonymous implementations of adopt commit objects n we show a lower bound of min logloglogmm loglog and an upper bound of log n log m O min log log m log n on the worst case individual step complexity For randomized non anonymous implementations we show that any execution contains at least one process whose steps exceed the deterministic lower bound Keywords distributed computing shared memory anonymity lower bounds covering argument adopt commit randomized consensus 1 Introduction An adopt commit object 2 21 or ratifier 3 is a one shot shared memory object that represents the adopt commit protocols of Gafni 15 and can be used to implement round based protocols for set agreement and consensus An m valued James Aspnes Yale University Department of Computer Science E mail aspnes cs yale edu Faith Ellen University of Toronto Department of Computer Science E mail faith cs toronto edu 2 James Aspnes Faith Ellen adopt commit object supports a single operation adoptCommit u where u is an input from a set of m values



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Tight Bounds for Adopt-Commit Objects and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Tight Bounds for Adopt-Commit Objects and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?