Review: A Modular Approach to Fault-Tolerant Broadcasts and Related Problems

    Fault-tolerant broadcasts and consensus have been widely studied, and they are important
parts to design fault-tolerant distributed applications. This paper explores these topics, and expose
these material in a coherent way. First, they start with weakest communication primitive, Reliable
Broadcast, and imposes additional requirements to create a stronger broadcast algorithm. Second,
they explore the paradigm of Consensus that is used to solve many distributed problems, such as
leader election or value agreement.
    The goal of the algorithms are to prevent inconsistency on faulty probability, or at least the
contamination of the correct ones in many situations. This is possible to all algorithms presented
here, and for all benign failures, but they have their limitations. In case of arbitrary faults, neither
inconsistency nor contamination can be prevented by these algorithms. The broadcast uses a
common point-to-point network.
    The several broadcasts algorithms explained here (FIFO, Causal, Atomic, FIFO Atomic, Causal
Atomic Broadcast) were created to deal with crash, or omission, or arbitrary faults, sometimes in
synchronous or asynchronous communication. They show that algorithms are correct when they all
satisfy the properties of Validity, Agreement, and Integrity. The mentioned algorithms were built
on top of Reliable Broadcast. Therefore, they all satisfy the properties of the reliable algorithm.
We can also place message delivery time on these broadcasts, turning them into timed broadcasts,
or add an uniform property so that the properties of broadcast algorithm would be imposed on
faulty processes. All the algorithms are built modularly. The authors show that given any Reliable
Broadcast algorithm, we can obtain any other broadcast algorithm by adding functionalities. E.g,
   • FIFO order + Reliable Broadcast = FIFO Broadcast;

   • Causal order + FIFO Broadcast = Causal Broadcast;

   • Total Order + Reliable, FIFO, Causal Broadcast = Atomic Broadcast.
The authors detail all the transformations that algorithms suffer to be turned into a new one, and
they proof that the algorithms respect all properties.
   They show that the consensus can be achieved from the Atomic Broadcast, and also showed that
Reliable Broadcast and Consensus can be transformed into Atomic Broadcast. In asynchronous
point-to-point networks, Atomic Broadcast can be implemented using failure detectors and randomized algorithms.

  All the algorithms have limitations and work on fault assumptions. The authors do not compare
the algorithms, do not list what faults they can handle, and do not show impossible results. They
only show the correctness of the algorithms, and how they respect all the properties. This makes
hard to understand and compare their limitations. This is the most significant point that the
authors do not address in the paper.
    Despite this negative point, the paper is interesting to read, and I have learnt the basics of
distributed algorithms. This paper is a compendium of broadcast algorithms, and consensus. The
authors start giving a beginners’ lesson about distributed system, and dwells into the main topics
where he writes a concise explanation. In overall, this is an important introductory paper.
    Nowadays, these algorithms does not follow the top of the edge research, but they are the basic
structure where all the new creation came from. The paper refers a big list of related work derived
from these ideas.
    In conclusion, this paper shows an insightful description of broadcast algorithms, and consensus,
and shows the importance of these topics in distributed systems. The contribution of this paper
comes from the fact that shows that we can create new algorithms by adding new functionalities
to an existent and modular broadcast algorithm.