Brief Announcement: Object oriented consensus

Yehuda Afek, James Aspnes, Edo Cohen, and Danny Vainstein. Brief Announcement: Object oriented consensus. ACM Symposium on Principles of Distributed Computing (PODC 2017), July 2017, pp. 367–369.

Abstract

We suggest a template that reveals the structure of many consensus algorithms as a generic procedure. The template builds on a new object, {vacillate-adopt-commit which is an extension of the well known adopt-commit object. In addition we extend Aspnes's conciliator object to a new object that we call a reconciliator. The consensus algorithm template works in rounds of alternating vacillate-adopt-commit and reconciliator operations. The vacillate-adopt-commit object observes the processors' preferences and suggests a preference output with a measure of confidence (vacillate, adopt or commit) on the preference. The reconciliator ensures termination, by providing new preferences for the processors. We show how several key consensus algorithms exactly fit our template. Here we demonstrate the decomposition of Ben-Or's randomized algorithm. The decomposition of the Phase King Byzantine and the Paxos algorithm are given in the full paper. We analyze and compare our template based on vacillate-adopt-commit and reconciliator objects to previous work, suggesting a decomposition of consensus based on adopt-commit and conciliator objects. We claim that the three return values of vacillate-adopt-commit more accurately describe existing algorithms.

BibTeX

Download
@inproceedings{AfekACV2017,
  author    = {Yehuda Afek and
               James Aspnes and
               Edo Cohen and
               Danny Vainstein},
  editor    = {Elad Michael Schiller and
               Alexander A. Schwarzmann},
  title     = {Brief Announcement: Object Oriented Consensus},
  booktitle = {Proceedings of the {ACM} Symposium on Principles of Distributed Computing,
               {PODC} 2017, Washington, DC, USA, July 25-27, 2017},
  pages     = {367--369},
  publisher = {{ACM}},
  year      = {2017},
  url       = {http://doi.acm.org/10.1145/3087801.3087867},
  doi       = {10.1145/3087801.3087867},
  timestamp = {Fri, 21 Jul 2017 13:32:16 +0200},
  biburl    = {http://dblp.dagstuhl.de/rec/bib/conf/podc/AfekACV17},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page