Yehuda Afek, James Aspnes, Edo Cohen, and Danny Vainstein. Object oriented consensus. A brief announcement of a preliminary version of this work appeared in ACM Symposium on Principles of Distributed Computing (PODC 2017), July 2017, pp. 367–369.
Our work focuses on the problem of decomposing consensus algorithms into a common framework composed of simple building blocks. We show that earlier decomposition strategies fall short when applied to some well known algorithms and present a new framework in order to tackle the problem. First we use Aspnes’ framework composed of adopt-commit and conciliator objects in order to decompose the well known Phase-King Byzantine algorithm. We then consider two other well-known algorithms and argue that this framework is insufficient in these (and other) cases and offer a new framework. The framework works in rounds where each consists of two steps. The first step involves an object which detects agreement and the second involves an object that aims at achieving consensus. We denote our newly defined objects as vacillate-adopt-commit and reconciliator. We demonstrate our decomposition on two well known algorithms. Namely, Ben-Or’s Randomized algorithm and the Raft algorithm.
@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 = {https://doi.acm.org/10.1145/3087801.3087867},
doi = {10.1145/3087801.3087867},
timestamp = {Fri, 21 Jul 2017 13:32:16 +0200},
biburl = {https://dblp.dagstuhl.de/rec/bib/conf/podc/AfekACV17},
bibsource = {dblp computer science bibliography, https://dblp.org}
}