Rozproszona pamięć współdzielona (ang. distributed shared memory)

Broadcast

Distributed

operating systems

Specifications and

algorithms

Reliable Broadcast

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

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.





m

m

Causal

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

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.





m

Atomic Broadcast

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 =

q =





m

m

FIFO Atomic Broadcast

FIFO Atomic Broadcast

is a

Reliable Broadcast

that satisfies

both the

FIFO

and

Total Order

requirements.

m



m

m

Causal Atomic Broadcast

Causal Atomic Broadcast

is a

Reliable Broadcast

that

satisfies both the

Causal

and

Total Order

requirements.

Incorrect process

m

Is it a

FIFO Atomic Broadcast



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)

Uniform Broadcasts

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 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

Reliable

Broadcast

Atomic

Broadcast

FIFO Atomic

Broadcast

Causal

Atomic

Broadcast

FIFO

Broadcast

Causal

Broadcast

Total Order

FIFO order

Causal Order

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

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

 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 (

- Reliable,

- FIFO,

Causal,

– FIFO Atomic,

– Causal Atomic).

RB Algorithm

Every process p executes the following:
1.

To execute broadcast(R, m):

tag m with sender(m) and seq# (m)

/* These tags make m unique

send(m) to all neighbors including p

deliver(R, m) occurs as follows:

upon receive(m) do

if p has not previously executed deliver(R, m)

then

if sender(m)  p then send(m) to all neighbors

deliver(R, m)

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

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

Broadcast

FB Algorithm

Every process p executes the following:
1.

Initialization:

msgBag := 

/* set of messages that p R-delivered but not yet F-

delivered */

next[q] := 1 for all q

/* sequence number of next message from q

that p will F-Deliver */

To execute broadcast(F, m):

broadcast(R, m)

deliver(F, m) occurs as follows:

upon deliver(R, m) do

q := sender(m)

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

Broadcast

 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

(with Uniform FIFO Order)

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)

prevDlvrs := 

6. deliver(C, m) occurs as follows:
7.

upon deliver(F,  m1, m2,… ,ml ) for some l do

for i := 1..l do

if p has not previously executed deliver(C, m

)

10.

then

11.

deliver(C, m

)

12.

prevDlvrs := prevDlvrs m

Causal Broadcast using FIFO Broadcast

(with Uniform FIFO Order)

 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

Reliable Broadcast

ABTR Algorithm

Every process p executes the following:
1. To execute broadcast(A



, m):

broadcast(R



, m)

3. deliver(A



, m) occurs as follows:

upon deliver(R



, m) do

schedule deliver(A



, m) at time ts(m) + 

Timed Atomic Broadcast using Timed

Reliable Broadcast

 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

Causal Broadcast

TCAB Algorithm

Every process p executes the following:
1. To execute broadcast(CA



, m):

broadcast(C



, m)

3. deliver(CA



, m) occurs as follows:

upon deliver(C



, m) do

schedule deliver(CA



, m) at time ts(m) + 

Timed Causal Atomic Broadcast using Timed

Causal Broadcast

 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

Broadcast

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 */

suspects := 

/* processes that p suspects to be faulty */

5. To execute broadcast(CA, m):
6.

broadcast(FA, m, prevDlvrs)

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

Broadcast

 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.

Document Outline