> Q(`
b/0DTimes New Roman@7|dv0|(
0DSymbolew Roman@7|dv0|(
0
`.
@n?" dd@ @@``L
>+$
B"c$@qDu ʚ;2Nʚ;g4kdkdv0pvppp@<4!d!d`
0,,8<4dddd`
0,,82*___PPT9z?%@MTotally Ordered Broadcast C
Algorithms for Distributed System
Semester Project
(Nam Thoai)
2D6.< Totally Ordered Broadcast Broadcast
Broadcast Service Qualities:
ordering : single-source FIFO, totally ordered, causally ordered
reliability
Implementing a broadcast service
Algorithm for Totally Ordered Broadcast
Modified Algorithm for Totally Ordered Broadcast
H)Oz)O{ Broadcast
Point-to-Point links: provides One-to-One communication one processor sends a message on an incident link to a single other processor
Broadcast(multicast): provides one-to-all (one-to-many) communication a processor sends a message to all processors
Broadcast (multicast) can be simulated by sending a number of point-to-point messages
LyVZY +The Basic Service Specification (broadcast),, + tbc-sendi(m,qos): An input event of processor pi, which sends a message m to all processors, containing an indication of the sender; qos is a parameter describing the quality of service required.
bc-recvi(m,j,qos): An output event in which processor pi receives the message m previously broadcast by pj; qos, as above, describes the quality of service provided.
Basic broadcast service: each bc-recvi(m,j,qos) event is mapped to an earlier bc-sendi(m,qos) event, every message received was previously sent (Integrity), and every message that is sent is received once (Liveness) and only once (No Duplicates) at every processor.j
<=
'
]
/
v < X V r 4 Broadcast Service Qualities Broadcast properties can be organized along two axes:
Ordering: Do processors see all messages in the same order or just see the messages from a single processor in the order they were sent ? Does the order in which messages are received by the broadcast service preserve the happens-before relation ?
Reliability: Do all processors see the same set of messages even if failures occur in the underlying system? Do all processors see all the messages broadcast by a nonfaulty processor?b77&
Ordering Single-Source FIFO: For all messages m1 and m2 and all processors pi and pj, if pi sends m1 before sends m2, then m2 is not received at pj before m1 is.
Totally Ordered: For all messages m1 and m2 and all processors pi and pj, if m1 is received at pi before m2 is, then m2 is not received at pj before m1 is.
Causally Ordered: For all messages m1 and m2 and every processor pi, if m1 happens before m2, then m2 is not received at pi before m1 is.
Note: message m1 is said to happen before message m2 if either:
the bc-recv event for m1 happens before the bc-send event for m2, or
m1 and m2 are sent by the same processor and m1 is sent before m2.A-
#
'
%
I = T C Z Ordering ,Causally Ordered implies Single-Source FIFO
6-- Reliability dIn the presence of faulty processors, the Liveness property needs to be weakened.
There are at most f faulty processors and the mapping a from bc-recv(m) events to bc-send(m) events.
Integrity: For each processor pi, 0 i n-1, the restriction of a to bc-recvi events is well-defined. That is, every message received was previously sent - no message is received out of thin air .
No Duplicates: For each processor pi, 0 i n-1, the restriction of a to bc-recvi events is one-to-one. That is, no message is received more than once at any single processor.
{d#- y
*_* \ Y _ Reliability \Nonfaulty Liveness: When restricted to bc-send and bc-recv events at nonfaulty processors, a is onto. That is, all messages broadcast by a nonfaulty processor are eventually received by all nonfaulty processors.
Faulty Liveness: If one nonfaulty processor has a bc-recv event that maps to a particular bc-send event of a faulty processor, then every nonfaulty processor has a bc-recv event that maps to the same bc-send event. That is, every messages sent by a faulty processor is either received by all nonfaulty processors or by none of them.
Atomic broadcast is a reliable broadcast with total ordering; atomic broadcast is also called total broadcast. FIFO atomic broadcast is an atomic broadcast with single-source FIFO ordering. Causal atomic broadcast is an atomic broadcast with preserves causality.!ZZIyDXD
<
<
)
.
Z
- Implementing a Broadcast Service!! Basic Broadcast Service
Using the underlying point-to-point message system to send a copy of m to all processors.
Single-Source FIFO OrderingH\\
Totally Ordered Broadcast$ vAn Asymmetric Algorithm
Processor pi sends m using the basic broadcast service to a unique central site at processor pc.
Processor pc assigns a sequence number to each message and then sends it to all processors using the basic broadcast service.
Message(k) is received if all messages(i) (0 i < k) are received
"-R
< Totally Ordered Broadcast$ A Symmetric Algorithm
Based on assigning timestamps to messages.
Assume that the underlying communication system provides single-source FIFO broadcast.
Each processor maintains an increasing counter (timestamp), which is tagged on messages.
Each processor also maintains a vector with estimates of the timestamps of all other processes. Processor pi updates its entry for pj using the tags on messages received from pj and using special timestamp update message sent by pj. -G+7Zu * 6 Totally Ordered Broadcast$ (Code for pi, 0 i n-1)
Initially ts[j]=0, 0 j n-1, and pending is empty
1: when bc-sendi(m,to) occurs: // quality of service to means totally ordered
2: ts[i] := ts[i]+1
3: add m, ts[i], i to pending
4: enable bc-sendi(m, ts[i], ssf) // quality of service to means single-source FIFO
5: when bc-recvi(m, T, j, ssf), ji, occurs: // j indicates sender; ignore messages from self
6: ts[j] := T
7: add m, T, j to pending
8: if T > ts[i] then
9: ts[i] := T
10: enable bc-sendi(ts-up, T, ssf) // bcast timestamp update message
11: when bc-recvi(ts-up, T , j, ssf), ji, occurs: // ignore message from self
12: ts[j] := T
13: enable bc-recvi(m, j, to) when
14: m, T, j is the entry in pending with the smallest (T, j)
15: T ts[k] for all k
16: result: remove m, T, j from pendingtZ'Z
'lWtHEc/U& 1 B @ E 1 #
1 Y 8
*Totally Ordered Broadcast (implementation)2+ * (Code for pi, 0 i n-1)
Initially ts[j]=0, tn[j]=0 (0 j n-1), N=0, and pending is empty
1: when bc-sendi(m,to) occurs: // quality of service to means totally ordered
2: ts[i] := ts[i]+1
N = N+1
3: add m, ts[i], N, i to pending
4: enable bc-sendi(m, ts[i], N, basic) // quality of service to means basic
5: when bc-recvi(m, T, N, j, basic), ji, occurs: // j indicates sender; ignore messages from self
6: ts[j] := T
7: add m, T, N, j to pending
8: if T > ts[i] then
9: ts[i] := T
10: enable bc-sendi(ts-up, T, basic) // bcast timestamp update message
11: when bc-recvi(ts-up, T , j, basic), ji, occurs: // ignore message from self
12: ts[j] := T
13: enable bc-recvi(m, j, to) when
14: m, T, N, j is the entry in pending with the smallest (T, j)
15: (T ts[k] for all k) and (N = tn[j]+1)
16: result: remove m, T, j from pending, and tn[j] := tn[j] + 1ZvZ
U:_H
5e25"% 7 B " A Y 4 # C ] 6 ` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@,|?" dd@ " @ ` n?" dd@ @@``PR @ ` `p>>f(
6k P
T Click to edit Master title style!
!
0n
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
04s ``
>*
0x `
@*
0|} `
@*H
0h ? ̙33 Default DesignpH8(
H
H
0p 18
>*
H
0 g 8
@*
H
6ÿ (1`
>*
H
6g (g `
@*H
H0bf@ ? ̙33
0$(
r
SGP
r
ShH
H
0h ? ̙33
@@0(
@x
@ c$4P
x
@ c$ܰ
H
@0h ? ̙33
P0 (
x
c$ʿP
x
c$T˿
+8
Z2
s* ` Z2
s*
ZB
s*D` P
P
6Ϳ
OM X2
0p ` X2
0
P
X2
0p
X2
00
X2
0
X2
0
P
XB
0D`
<п
OM
BCDE4F
8phHp88@ `RB
s*D`
`RB
s*D`
RB
s*D
`
RB
s*D
`
H
0h ? ̙33
`0(
x
c$hP
x
c$
H
0h ? ̙33
0(
x
c$p
P
x
c$
H
0h ? ̙33
0(
x
c$AP
x
c$hB
H
0h ? ̙33
*=0(
x
c$PP
x
c$Q
LB
c$D00 LB
c$DPRB
s*D !RB
s*D XB
0D 0XB
0D
#BCDEFp`Ph@ `@
#BCDEFl`PL`@ 0
60
Qa(2
6 @
Sa,b(2
6X @
Sb,a(2
6̗
Qb(2
6l
t&(1) causally ordered (totally ordered)' 2'& RB
s*D RB
s*DXB
0D @
#BCDEFp`Ph@ `@
6$0
Qa(2
60
Sb,a(2
!
6Ģ0
Sb,a(2
"
680
Qb(2
#
6خ .
=(2) totally ordered (causally ordered, single-source ordered)> 2>= LB
$
c$DPLB
%
c$D@@P
&
BC DEF pH, @ RB
)
s*D @RB
+
s*D RB
,
s*D
1
6@
@0
Qa(2
2
6 @
Sb,a(2
3
6ඕ~
@R
Sa,b(2
4
6|v
Qb(2
5
6
:(1) single-source FIFO (totally ordered, causally ordered); 2;: LB
8
c$D
9
BCDEF`h@`@ RB
:
s*D
RB
;
s*D@`
<
BCDEFp`P0`@ @
LB
=
c$DP
@@
H
0h ? ̙33
* 0(
x
c$[P
x
c$l\
H
0h ? ̙33
|t"#((
(x
( c$`P
x
( c$paP
F 0
(
Z2
(
s* ` 0Z2
(
s*
@0
(
6e0
Pm1 Z2
(
s*
0Z2
(
s*
`@ZB
(B
s*D0 ZB
(
s*DZB
(
s*D
(
6pj@
Pm1
(
6Xn
Pm1
(
6Ǖ 0
\P0"
(
6˕
0p
\P1"
(
6h
0
nPn-1-f"
"
(
600
c. . .&
(
6@0`
lPn-1"
" X2
(
00
X2
(
0p
(
<<`
Pm1 X2
(
0@
X2
(
0P
p
^B
(@
6D
@^B
(
6D
@@^B
(
6D
@
(
<p
Pm1
(
<
Pm1
(
<
0
\P0"
(
<ľ
\P1"
!(
<Ⱦ
nPn-1-f"
"
"(
<p`
c. . .&
#(
<^
p
lPn-1"
" H
(0h ? ̙33
,0F(
,x
, c$ՕP
,
<֕ P
X2
,
0P
X2
,
0P
p
XB
,
0D
,
<ؕ P
P
^message(data, N)
,
< ݕ
`
ON
,
<`p@0
N = N+1;
bc-send(data, N). N
,
<d@@0
Message(data, n) is received if all
message(i) (0 i < n) are received J3J H
,0h ? ̙33
/A0;(
0x
0 c$XP
0
< P
X2
0
00 pX2
0
0
0X2
0
0
0 X2
0
0
XB
0
0D
XB
0
0D0 0
XB
0
0Dp `P
XB
0
0D 0
XB
0
0D`
XB
0@
0Dp0
0
<
P@
Oa
0
<
Ob
0
<4`P
Oc L P
0#P
0
6\ P
Ra(1)
0
6
P
Rb(2)
0
6DP
Rc(3) L P
"0#@
#0
6`" P
Ra(1)
$0
6%
P
Rb(2)
%0
6P
Rc(3) L P
&0#@`
'0
6, P
Rc(3)
(0
6/
P
Rb(2)
)0
63P
Ra(1) L P
*0#@0`
+0
67 P
Rb(2)
,0
6;
P
Ra(1)
-0
64P
Rc(3) L P
/0#0`
00
6\3 P
Ra(1)
10
6H3
P
Rb(2)
20
643P
Rc(3) L P
70#
80
6+ P
Ra(1)
90
6(>
P
Rb(2)
:0
6LEP
Rc(3) L P
;0#`
<0
6K3 P
Ra(1)
=0
643
P
Rb(2)
>0
63P
Rc(3)
?0
043P
B$(2
@0
0$3
B$(2
A0
03
@
B$(2H
00h ? ̙33
!4H(
4x
4 c$P
4
< P
H
40h ? ̙33
8H(
8x
8 c$P
8
<` `
H
80h ? ̙33
<H(
<x
< c$D3P
3
<
<|
3 `3
H
<0h ? ̙33rLQ+^bkmoq֊ΌĨ`KZ
tOh+'0 `h
Totally Ordered Broadcastinthoai nthoai 43oMicrosoft PowerPointcas@ r;@0rj@4Gg 9& &&#TNPP2OMiL
&
TNPP &&TNPP
--- !---&G&qw@j
LSwUSw0- &Gy& --y@H-- @Times New RomanLSwUSw0- .-2
Totally Ordered Broadcast#+&.--yH-- @Times New RomanLSwUSw0- .92
/!Algorithms for Distributed System
!. .2
lVSemester Project!
.@Times New RomanLSwUSw0- .2
(Nam . .2
Thoai . . 2
().--"System
0-&TNPP &՜.+,00
On-screen Show GUP-Linz Sh{
Times New RomanSymbolDefault DesignTotally Ordered BroadcastTotally Ordered Broadcast
Broadcast,The Basic Service Specification (broadcast)Broadcast Service Qualities Ordering OrderingReliabilityReliability!Implementing a Broadcast ServiceTotally Ordered BroadcastTotally Ordered BroadcastTotally Ordered Broadcast+Totally Ordered Broadcast (implementation)Fonts UsedDesign Template
Slide Titles_Wnthoainthoai
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefhijklmnpqrstuvxyz{|}~Root EntrydO)Current UserwSummaryInformation(gPowerPoint Document({DocumentSummaryInformation8o