分布式計算英文課件：Chapter 6 Synchronization

1、DISTRIBUTED SYSTEMSPrinciples and ParadigmsSecond EditionANDREW S. TANENBAUMMAARTEN VAN STEENChapter 6SynchronizationTanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Clock SynchronizationFigure 6-1. When each mac

2、hine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Physical Clocks (1)Figure 6-2. Computation of the m

3、ean solar day.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Physical Clocks (2)Figure 6-3. TAI seconds are of constant length, unlike solar seconds. Leap seconds are introduced when necessary to keep in phase

4、with the sun.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Global Positioning System (1)Figure 6-4. Computing a position in a two-dimensional space.Tanenbaum & Van Steen, Distributed Systems: Principles and Pa

5、radigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Global Positioning System (2)Real world facts that complicate GPSIt takes a while before data on a satellites position reaches the receiver.The receivers clock is generally not in synch with that of a satellite.Tanenbaum & V

6、an Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Clock Synchronization AlgorithmsFigure 6-5. The relation between clock time and UTC when clocks tick at different rates.Tanenbaum & Van Steen, Distributed Systems: Principles a

7、nd Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Network Time ProtocolFigure 6-6. Getting the current time from a time server.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5The B

8、erkeley Algorithm (1)Figure 6-7. (a) The timedaemon asks all the other machines for their clockvalues. Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5The Berkeley Algorithm (2)Figure 6-7. (b) The machines answe

9、r.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5The Berkeley Algorithm (3)Figure 6-7. (c) The time daemon tells everyone how to adjust their clock.Tanenbaum & Van Steen, Distributed Systems: Principles and Par

10、adigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Clock Synchronization in Wireless Networks (1)Figure 6-8. (a) The usual critical path in determining network delays. Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All r

11、ights reserved. 0-13-239227-5Clock Synchronization in Wireless Networks (2)Figure 6-8. (b) The critical path in the case of RBS.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Lamports Logical Clocks (1)The happ

12、ens-before relation can be observed directly in two situations:If a and b are events in the same process, and a occurs before b, then a b is true.If a is the event of a message being sent by one process, and b is the event of the message being received by another process, then a bTanenbaum & Van Ste

13、en, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Lamports Logical Clocks (2)Figure 6-9. (a) Three processes, each with its own clock. The clocks run at different rates. Tanenbaum & Van Steen, Distributed Systems: Principles and Par

14、adigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Lamports Logical Clocks (3)Figure 6-9. (b) Lamports algorithm corrects the clocks.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Lampor

15、ts Logical Clocks (4)Figure 6-10. The positioning of Lamports logical clocks in distributed systems.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Lamports Logical Clocks (5)Updating counter Ci for process PiBe

16、fore executing an event Pi executes Ci Ci + 1.When process Pi sends a message m to Pj, it sets ms timestamp ts (m) equal to Ci after having executed the previous step.Upon the receipt of a message m, process Pj adjusts its own local counter as Cj maxCj , ts (m), after which it then executes the firs

17、t step and delivers the message to the application.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Example: Totally Ordered MulticastingFigure 6-11. Updating a replicated database and leaving it in an inconsiste

18、nt state.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Vector Clocks (1)Figure 6-12. Concurrent message transmission using logical clocks.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2

19、e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Vector Clocks (2)Vector clocks are constructed by letting each process Pi maintain a vector VCi with the following two properties:VCi i is the number of events that have occurred so far at Pi. In other words, VCi i is the local logica

20、l clock at process Pi .If VCi j = k then Pi knows that k events have occurred at Pj. It is thus Pis knowledge of the local time at Pj .Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Vector Clocks (3)Steps carri

21、ed out to accomplish property 2 of previous slide:Before executing an event Pi executes VCi i VCi i + 1.When process Pi sends a message m to Pj, it sets ms (vector) timestamp ts (m) equal to VCi after having executed the previous step.Upon the receipt of a message m, process Pj adjusts its own vecto

22、r by setting VCj k maxVCj k , ts (m)k for each k, after which it executes the first step and delivers the message to the application.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Enforcing Causal Communication

23、Figure 6-13. Enforcing causal communication.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Mutual ExclusionA Centralized Algorithm (1)Figure 6-14. (a) Process 1 asks the coordinator for permission to access a h

24、ared resource. Permission is granted. Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Mutual ExclusionA Centralized Algorithm (2)Figure 6-14. (b) Process 2 then asks permission to access the same resource. The c

25、oordinator does not reply. Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Mutual ExclusionA Centralized Algorithm (3)Figure 6-14. (c) When process 1 releases the resource, it tells the coordinator, which then r

26、eplies to 2.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5A Distributed Algorithm (1)Three different cases:If the receiver is not accessing the resource and does not want to access it, it sends back an OK mess

27、age to the sender.If the receiver already has access to the resource, it simply does not reply. Instead, it queues the request.If the receiver wants to access the resource as well but has not yet done so, it compares the timestamp of the incoming message with the one contained in the message that it

28、 has sent everyone. The lowest one wins. Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5A Distributed Algorithm (2)Figure 6-15. (a) Two processes want to access a shared resource at the same moment. Tanenbaum &

29、 Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5A Distributed Algorithm (3)Figure 6-15. (b) Process 0 has the lowest timestamp, so it wins. Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007

30、 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5A Distributed Algorithm (4)Figure 6-15. (c) When process 0 is done, it sends an OK also, so 2 can now go ahead.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-23922

31、7-5A Token Ring AlgorithmFigure 6-16. (a) An unordered group of processes on a network. (b) A logical ring constructed in software.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5A Comparison of the Four Algorit

32、hmsFigure 6-17. A comparison of three mutual exclusion algorithms.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Global Positioning Of Nodes (1)Figure 6-18. Computing a nodes position in a two-dimensional space

33、.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Global Positioning Of Nodes (2)Figure 6-19. Inconsistent distance measurements in a one-dimensional space.Tanenbaum & Van Steen, Distributed Systems: Principles a

34、nd Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Election Algorithms The Bully AlgorithmP sends an ELECTION message to all processes with higher numbers.If no one responds, P wins the election and becomes coordinator.If one of the higher-ups answers, it takes over. Ps

35、 job is done.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5The Bully Algorithm (1)Figure 6-20. The bully election algorithm. (a) Process 4 holds an election. (b) Processes 5 and 6 respond, telling 4 to stop. (

36、c) Now 5 and 6 each hold an election.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5The Bully Algorithm (2)Figure 6-20. The bully election algorithm. (d) Process 6 tells 5 to stop. (e) Process 6 wins and tells

37、everyone.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5A Ring AlgorithmFigure 6-21. Election algorithm using a ring.Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-H

38、all, Inc. All rights reserved. 0-13-239227-5Elections in Wireless Environments (1)Figure 6-22. Election algorithm in a wireless network, with node a as the source. (a) Initial network. (b)(e) The build-tree phaseTanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5Elections in Wireless Environments (2)Figure 6-22. Elect