Relaxed Reliable Broadcast for Decentralized Trust

João Paulo Bezerra; Petr Kuznetsov; Alice Koroleva

doi:10.1007/978-3-031-17436-0_8

Relaxed Reliable Broadcast for Decentralized Trust

João Paulo Bezerra
, Petr Kuznetsov
, Alice Koroleva

Institut Polytechnique de Paris
St. Petersburg National Research University of Information Technologies

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

Reliable broadcast is a fundamental primitive, widely used as a building block for data replication in distributed systems. Informally, it ensures that system members deliver the same values, even in the presence of equivocating Byzantine participants. Classical broadcast protocols are based on centralized (globally known) trust assumptions defined via sets of participants (quorums) that are likely not to fail in system executions. In this paper, we consider the reliable broadcast abstraction in decentralized trust settings, where every system participant chooses its quorums locally. We introduce a class of relaxed reliable broadcast abstractions that perfectly match these settings. We then describe a broadcast protocol that achieves optimal consistency, measured as the maximal number of different values from the same source that the system members may deliver. In particular, we establish how this optimal consistency is related to parameters of a graph representation of decentralized trust assumptions.

Original language	English
Title of host publication	Networked Systems - 10th International Conference, NETYS 2022, Proceedings
Editors	Mohammed-Amine Koulali, Mira Mezini
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	104-118
Number of pages	15
ISBN (Print)	9783031174353
DOIs	https://doi.org/10.1007/978-3-031-17436-0_8
Publication status	Published - 1 Jan 2022
Event	10th International Conference on Networked Systems, NETYS 2022 - Virtual, Online Duration: 17 May 2022 → 19 May 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13464 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Networked Systems, NETYS 2022
City	Virtual, Online
Period	17/05/22 → 19/05/22

Keywords

Consistency measure
Decentralized trust
Quorum systems
Reliable broadcast

Access to Document

10.1007/978-3-031-17436-0_8

Cite this

Bezerra, J. P., Kuznetsov, P., & Koroleva, A. (2022). Relaxed Reliable Broadcast for Decentralized Trust. In M.-A. Koulali, & M. Mezini (Eds.), Networked Systems - 10th International Conference, NETYS 2022, Proceedings (pp. 104-118). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13464 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-17436-0_8

Bezerra, João Paulo ; Kuznetsov, Petr ; Koroleva, Alice. / Relaxed Reliable Broadcast for Decentralized Trust. Networked Systems - 10th International Conference, NETYS 2022, Proceedings. editor / Mohammed-Amine Koulali ; Mira Mezini. Springer Science and Business Media Deutschland GmbH, 2022. pp. 104-118 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{60e773c3f1614097a06fcbe00cf874a9,

title = "Relaxed Reliable Broadcast for Decentralized Trust",

abstract = "Reliable broadcast is a fundamental primitive, widely used as a building block for data replication in distributed systems. Informally, it ensures that system members deliver the same values, even in the presence of equivocating Byzantine participants. Classical broadcast protocols are based on centralized (globally known) trust assumptions defined via sets of participants (quorums) that are likely not to fail in system executions. In this paper, we consider the reliable broadcast abstraction in decentralized trust settings, where every system participant chooses its quorums locally. We introduce a class of relaxed reliable broadcast abstractions that perfectly match these settings. We then describe a broadcast protocol that achieves optimal consistency, measured as the maximal number of different values from the same source that the system members may deliver. In particular, we establish how this optimal consistency is related to parameters of a graph representation of decentralized trust assumptions.",

keywords = "Consistency measure, Decentralized trust, Quorum systems, Reliable broadcast",

author = "Bezerra, \{Jo{\~a}o Paulo\} and Petr Kuznetsov and Alice Koroleva",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 10th International Conference on Networked Systems, NETYS 2022 ; Conference date: 17-05-2022 Through 19-05-2022",

year = "2022",

month = jan,

day = "1",

doi = "10.1007/978-3-031-17436-0\_8",

language = "English",

isbn = "9783031174353",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "104--118",

editor = "Mohammed-Amine Koulali and Mira Mezini",

booktitle = "Networked Systems - 10th International Conference, NETYS 2022, Proceedings",

}

Bezerra, JP, Kuznetsov, P & Koroleva, A 2022, Relaxed Reliable Broadcast for Decentralized Trust. in M-A Koulali & M Mezini (eds), Networked Systems - 10th International Conference, NETYS 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13464 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 104-118, 10th International Conference on Networked Systems, NETYS 2022, Virtual, Online, 17/05/22. https://doi.org/10.1007/978-3-031-17436-0_8

Relaxed Reliable Broadcast for Decentralized Trust. / Bezerra, João Paulo; Kuznetsov, Petr; Koroleva, Alice.
Networked Systems - 10th International Conference, NETYS 2022, Proceedings. ed. / Mohammed-Amine Koulali; Mira Mezini. Springer Science and Business Media Deutschland GmbH, 2022. p. 104-118 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13464 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Relaxed Reliable Broadcast for Decentralized Trust

AU - Bezerra, João Paulo

AU - Kuznetsov, Petr

AU - Koroleva, Alice

PY - 2022/1/1

Y1 - 2022/1/1

N2 - Reliable broadcast is a fundamental primitive, widely used as a building block for data replication in distributed systems. Informally, it ensures that system members deliver the same values, even in the presence of equivocating Byzantine participants. Classical broadcast protocols are based on centralized (globally known) trust assumptions defined via sets of participants (quorums) that are likely not to fail in system executions. In this paper, we consider the reliable broadcast abstraction in decentralized trust settings, where every system participant chooses its quorums locally. We introduce a class of relaxed reliable broadcast abstractions that perfectly match these settings. We then describe a broadcast protocol that achieves optimal consistency, measured as the maximal number of different values from the same source that the system members may deliver. In particular, we establish how this optimal consistency is related to parameters of a graph representation of decentralized trust assumptions.

AB - Reliable broadcast is a fundamental primitive, widely used as a building block for data replication in distributed systems. Informally, it ensures that system members deliver the same values, even in the presence of equivocating Byzantine participants. Classical broadcast protocols are based on centralized (globally known) trust assumptions defined via sets of participants (quorums) that are likely not to fail in system executions. In this paper, we consider the reliable broadcast abstraction in decentralized trust settings, where every system participant chooses its quorums locally. We introduce a class of relaxed reliable broadcast abstractions that perfectly match these settings. We then describe a broadcast protocol that achieves optimal consistency, measured as the maximal number of different values from the same source that the system members may deliver. In particular, we establish how this optimal consistency is related to parameters of a graph representation of decentralized trust assumptions.

KW - Consistency measure

KW - Decentralized trust

KW - Quorum systems

KW - Reliable broadcast

U2 - 10.1007/978-3-031-17436-0_8

DO - 10.1007/978-3-031-17436-0_8

M3 - Conference contribution

AN - SCOPUS:85140477275

SN - 9783031174353

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 104

EP - 118

BT - Networked Systems - 10th International Conference, NETYS 2022, Proceedings

A2 - Koulali, Mohammed-Amine

A2 - Mezini, Mira

PB - Springer Science and Business Media Deutschland GmbH

T2 - 10th International Conference on Networked Systems, NETYS 2022

Y2 - 17 May 2022 through 19 May 2022

ER -

Bezerra JP, Kuznetsov P, Koroleva A. Relaxed Reliable Broadcast for Decentralized Trust. In Koulali MA, Mezini M, editors, Networked Systems - 10th International Conference, NETYS 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 104-118. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-17436-0_8