Publication

Dynamic Byzantine Reliable Broadcast

Rachid Guerraoui, Jovan Komatovic, Dragos-Adrian Seredinschi, Andrei Tonkikh
2021
Conference Papers

Résumé

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. LIPIcs, Vol. 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), pages 23:1-23:18

Source officielle

Rachid Guerraoui, Jovan Komatovic, Dragos-Adrian Seredinschi, Andrei Tonkikh
2021
Conference Papers

Résumé

Source officielle

Concepts associés (32)

Asynchronous I/O

In computer science, asynchronous I/O (also non-sequential I/O) is a form of input/output processing that permits other processing to continue before the transmission has finished. A name used for asynchronous I/O in the Windows API is overlapped I/O. Input and output (I/O) operations on a computer can be extremely slow compared to the processing of data. An I/O device can incorporate mechanical devices that must physically move, such as a hard drive seeking a track to read or write; this is often orders of magnitude slower than the switching of electric current.

Business Process Management

Le Business Process Management (BPM), ou Gestion des Processus Métiers, permet d’avoir une vue d’ensemble de processus métiers de l’organisation et de leurs interactions pour les optimiser et les automatiser autant que possible. Pour ce faire, il faut analyser le fonctionnement réel de l'entreprise afin de le modéliser informatiquement, par exemple avec le formalisme BPMN et les outils associés. Dans une deuxième étape, les processus automatisés, même partiellement, font l'objet d'un monitoring (Cf.

Système d'exploitation distribué

Un système d'exploitation distribué est une couche logicielle au dessus d'un ensemble de nœuds de calculs indépendants, communiquant par un système de réseau propre ou général. Chaque nœud comprend dans ce type de système d'exploitation un sous ensemble de l’agrégat global. Chaque nœud comporte son propre noyau servant à contrôler le matériel et les couches basses des communications en réseau. Des logiciels de plus haut niveau sont chargés de coordonner les activités collaboratives de l'ensemble de la grappe et des éléments de chacun de ces nœuds.

Afficher plus

Publications associées (29)

Planetary-Scale Byzantine Fault Tolerance

Matteo Monti

The scale and pervasiveness of the Internet make it a pillar of planetary communication, industry and economy, as well as a fundamental medium for public discourse and democratic engagement. In stark contrast with the Internet's decentralized infrastructur ...

EPFL2024

Reliable Microsecond-Scale Distributed Computing

Athanasios Xygkis

The landscape of computing is changing, thanks to the advent of modern networking equipment that allows machines to exchange information in as little as one microsecond. Such advancement has enabled microsecond-scale distributed computing, where entire dis ...

EPFL2023

Building Strongly-Consistent Systems Resilient to Failures, Partitions, and Slowdowns

Cristina Basescu

Distributed systems designers typically strive to improve performance and preserve availability despite failures or attacks; but, when strong consistency is also needed, they encounter fundamental limitations. The bottleneck is in replica coordination, whi ...

EPFL2023

Afficher plus