License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.5
URN: urn:nbn:de:0030-drops-134909
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13490/
Go to the corresponding LIPIcs Volume Portal

Sheff, Isaac ; Wang, Xinwen ; van Renesse, Robbert ; Myers, Andrew C.

Heterogeneous Paxos

pdf-format:
LIPIcs-OPODIS-2020-5.pdf (0.6 MB)

Abstract

In distributed systems, a group of learners achieve consensus when, by observing the output of some acceptors, they all arrive at the same value. Consensus is crucial for ordering transactions in failure-tolerant systems. Traditional consensus algorithms are homogeneous in three ways:
- all learners are treated equally,
- all acceptors are treated equally, and
- all failures are treated equally. These assumptions, however, are unsuitable for cross-domain applications, including blockchains, where not all acceptors are equally trustworthy, and not all learners have the same assumptions and priorities. We present the first consensus algorithm to be heterogeneous in all three respects. Learners set their own mixed failure tolerances over differently trusted sets of acceptors. We express these assumptions in a novel Learner Graph, and demonstrate sufficient conditions for consensus.
We present Heterogeneous Paxos, an extension of Byzantine Paxos. Heterogeneous Paxos achieves consensus for any viable Learner Graph in best-case three message sends, which is optimal. We present a proof-of-concept implementation and demonstrate how tailoring for heterogeneous scenarios can save resources and reduce latency.

BibTeX - Entry

@InProceedings{sheff_et_al:LIPIcs:2021:13490,
  author =	{Isaac Sheff and Xinwen Wang and Robbert van Renesse and Andrew C. Myers},
  title =	{{Heterogeneous Paxos}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Quentin Bramas and Rotem Oshman and Paolo Romano},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13490},
  URN =		{urn:nbn:de:0030-drops-134909},
  doi =		{10.4230/LIPIcs.OPODIS.2020.5},
  annote =	{Keywords: Consensus, Trust, Heterogeneous Trust}
}

Keywords: Consensus, Trust, Heterogeneous Trust
Collection: 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Issue Date: 2021
Date of publication: 25.01.2021
Supplementary Material: Implementation source: https://github.com/isheff/charlotte-public

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI