COMPSCI 711 Agreement Misc radu/2020
SYNCHRONISERS: ATTEMPT TO SYNCHRONISE ASYNC NETWORKS (SEE LYNCH CH 16) DO NOT COPE WITH STOPPING (OR, EVEN LESS, WITH BYZ) FAILURES
GlobSync ( )
o ensures that all messages are sent before receiving
o collects all sent messages and then delivers them to their targets
Global Synchronizer
LocSync ( ) o similar to GlobSync
o but only ensures that all
neighborhood messages are sent before receiving
Local Synchronizer
o Synchronizers need to keep the round number, explicitly or implicitly.
o Even if no faulty nodes are present, messages from different rounds may arrive interleaved (fast, slow).
o Here, process U3 may receive a round 2 message from U2, before receiving its round 1 message from U1 !
U1
U2
U3 U4
U1 U2
SimpleSync ( ) an implementation of the LocSync
S1 C12 S2 C21
U1
U2
Simple Synchronizer
1.8
COMPSCI 711 Agreement Misc radu/2020
SYNCHRONISERS: CAN THEY HELP?
o Using a simpler sync algorithm instead of a much more complex async !
o E.g. Sync Distributed MST instead of the Async Distributed MST (GHS)
o Obtaining a faster runtime ?
o E.g. could this avoid greedy choices, which may be very costly in the end ? o What if we apply a synchroniser to Distributed Bellman-Ford ?
2.8
COMPSCI 711 Agreement Misc
COMMUNICATION FAILURES
radu/2020
Is it possible to reach a distributed agreement with ( ) communication failures?
unbounded
Formal conditions: o All processes eventually decide.
o Termination: o Agreement:
o No two processes ever decide on different values.
o Validity:
o If processes start with the same initial value 1 and
, then 1 is the only one possible decision value. [WEAK]
▪ relaxation: allow fallback on 0 if communications fail (approx. v0 could be 0)
and
o If all processes start with the same initial value 0, then 0 is the only one possible decision value. [STRONG]
We also assume that a decision once taken can be immediately acted upon (by all processes in sync).
all
all messages are properly delivered
Initial
Decision
No comm fault
0
0
Comm faults
0
0
Initial
Decision
No comm fault
1
1
Comm faults
1
1 or
0
Initial
Decision
No comm fault
0,1
1 or 0
Comm faults
0,1
1 or 0
3.8
Diagrams
COMPSCI 711 Agreement Misc radu/2020
Fundamental result: Even under such relaxed conditions, no deterministic agreement is possible if unlimited communication failures are possible (but then, how do TCP and the internet work?)
Proof: by induction, using the given validity, agreement and termination conditions
In our diagrams, ! denotes a no-return state, where a certain decision will inevitably follow (even if no more messages are received)
11
1
1
no lost messages
11
1!
n?
consensus!
1 lost messages +n?
1
1
11
1!
1!
… lost messages
11
all messages lost
1!
1!
01 consensus!
1
!
1!
0
4.8
1!
consensus!
contradiction!
0
1!
COMPSCI 711
Agreement Misc
radu/2020
DISTRIBUTED COMMIT
o 2 PHASE COMMIT – WEAK TERMINATION (“BLOCKING”)
o 3 PHASE COMMIT – STRONG TERMINATION (“NON-BLOCKING”)
All non-faulty
Termination: eventually decide [
or
If there are
eventually decide [ ]. (2PC)
Agreement: No two processes (even faulty) ever decide on different values [STRONG]. (2&3PC)
Validity: If any process starts with the initial value 0, then 0 is the only one possible decision value.
initial 0 → can start as decided 0! and If all processes start with the same initial value 1 and there are no failures, then 1 is the only one possible decision value.
[WEAK]. (2&3PC)
STRONG
processes ]. (3PC)
no failures
then all processes
WEAK
Decided, not failing
1
or
0†
1
Decided, before failing
1
or
0†
Non-decided, failed
—
Non-decided, not failing (2PC)
Process
—
Initial
Decision
Decided, not failing
0
0
Decided, before failing
0
Non-decided, failed
—
Non-decided, not failing (2PC)
—
2PC weak termination
only if
fail
1
blocked
Diagrams
Process
Initial
Decision
†
Decision 0 is allowed
The
one/more processes
condition allows non-faulty
process (with initial value ) that never decide, that remain
“ ” (unless they receive some “magical” help).
5.8
COMPSCI 711 Agreement Misc radu/2020
THE 2 PHASE COMMIT – WEAK TERMINATION (“BLOCKING”)
We do not discuss here:
o how the processes start this,
o how do they recover after failures.
o Participants: coordinator (leader), cohorts.
o States: decided(0) uncertain(1) → decided(1), or +failed
final:
decided(0)
(1,u)
(0,d)
(0,d)
final:
decided(1)
(1,u)
(1,d)
(1,d)
(0,d)
(0,d)
(0,d)
(1,u)
(1,u)
(1,d)
(0,d)
(0,d)
(0,d)
(1,u)
(1,u)
(1,d)
(1,u)
(1,u)
(0,d)
If #1 fails, then #2&3 cannot differentiate between left and right (even if they talk), will remain
attempted decision(1) blocked for ever
(1,u) (1,d) (1,u) (1,u) (1,u) (1,u)
(1,d)
(1,u) (1,u)
attempted
decision(0)
blocked
for ever
(0,d)
(0,d)
(0,d)
(1,u)
(1,u)
(1,u)
(1,u)
(1,u)
(1,u)
o 2PC blocks because the leader is too greedy to decide on 1 and fails before sending its messages
6.8
blocked
THE
3
PHASE COMMIT –
STRONG
TERMINATION (“
NON-BLOCKING
”)
3PC algorithm is less greedy than 2PC and new coordinators arise in place of failed ones States (one more, ready): decided(0) uncertain(1) → ready(1) → decided(1), or +failed
o State transition rules are “natural” and similar for all rounds, except:
o In the first 3 rounds:
o Any missing message
decided(0)!
o If all are uncertain, they will
attempt decided(1)!
o In round 4 and following:
o Any missing message is
ignored!
o If all the rest are uncertain,
they will certainly decided(0)!
final:
decide(1)
(1,u)
(1,r)
(1,d)
(1,d)
(1,u)
(1,u)
(1,r)
(1,d)
(1,u)
(1,u)
(1,r)
(1,d)
final:
decide(0)
(1,u)
(0,d)
(0,d)
(0,d)
(0,d)
(0,d)
(0,d)
(0,d)
(0,d)
(1,u)
(1,u)
(0,d)
COMPSCI 711 Agreement Misc radu/2020
7.8
COMPSCI 711 Agreement Misc radu/2020
AVOIDING THE BLOCK
2PC would attempt decision(1) but it
would block
– 3PC doesn’t block final
decided(1)
(1,u)
(1,r)
(1,r)
(1,u)
(1,u)
(1,r)
(1,r)
(1,r)
(1,d)
(1,d)
(1,u)
(1,u)
(1,u)
(1,u)
(1,u)
(1,r)
(1,d)
2PC would attempt decision(1) but it
would block
– 3PC doesn’t block final
decided(0)
(1,u)
(1,r)
(1,r)
(1,u)
(1,u)
(1,u)
(1,u)
(0,d)
(0,d)
(0,d)
(1,u)
(1,u)
(1,u)
(1,u)
(1,u)
(0,d)
(0,d)
2PC would attempt decision(0) but it would block – 3PC doesn’t block final decided(0) (0,d) (0,d) (0,d)
(1,u) (1,u) (1,u) (1,u) (0,d) (0,d) (0,d) (1,u) (1,u) (1,u) (1,u) (1,u) (0,d) (0,d)
8.8