Broadcast

Broadcast (definition): one processes sends a message to all other processes in a system.

A process is correct it will not crash.

A sender is correct: if message is delivered to all correct destinations.

Reliable often means:

  • messages are not lost or duplicated
  • is are delivered in the order in which they were sent

Assumption that:

  • All processes are connected and can exchange messages
  • Each message is uniquely identifiable
  • Recipient can see from the message the sender

Properties:

  • Reliable delivery: messages are eventually delivered when processes are correct
  • No duplication: no message is delivered more than once
  • No creation: no message is delivered unless it was broadcast

Best-effort broadcast #

  • Guarantees that all correct processes deliver the same set of messages if the senders are correct
  • Inherits reliable delivery property by using pp2p: if the sender is correct all destinations receive the message
  • Performance: one communication step
  • Not reliable since not all messages are delivered when the sender crashes

Reliable broadcast #

If messages cannot be delivered to all processes, no process delivers the message to the application.

Agreement: for any message $m$, if a correct process delivers $m$, then every correct process delivers $m$

Uniform broadcast #

Uniform Agreement: for any message $m$, if a correct process delivers $m$, then every correct process delivers $m$

Without perfect failure detector: assume that > N/2 processes are correct then deliver if > N/2 acknowledged

Causal broadcast #

Causal Order: If any process delivers a message $𝑚_2$, then it must have delivered every message $m_1$ such that $m_1 \rightarrow m_2$.