Broadcast
Broadcast
s
s
Distributed
Distributed
operating systems
operating systems
Specifications and
Specifications and
algorithms
algorithms
Specifications
Specifications
Reliable Broadcast
FIFO Broadcast
Causal Precedence
Causal Broadcast
Atomic Broadcast
FIFO Atomic Broadcast
Causal Atomic Broadcast
Timed Broadcasts
Uniform Broadcasts
Relationship among Broadcast Primitives
Reliable Broadcast
Reliable Broadcast
A
Reliable Broadcast
is a broadcast that satisfies the following
three properties:
Validity:
If a correct process broadcasts a message m, then
all correct processes eventually deliver m.
Agreement:
If a correct process delivers a message m,
then all correct processes eventually deliver m.
Integrity:
For any message m, every correct process
delivers m at most once, and only if m was previously
broadcast by sender(m).
FIFO Broadcast
FIFO Broadcast
A
FIFO Broadcast
is a
Reliable Broadcast
that satisfies the
following requirement on message delivery:
FIFO Order:
If a process broadcasts a message m before it
broadcasts a message m, then no correct process delivers
m unless it has previously delivered m.
P
1
P
2
P
3
P
4
m
m
m
m
m
Causal
Causal
Precedence
Precedence
An execution of a broadcast or deliver primitive by a process is
called an
event
. We say that event e
causally precedes
event f, denoted e f, if and only if:
1. a process executes both e and f, in that order, or
2. e is the broadcast of some message m and f is the delivery
of m, or
3. there is an event h, such that e h and h f.
Causal Broadcast
Causal Broadcast
A
Causal Broadcast
is a
Reliable Broadcast
that satisfies the
following requirements:
Causal Order:
If the broadcast of a message m causally
precedes the broadcast of a message m
, then no correct
process delivers m
unless it has previously delivered m.
P
1
P
2
P
3
m
m
m
m
Atomic Broadcast
Atomic Broadcast
An
Atomic Broadcast
is a
Reliable Broadcast
that satisfied the
following requirement:
Total Order:
If correct processes p and q both deliver
messages m and m
, then p delivers m before m
if and only
if q delivers m before m
.
P
1
p =
P
2
q =
P
3
P
4
m
m
m
m
m
FIFO Atomic Broadcast
FIFO Atomic Broadcast
A
FIFO Atomic Broadcast
is a
Reliable Broadcast
that satisfies
both the
FIFO
and
Total Order
requirements.
m
m
P
1
P
2
P
3
P
4
m
m
Causal Atomic Broadcast
Causal Atomic Broadcast
A
Causal Atomic Broadcast
is a
Reliable Broadcast
that
satisfies both the
Causal
and
Total Order
requirements.
Incorrect process
P
1
Incorrect process
P
2
P
3
m
m
Is it a
FIFO Atomic Broadcast
?
Timeliness and Timed Broadcasts
Timeliness and Timed Broadcasts
(Real-Time) -Timeliness:
There is a known constant
such that if the broadcast of m is initiated at real time t, no
correct process delivers m after real-time t + .
(Local-Time) -Timeliness:
There is a known constant
such that no correct process p delivers a message m after
local time ts(m) + on p’s clock.
A broadcast that satisfies either version of the -Timeliness
property is called a
Time Broadcast
.
ts(m)
t
Uniform Broadcasts
Uniform Broadcasts
1
1
Uniform Agreement:
If a process (whether correct or faulty)
delivers a message m, then all correct processes eventually
deliver m.
Uniform Integrity:
For any message m, every process
(whether correct or faulty) delivers m at most once, and
only if some process broadcast m.
Uniform Local-Time -Timeliness:
There is a known
constant such that no process p (whether correct or
faulty) delivers a message m after local time ts(m) + on
p’s clock.
Uniform Broadcasts
Uniform Broadcasts
2
2
Uniform FIFO Order:
If a process broadcasts a message m
,
then no process (whether correct or faulty) delivers m
unless it has previously delivered m.
Uniform Causal Order:
If the broadcast of a message m
causally precedes the broadcast of a message m
, then no
process (whether correct or faulty) delivers m
unless it has
previously delivered m.
Uniform Total Order:
If any processes p and q (whether
correct or faulty) both deliver messages m and m
, then p
delivers m before m
if and only if q delivers m before m
.
For each type of broadcast we define a Uniform counterpart,
by replacing its
Agreement
,
Integrity
,
Order
and
-Timeless
properties by the corresponding Uniform ones.
Relationship among Broadcast Primitives
Relationship among Broadcast Primitives
Reliable
Broadcast
Atomic
Broadcast
FIFO Atomic
Broadcast
Causal
Atomic
Broadcast
FIFO
Broadcast
Causal
Broadcast
Total Order
Total Order
Total Order
FIFO order
FIFO order
Causal Order
Causal Order
Algorithms
Algorithms
RB Algorithm (Reliable Broadcast)
FB Algorithm (FIFO Broadcast)
CB Algorithm (Causal Broadcast)
ABTR Algorithm (Timed Atomic Broadcast using Timed
Reliable Broadcast)
TCAB Algorithm (Timed Causal Atomic Broadcast)
CABFAB Algorithm (Causal Atomic Broadcast using FIFO
Atomic Broadcast)
Reliable Broadcast
Reliable Broadcast
We assume that the send(m) and receive(m) primitives used
to transmit a message m over a link (say, from process p to
process q) satisfy the following two properties:
Validity:
If p sends m to q, and both p and q and the link
between them are correct, then q eventually receives m.
Uniform Integrity:
For any message m, q receives m at
most once from p, and only if p previously sent m to q.
Reliable Broadcast Algorithm
Reliable Broadcast Algorithm
The algorithm uses the send and receive primitives. It is based on
message diffusion.
We denote by broadcast(T, m) and deliver(T, m), the two primitives
corresponding to a broadcast of type T (
R
- Reliable,
F
- FIFO,
C
-
Causal,
FA
– FIFO Atomic,
CA
– Causal Atomic).
RB Algorithm
Every process p executes the following:
1.
To execute broadcast(R, m):
2.
tag m with sender(m) and seq# (m)
/* These tags make m unique
*/
3.
send(m) to all neighbors including p
4.
deliver(R, m) occurs as follows:
5.
upon receive(m) do
6.
if p has not previously executed deliver(R, m)
7.
then
8.
if sender(m) p then send(m) to all neighbors
9.
deliver(R, m)
Reliable Broadcast Algorithm
Reliable Broadcast Algorithm
Theorem
Consider an asynchronous system where every
two correct processes are connected via a path of processes
and links that never fail. The RB algorithm is a Reliable
Broadcast for such a system.
Theorem
Consider an asynchronous system where
processes only fail by receive omission failures, and every
process (whether correct or faulty) is connected to every
correct process via a path of processes and links that never
fail. The RB algorithm is a Uniform Reliable Broadcast for
such a system.
Timed Reliable Broadcast
Timed Reliable Broadcast
Assume that the underlying network satisfies the following
properties:
1. At most f processes can fail.
2. Every two correct processes are connected via a path of
length at most d, consisting entirely of correct processes and
links.
3. There is known upper bound
on message delay.
4. The time to execute a local step is taken to be zero.
Theorem
With general omission failures and assumptions 1-
4, the RB algorithm is a (Real-Time) Timed Reliable Broadcast
with
= (f + d)
.
Using Reliable Broadcast to build FIFO
Using Reliable Broadcast to build FIFO
Broadcast
Broadcast
1
1
FB Algorithm
Every process p executes the following:
1.
Initialization:
2.
msgBag :=
/* set of messages that p R-delivered but not yet F-
delivered */
3.
next[q] := 1 for all q
/* sequence number of next message from q
that p will F-Deliver */
4.
To execute broadcast(F, m):
5.
broadcast(R, m)
6.
deliver(F, m) occurs as follows:
7.
upon deliver(R, m) do
8.
q := sender(m)
9.
msgBag := msgBag {m}
10.
while ( m
msgBag : sender(m
) = q and seq#(m
) =
next[q])do
11.
deliver(F, m
)
12.
next[q] := next[q] + 1
13.
msgBag := msgBag – {m
}
Using Reliable Broadcast to build FIFO
Using Reliable Broadcast to build FIFO
Broadcast
Broadcast
2
2
Theorem
Given a Reliable Broadcast algorithm, the FB
algorithm is a FIFO Broadcast that satisfies Uniform FIFO
Order. Furthermore, if the Reliable Broadcast satisfies
Uniform Agreement or -Timeliness, then so does the
derived FIFO Broadcast.
Causal Broadcast using FIFO Broadcast
Causal Broadcast using FIFO Broadcast
(with Uniform FIFO Order)
(with Uniform FIFO Order)
1
1
CB Algorithm
Every process p executes the following:
1. Initialization:
2.
PrevDlvrs :=
/* sequence of messages that p C-delivered
since its previous C-broadcast */
3. To execute broadcast(C, m):
4.
broadcast(F, prevDlvrs m)
5.
prevDlvrs :=
6. deliver(C, m) occurs as follows:
7.
upon deliver(F, m1, m2,… ,ml ) for some l do
8.
for i := 1..l do
9.
if p has not previously executed deliver(C, m
i
)
10.
then
11.
deliver(C, m
i
)
12.
prevDlvrs := prevDlvrs m
i
Causal Broadcast using FIFO Broadcast
Causal Broadcast using FIFO Broadcast
(with Uniform FIFO Order)
(with Uniform FIFO Order)
2
2
Theorem
Given a FIFO Broadcast algorithm that satisfies
Uniform FIFO Order, the CB algorithm is a Causal
Broadcast that satisfies Uniform Causal Order.
Furthermore, if the given FIFO Broadcast satisfies Uniform
Agreement or -Timeliness, then so does the derived Causal
Broadcast.
Timed Atomic Broadcast using Timed
Timed Atomic Broadcast using Timed
Reliable Broadcast
Reliable Broadcast
1
1
ABTR Algorithm
Every process p executes the following:
1. To execute broadcast(A
, m):
2.
broadcast(R
, m)
3. deliver(A
, m) occurs as follows:
4.
upon deliver(R
, m) do
5.
schedule deliver(A
, m) at time ts(m) +
Timed Atomic Broadcast using Timed
Timed Atomic Broadcast using Timed
Reliable Broadcast
Reliable Broadcast
2
2
Theorem
Given a (Local-Time) Timed Reliable Broadcast
algorithm in a system with clocks that satisfy the
monotonicity assumption, the ABTR algorithm is a (Local-
Time) Timed Atomic Broadcast.
Timed Causal Atomic Broadcast using Timed
Timed Causal Atomic Broadcast using Timed
Causal Broadcast
Causal Broadcast
1
1
TCAB Algorithm
Every process p executes the following:
1. To execute broadcast(CA
, m):
2.
broadcast(C
, m)
3. deliver(CA
, m) occurs as follows:
4.
upon deliver(C
, m) do
5.
schedule deliver(CA
, m) at time ts(m) +
Timed Causal Atomic Broadcast using Timed
Timed Causal Atomic Broadcast using Timed
Causal Broadcast
Causal Broadcast
2
2
Theorem
Given a (Local-Time) Timed Causal Broadcast
algorithm in a system with clocks that satisfy the
monotonicity assumption, the TCAB algorithm is a (Local-
Time) Timed Causal Atomic Broadcast. Furthermore, if the
Timed Causal Broadcast is Uniform, then so is the derived
Timed Causal Atomic Broadcast.
Causal Atomic Broadcast using FIFO Atomic
Causal Atomic Broadcast using FIFO Atomic
Broadcast
Broadcast
1
1
CABFAB Algorithm
1. Every process p executes the following:
2. Initialization:
3.
prevDlvrs :=
/* set of messages that p CA-delivered since its
previous CA-broadcast */
4.
suspects :=
/* processes that p suspects to be faulty */
5. To execute broadcast(CA, m):
6.
broadcast(FA, m, prevDlvrs)
7.
prevDlvrs :=
8. deliver(CA, m) occurs as follows:
9.
upon deliver(FA, m, D) do
10.
if sender(m) suspects and
11.
p has previously executed deliver(CA, m
) for all m
D
12.
then
13.
deliver(CA, m)
14.
prevDlvrs := prevDlvrs {m}
15.
else
/* either p or sender(m) is faulty */
16.
discard m
17.
suspects := suspects {sender(m)}
Causal Atomic Broadcast using FIFO Atomic
Causal Atomic Broadcast using FIFO Atomic
Broadcast
Broadcast
2
2
Theorem
Given a FIFO Atomic Broadcast algorithm, the
CABFAB algorithm is a Causal Atomic Broadcast.
Furthermore, if the FIFO Atomic Broadcast satisfies
Uniform Agreement or -Timeliness, then so does the
derived Causal Atomic Broadcast.