Broadcasts

Primitives

• broadcast(m) : p broadcasts m to the group
• deliver(m) : delivers m to p

Issues

Ensure two properties:

• delivery guarantee
• ordering guarantee

Delivery guarantees

Best-effort

With best-effort broadcast, the burden of ensuring reliability is only on the sender. Therefore, the remaining processes do not have to be concerned with enforcing the reliability of received messages. On the other hand no delivery guarantees are offered in case the sender fails. Best-effort broadcast is characterized by the following three properties:

• validity is a liveness property, where p1 and p2 are correct, a message m, broadcasted by p1 eventually gets delivered by p2, whereas the;
• no duplication property, ensuring that messages get delivered at most once, and the;
• no creation property, where only message broadcasted by a process, are safety properties

They descend directly from the corresponding properties of perfect point-to-point links. Note that broadcast messages are implicitly addressed to all processes. Remember also that messages are unique, that is, no process ever broadcasts the same message twice and furthermore, no two processes ever broadcast the same message.

Process P :
  BestEffort_broadcast(m)
    send m to all including me

upon recv(m) :
    BestEffort_deliver(m)

Reliable broadcast (fiable)

Best-effort broadcast ensures the delivery of messages as long as the sender does not fail. If the sender fails, some processes might deliver the message and others might not deliver it. In other words, they do not agree on delivery of the message. Ensuring agreement even when the sender fails is an important property for many practical applications that rely on broadcast. The abstraction of (regular) reliable broadcast provides exactly this stronger notion of reliability.

Specification

Intuitively, the semantics of a reliable broadcast algorithm ensure that the correct processes agree on the set of messages they deliver, even when the sender of the messages crash during the transmission. It should be noted that a sender may crash before being able to transmit the message, in which case no process will deliver it.

• validity if a correct process broadcasts message m then all correct process delivers m
• agreement if a correct process delivers message m then all the correct members deliver m
• completeness Messages are delivered at most once to every correct process, if it was broadcasted by a process

Idea

If one correct process delivers the broadcasted message m, every correct process delivers m.

Algo

Process P: 
  Local Variable: 
    rec= new();

    real_bcast(m) 
      timestamp m with sender_id and sequence #
      send m to every process
    
    upon recv(m) do
      if m not in rec 
        rec.add(m)
      if sender(m) != P 
        send m to every process but P
      real_deliver(m)

Summary

• [+] No need for fault detection
• [+] Algo works in any temporal model
• [-] Bad perf, n(n-1) messages per bcast
• [-] Makes it useless irl
• No guarantees of order

Uniform Reliable broadcast (fiable uniforme)

With regular reliable broadcast, the semantics just require the correct processes to deliver the same set of messages, regardless of what messages have been delivered by faulty processes. In particular, a process that rb-broadcast a message might rb-deliver it and then crash, before the best-effort broadcast abstraction can even beb-deliver the message to any other process. There are cases where such behavior causes problems because even a process that rb-delivers a message and later crashes may bring the application into a inconsistent state. We now introduce a stronger definition of reliable broadcast, called uniform reliable broadcast. This definition is stronger in the sense that it guarantees that the set of messages delivered by faulty processes is always a subset of the messages delivered by correct processes. Many other abstractions also have such uniform variants.

Uniformity ensures compliance of specifications to both correct and faulty processes.

Specs

• validite si un processus correct diffuse le message m, alors tous les processus corrects delivrent m
• accord uniforme si un processus (correct ou fautif) delivre le message m, alors tous les membres corrects delivrent m
• integrite uniforme Un message m est delivre au plus une fois a tout processus (correct ou fautif), et seulement s’il a ete diffuse par un processus

Order guarantees

FIFO

The specification of reliable broadcast does not state anything about the order in which multiple messages are delivered. A FIFO-order is one of the simplest possible orderings and guarantees that messages from the same sender are delivered in the same sequence as they were broadcast by the sender. Note, this does not affect messages from different senders. The FIFO-order (reliable) broadcast abstraction is obtained from the (regular) reliable broadcast abstraction by extending it with the FIFO delivery property. A uniform variation of FIFO-order (reliable) broadcast with causal order can be obtained in the same way. For brevity we usually skip the term reliable refer to a FIFO-order broadcast abstraction.

Causal

The causal order property for a broadcast abstraction ensures that messages are delivered such that they respect all cause-effect relations. The happenned-before relation expresses all such dependencies. This relation is also called the causal order relation, when applied to messages exchanged among processes and expressed by broadcast and delivery events. In this case, we say that a message m1 may have potentially caused another message m2, denoted as m1 -> m2, if any of the following relations apply:

• some process p broadcasts m1 before it broadcasts m2
• some process p delivers m1 and subsequently broadcasts m2; or
• there exists some message m' such that m1 -> m' and m' -> m2

As is evident from the first condition of causal order, the causal delivery property implies the FIFO order property. Hence, a causal-order broadcast primitive provides also FIFO-order reliable broadcast.

Both causal and FIFO orders are only partial orders; there’s no properties about the delivery order for concurrent bcasts

Total

The messages are delivered in the same order to all the destinaties.