Quorum Systems in Permissionless Networks

Cachin, Christian; Losa, Giuliano; Zanolini, Luca (2022). Quorum Systems in Permissionless Networks. Leibniz International Proceedings in Informatics Schloss Dagstuhl - Leibniz-Zentrum für Informatik 10.4230/LIPIcs.OPODIS.2022.17

[img]
Preview
Text
2211.05630.pdf - Published Version
Available under License Creative Commons: Attribution (CC-BY).

Download (303kB) | Preview

Fail-prone systems, and their quorum systems, are useful tools for the design of distributed algorithms. However, fail-prone systems as studied so far require every process to know the full system membership in order to guarantee safety through globally intersecting quorums. Thus, they are of little help in an open, permissionless setting, where such knowledge may not be available. We propose to generalize the theory of fail-prone systems to make it applicable to permissionless systems. We do so by enabling processes not only to make assumptions about failures, but also to make assumptions about the assumptions of other processes. Thus, by transitivity, processes that do not even know of any common process may nevertheless have intersecting quorums and solve, for example, reliable broadcast. Our model generalizes existing models such as the classic fail-prone system model [Malkhi and Reiter, 1998] and the asymmetric fail-prone system model [Cachin and Tackmann, OPODIS 2019]. Moreover, it gives a characterization with standard formalism of the model used by the Stellar blockchain.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Institute of Computer Science (INF) > Cryptology and Data Security Group
08 Faculty of Science > Institute of Computer Science (INF)

UniBE Contributor:

Cachin, Christian, Zanolini, Luca

Subjects:

000 Computer science, knowledge & systems
500 Science > 510 Mathematics

ISSN:

1868-8969

ISBN:

978-3-95977-265-5

Publisher:

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Language:

English

Submitter:

Christian Cachin

Date Deposited:

30 Mar 2023 13:01

Last Modified:

25 Mar 2024 08:01

Publisher DOI:

10.4230/LIPIcs.OPODIS.2022.17

Additional Information:

26th International Conference on Principles of Distributed Systems (OPODIS)

BORIS DOI:

10.4230/lipics.opodis.2022.17

URI:

https://boris.unibe.ch/id/eprint/181058

Actions (login required)

Edit item Edit item
Provide Feedback