18-More Clocks and Mutual Exclusion

More on Total Order Multicast using Logical Clocks Vector Clocks Mutual Exclusion
展开查看详情

1.CSC2/458 Parallel and Distributed Systems More Clocks and Mutual Exclusion Sreepathi Pai March 27, 2018 URCS

2.Outline More on Total Order Multicast using Logical Clocks Vector Clocks Mutual Exclusion

3.Outline More on Total Order Multicast using Logical Clocks Vector Clocks Mutual Exclusion

4.Total-ordered multicast • Each client multicasts a message to all replicas • Each message is timestamped according to local logical clock • Assume no loss of messages • Assume reliable ordering • Each replica places received messages in a queue • Each replica acknowledges receipt of messages using a multicast • Each replica processes messages in order of their timestamps • Only when it has received acknowledgement for that message from all other replicas This protocol ensures all processes see the same queue.

5.Invariants • Process a message if: • it has been acknowledged by all other processes • If multiple such messages exist: • process them in sender-timestamp order

6.Empty queue Consider yourself to be a process. • Your queue is empty • What do you do?

7.Queue with a message • Your queue contains a single message • (or multiple messages) • But no acknowledgements • What do you know? • What do you do?

8.Queue with acknowledgements • Your queue contains only acknowledgements • But no messages • What do you know? • What do you do?

9.Queue with message + all acknowledgements • Your queue contains a message and all its acknowledgements • no other message (if any) has all its acknowledgements • What do you know? • What do you do? • What if a message without its acknowledgements has a lower sender-timestamp?

10.Could it happen? • Your queue contains a message A and all its acknowledgements • and no other message or acknowledgements • Some other process contains a message B and all its acknowledgements • and no other message or acknowledgements

11.Checking all possible states of a finite state machine • A formal method called model checking • Used by Amazon (among others) • How Amazon Web Services uses Formal Methods, CACM 48(4) • Tools, TLA+ and TLC • The TLA home page

12.Outline More on Total Order Multicast using Logical Clocks Vector Clocks Mutual Exclusion

13.Causality • Consider a messaging board where messages and replies are multicast (or broadcast) • Messages must appear to everybody before their replies • I.e. Replies are “caused by” messages • In logical clocks: • a → b implies C (a) < C (b) • but C (a) < C (b) does not imply a → b

14.Example P1 P2 P3 0 0 0 6 m1 8 10 12 16 m2 20 18 24 30 24 32 m3 40 30 40 50 36 48 60 42 61 m4 70 48 69 80 70 m5 77 90 76 85 100 • Are m1 and m2 causally related? • note: maybe better to read: did m1 happen before m2 ?

15.Easy way • Each message carries a list of all messages seen by sender • Causal history • Easy to see when messages are not causally related • If b happened after a, it must have seen a • See textbook for formal definition

16.Vector Clocks • Encode global knowledge into timestamps • Each timestamp ts(m) for message m is now a vector (i.e. an array) • Contains n items for n processes • Vi [j] is vector clock at process i, containing last known timestamp at process j • Vi [i] is incremented every time an event is generated (i.e. it is like i’s local clock) • Importantly, Vi [j] = k means that process i knows k events have happened at process j • Update: • Vi [k] = max{Vi [k], ts(m)[k]} for all k

17.Example: Determining ordering • Define ts(a) < ts(b) for messages a and b if and only: • ts(a)[k] ≤ ts(b)[k] for all k • ts(a)[k ] < ts(b)[k ] for some k • Did m2 happen before m4 ? (1,1,0) (2,1,0) (3,1,0) (4,1,0) P1 m1 m2 m3 (4,3,0) P2 (0,1,0) (4,2,0) m4 P3 (2,1,1) (4,3,2)

18.Example: Determining ordering – contd • Did m2 happen before m4 ? (1,1,0) (2,1,0) (3,1,0) (4,1,0) P1 m1 m3 m2 P2 (2,3,0) (0,1,0) (2,2,0) m4 P3 (2,3,1) (4,3,2)

19.Causal-ordered Multicast Board (1,0,0) (1,1,0) P1 m (1,1,0) P2 (1,0,0) m* P3 (0,0,0) (1,0,0) (1,1,0)

20.Outline More on Total Order Multicast using Logical Clocks Vector Clocks Mutual Exclusion

21.Centralized Mutual Exclusion • One Coordinator • All processes Request exclusive access from Coordinator • Coordinator • Grants access if no other process is requesting the same resource • does not reply if another process is granted resource • places request in queue • Process • blocks waiting for reply from Coordinator • accesses resource on grant from Coordinator • Releases resource by informing Coordinator • Coordinator • on release, informs next process in queue that requested resource

22.Evaluating Centralized Mutual Exclusion • Scalability • Single coordinator may become performance bottleneck • Availability • Single coordinator may crash • What about process crashes? • Number of messages • to enter critical section: 2

23.Mutual Exclusion using Totally ordered Multicasts • Total ordered multicast produces a total order among all messages • Can be used to implement mutual exclusion • Messages: • ENTER: process multicasts that it wants to enter a critical section • ALLOW: process unicasts permission to ENTERing process • RELEASE: process multicasts that it has left a critical section

24.Evaluating Totally Ordered Multicasts • Scalability • No single coordinator • But what about requiring permission from everybody ? • Availability • What if a process crashes? • Number of Messages • to enter critical section? • Multicasts and complexity • what if there is no multicast primitive?

25.Token Ring Mutual Exclusion Token 0 1 2 3 7 6 5 4 • Construct ring overlay (i.e. logical) network • Has no relation to physical network • how to construct this? • Generate token • On receiving token • Optionally, perform accesses to any shared resources • Pass token to neighbour

26.Evaluating Token Ring Mutual Exclusion • Scalability • No centralized coordinator • Availability • What if token is lost? • What if a process not holding a token crashes? • What if a process holding a token crashes? • Number of messages • to enter critical section: N − 1 (max.)

27.Decentralized Mutual Exclusion using Voting • Replicate resource N times • Each replica controlled by different coordinator • When a process requests access to a resource • It must get permission from more than N/2 coordinators (does it need to wait for all coordinators?) • Coordinators may refuse to give access if they’ve already given access • A process that is refused access sends releases to coordinators it got access from and will backoff and retry after some time • Of interest, a coordinator may crash and “forget” it had given access • Incorrectly give access to a process • When will this cause a problem?

28.Evaluating Mutual Exclusion using Voting • Scalability • Multiple centralized coordinators, only require majority • Availability • Probabilistic arguments against all coordinators crashing • What about processes holding locks? • Utilization • Does at least one process that competes for a resource get it? • Number of messages • to enter a critical section: ?