Dynamic Byzantine Reliable Broadcast

Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei TonkikhOPODIS 2020 · OpenReview

TL;DR

This paper introduces the first specification and algorithm for Dynamic Byzantine Reliable Broadcast (DBRB), a crucial primitive for building highly available distributed systems. DBRB allows processes to join and leave a system while still guaranteeing that all non-departing correct processes receive the same messages, even in the face of Byzantine failures. This work is significant because it enables more robust and adaptable distributed applications, like payment systems, in asynchronous environments.

What Problem Does This Paper Address?

Reliable broadcast is a fundamental building block in distributed systems, ensuring that all participating processes agree on a set of messages. It's particularly attractive because it can be implemented deterministically in asynchronous settings, unlike stronger primitives like consensus. However, existing asynchronous reliable broadcast protocols have a major limitation: they assume a static system where processes cannot join or leave. This is a significant drawback for long-lived, highly available applications. This paper tackles the challenge of dynamic reliable broadcast in a Byzantine (adversarial) environment, where processes can join or leave the system, and some processes might behave maliciously.

Methods

The authors introduce a novel specification for Dynamic Byzantine Reliable Broadcast (DBRB) and present an asynchronous algorithm to implement it. The core of their approach involves:

  • View Abstraction: To handle dynamic membership, the system uses a "view" abstraction. A view represents the system's membership at a given point in time. Processes maintain their own views, and the system manages transitions between these views.
  • Sequence of Views: To reconcile differing views among processes due to asynchrony, the algorithm uses a sequence of views. This allows processes to agree on a consistent history of membership changes.
  • Reconfiguration Protocol: A sophisticated protocol is designed for processes to join (DBRB-JOIN) and leave (DBRB-LEAVE) the system. This involves disseminating reconfiguration messages, proposing new views, and converging on a new system membership.
  • Static Reliable Broadcast as a Building Block: The DBRB algorithm leverages a standard, static Byzantine reliable broadcast protocol for its internal communication.
  • Asynchronous Implementation: Crucially, the entire system operates in an asynchronous network, meaning there are no assumptions about message delivery times or process speeds.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Dynamic Membership is Essential for Availability: The paper highlights that for applications aiming for high availability, the ability for processes to join and leave is not just a convenience but a necessity. Precluding this limits the applicability of existing reliable broadcast protocols.
  • View Sequences Bridge Asynchrony and Dynamics: The concept of a sequence of views is a clever way to manage the inherent disagreements about system membership that arise in asynchronous environments when processes are constantly joining and leaving.
  • Tightness of the 2/3 Majority: The paper emphasizes that maintaining a majority of more than 2/3 correct processes is a tight requirement for Byzantine fault tolerance in this dynamic setting. This is a common threshold in Byzantine fault tolerance but is particularly critical here due to the added complexity of membership changes.
  • Impossibility Result for Stronger Properties: A significant theoretical contribution is the proof that in an asynchronous system, even with only one crash-faulty process, it's impossible to achieve a stronger form of reliable broadcast that guarantees delivery to processes even after they have explicitly decided to leave. This clarifies the fundamental limits of what can be achieved.

Key Results

  • First Specification of DBRB: The paper provides the first formal specification for dynamic Byzantine reliable broadcast.
  • Asynchronous Algorithm: An algorithm is presented that implements the DBRB specification in an asynchronous network.
  • Guaranteed Delivery (with caveats): The algorithm ensures that if a correct process broadcasts a message, all other correct processes that do not leave the system will eventually deliver it. Conversely, if a correct process delivers a message, all other correct processes that have not expressed their intent to leave will also deliver it.
  • Theoretical Bound: The paper demonstrates that the 2/3 majority assumption for correct processes is tight.
  • Impossibility Proof: A formal proof shows that stronger delivery guarantees (including to departing processes) are impossible in asynchronous systems with even a single crash-faulty process.

Limitations and Future Work

  • 2/3 Correct Process Assumption: The algorithm relies on the assumption that more than 2/3 of processes in the system are correct at all times. While this is standard for Byzantine fault tolerance, it's a limitation in scenarios with very high churn or Byzantine participation.
  • Formal Proofs Delegated: Detailed formal proofs for correctness are delegated to a full version of the paper.
  • Future Work: The paper suggests that future work could explore relaxing the 2/3 majority assumption or investigating the implications of different fault models. The authors also mention that their work is inspired by previous research on reconfigurable systems and aims to extend these ideas to the Byzantine fault model.

Summary updated

Abstract

Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a completely asynchronous environment, unlike stronger primitives like consensus and total-order broadcast, and yet (ii) reliable broadcast is powerful enough to implement important applications like payment systems. The problem we tackle in this paper is that of dynamic reliable broadcast, i.e., enabling processes to join or leave the system. This property is desirable for long-lived applications (aiming to be highly available), yet has been precluded in previous asynchronous reliable broadcast protocols. We study this property in a general adversarial (i.e., Byzantine) environment. We introduce the first specification of a dynamic Byzantine reliable broadcast (dbrb) primitive that is amenable to an asynchronous implementation. We then present an algorithm implementing this specification in an asynchronous network. Our dbrb algorithm ensures that if any correct process in the system broadcasts a message, then every correct process delivers that message unless it leaves the system. Moreover, if a correct process delivers a message, then every correct process that has not expressed its will to leave the system delivers that message. We assume that more than 2/3 of processes in the system are correct at all times, which is tight in our context. We also show that if only one process in the system can fail - and it can fail only by crashing - then it is impossible to implement a stronger primitive, ensuring that if any correct process in the system broadcasts or delivers a message, then every correct process in the system delivers that message - including those that leave.
BibTeX
@inproceedings{guerraoui2020dynamic,
  author = {Rachid Guerraoui and Jovan Komatovic and Petr Kuznetsov and Yvonne-Anne Pignolet and Dragos-Adrian Seredinschi and Andrei Tonkikh},
  title = {{Dynamic Byzantine Reliable Broadcast}},
  booktitle = {OPODIS},
  year = {2020},
  url = {https://openreview.net/forum?id=PRG4s8wpTO3},
}
Figure