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.CONCUR.2019.33
URN: urn:nbn:de:0030-drops-109358
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10935/
Go to the corresponding LIPIcs Volume Portal

Bertrand, Nathalie ; Konnov, Igor ; Lazic, Marijana ; Widder, Josef

Verification of Randomized Consensus Algorithms Under Round-Rigid Adversaries

pdf-format:
LIPIcs-CONCUR-2019-33.pdf (0.7 MB)

Abstract

Randomized fault-tolerant distributed algorithms pose a number of challenges for automated verification: (i) parameterization in the number of processes and faults, (ii) randomized choices and probabilistic properties, and (iii) an unbounded number of asynchronous rounds. This combination makes verification hard. Challenge (i) was recently addressed in the framework of threshold automata.
We extend threshold automata to model randomized consensus algorithms that perform an unbounded number of asynchronous rounds. For non-probabilistic properties, we show that it is necessary and sufficient to verify these properties under round-rigid schedules, that is, schedules where processes enter round r only after all processes finished round r-1. For almost-sure termination, we analyze these algorithms under round-rigid adversaries, that is, fair adversaries that only generate round-rigid schedules. This allows us to do compositional and inductive reasoning that reduces verification of the asynchronous multi-round algorithms to model checking of a one-round threshold automaton. We apply this framework and automatically verify the following classic algorithms: Ben-Or's and Bracha's seminal consensus algorithms for crashes and Byzantine faults, 2-set agreement for crash faults, and RS-Bosco for the Byzantine case.

BibTeX - Entry

@InProceedings{bertrand_et_al:LIPIcs:2019:10935,
  author =	{Nathalie Bertrand and Igor Konnov and Marijana Lazic and Josef Widder},
  title =	{{Verification of Randomized Consensus Algorithms Under Round-Rigid Adversaries}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Wan Fokkink and Rob van Glabbeek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10935},
  URN =		{urn:nbn:de:0030-drops-109358},
  doi =		{10.4230/LIPIcs.CONCUR.2019.33},
  annote =	{Keywords: threshold automata, counter systems, parameterized verification, randomized distributed algorithms, Byzantine faults}
}

Keywords: threshold automata, counter systems, parameterized verification, randomized distributed algorithms, Byzantine faults
Collection: 30th International Conference on Concurrency Theory (CONCUR 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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