content Flashcards
Best-effort broadcast (beb)
Uses perfect link
- Request : bebBroadcast, m
- Indication : bebDelilver, src, m
• BEB1. Validity : If pi and pj are correct then every message broadcast by pi
is eventually delivered
by pj
• BEB2. No duplication : No message is delivered more than once
• BEB3. No creation : No messages is delivered unless it was broadcast
Reliable broadcast (rb)
Uses BeB, perfect failure detector
Properties RB1 = BEB1. RB2 = BEB2. RB3 = BEB3. RB4. Agreement: For any message m, if any correct process delivers m, then every correct process delivers m
Uniform broadcast (urb)
uses BEB, P
- Request :
- Indication :
Properties URB1 = BEB1. URB2 = BEB2. URB3 = BEB3. URB4. Uniform Agreement: For any message m, if any process delivers m, then every correct process delivers m
Causality
Let m1 and m2 be any two messages: m1 -
> m2 (m1 causally precedes m2) iff
C1 (FIFO order). Some process pi
broadcasts m1 before broadcasting m2
C2 (Local order). Some process pi delivers
m1 and then broadcasts m2
C3 (Transitivity). There is a message m3
such that m1 -> m3 and m3 - > m2
Causal broadcast
Request :
• Indication :
• Property:
• CO: If any process pi delivers a message
m2, then pi must have delivered every
message m1 such that m1 -> m2
Reliable causal broadcast (rcb)
uses rb
Request :
• Indication :
• Properties:
- RB1, RB2, RB3, RB4 +
- CO
Uniform causal broadcast (ucb)
Uses urb
Request :
• Indication :
• Properties:
- URB1, URB2, URB3, URB4 +
- CO
Total order broadcast (tob)
uses rb, consensus
Request :
• Indication :
• Properties:
• RB1, RB2, RB3, RB4
• Total order property : Let m and m’ be any two messages.
Let pi be any (correct) process that delivers m
without having delivered m’
Then no (correct) process delivers m’ before m
Consensus properties
C1. Validity: Any value decided is a value proposed C2. Agreement: No two correct processes decide differently C3. Termination: Every correct process eventually decides C4. Integrity: No process decides twice
Uniform consensus - properties
C1. Validity: Any value decided is a value proposed C2. Uniform Agreement: No two processes decide differently C3. Termination: Every correct process eventually decides C4. Integrity: No process decides twice
Consensus - inteface
- Request : Propose, v
* Indication : Decide, v’
Beb interface
- Request : bebBroadcast, m
* Indication :bebDelilver, src, m
RB - interface
- Request : rbBroadcast, m
* Indication : rbDeliver, src, m
URB interface
- Request : urbBroadcast, m
* Indication : urbDeliver, src, m
rcb - interface
- Request : rcoBroadcast, m
* Indication : rcoDeliver, src, m
UCB - interface
- Request : ucoBroadcast, m
* Indication : ucoDeliver, src, m
TOB - interface
- Request : toBroadcast, m
* Indication : toDeliver, src, m
ACID properties
Atomicity: a transaction either performs entirely or none at all
Consistency: a transaction transforms a consistent state into
another consistent state
Isolation: a transaction appears to be executed in isolation
Durability: the effects of a transaction that commits are
permanent
Nbac interface
Uses beb, P, uniCons
Request : Propose, v
Indication : Decide, v’
nbac properties
NBAC1. Agreement : No two processes decide differently
• NC1C2. Termination : Every correct process eventually decides
• NBAC3. Commit-Validity : 1 can only be decided if all process propose 1
• NBAC4. Abort-Validity : 0 can only be decided if some process crashes of votes 0
Group Membership - properties
Memb1. Local Monotonicity: If a process installs view
(j,M) after installing (k,N), then j > k and M < N
Memb2. Agreement: No two processes install views
(j,M) and (j,M’) such that M ≠ M’
Memb3. Completeness: If a process p crashes, then
there is an integer j such that every correct process
eventually installs view (j,M) such that p not in M
Memb4. Accuracy: If some process installs a view (i,M)
and p not in M, then p has crashed
Group Membership - interface
Uses:
PerfectFailureDetector (P).
UniformConsensus(Ucons).
Events
Indication: membView, V
View Synchrony broadcast - interface
Uses:
GroupMembership (gmp).
TerminatingReliableBroadcast(trb).
BestEffortBroadcast(beb).
Request:
vsBroadcast, m; vsBlock, ok
Indication:
vsDeliver, src, m; vsView, V; vsBlock
TRB - interface
Uses:
BestEffortBroadcast (beb).
PerfectFailureDetector (P).
Consensus(cons).
Events
Request: trbBroadcast, m
Indication: trbDeliver, p, m
TRB - properties
TRB1. Integrity: If a process delivers a message m, then
either m is j or m was broadcast by src
TRB2. Validity: If the sender src is correct and broadcasts a
message m, then src eventually delivers m
TRB3. (Uniform) Agreement: For any message m, if a
correct (any) process delivers m, then every correct process
delivers m
TRB4. Termination: Every correct process eventually delivers
exactly one message
Fair-loss links - properties
FL1. Fair-loss: If a message is sent infinitely
often by pi to pj , and neither pi or pj crashes,
then m is delivered infinitely often by pj
FL2. Finite duplication: If a message m is sent
a finite number of times by pi to pj, m is delivered
a finite number of times by pj
FL3. No creation: No message is delivered unless
it was sen
Stubborn links - properties
SL1. Stubborn delivery: if a process pi sends a
message m to a correct process pj, and pi does not
crash, then pj delivers m an infinite number of times
SL2. No creation: No message is delivered unless
it was sent
Perfect Link - properties
PL1. Validity: If pi and pj are correct, then every message sent by pi to pj is eventually delivered by pj PL2. No duplication: No message is delivered (to a process) more than once PL3. No creation: No message is delivered unless it was sent
Failure Detection -interface
Events
Indication: crash, p
perfect Failure detec - properties
Strong Completeness: Eventually, every process that
crashes is permanently suspected by every correct process
Strong Accuracy: No process is suspected before it crashes
Eventually perfect Failure detec
Strong Completeness
Eventual Strong Accuracy: Eventually, no correct process is
ever suspected
