MISM 95-702 Distributed Systems 1 Distributed Systems Time and Global StatesMISM 95-702 Distributed Systems 2 Learning Goals • To understand: – The challenge of time in a distributed system – How to synchronize distributed clocks – How you can assess the state of a distributed systemExample • Browse to http://tinyurl.com/702clock – This is your local clock • Take out a piece of paper • Solve by hand: 643 * 192 – Timestamp each line after you complete it • E.g. MISM 95-702 Distributed Systems 3 Arithmetic Timestamp 643 92 192 96 1286 112 …Time in distributed systems • Who finished first? • How could decide computationally who finished first? • Can you use the timestamps? – Are they reliable? – Why or why not are they reliable? • How could you make the timestamps more reliable? • What other approach could you take? MISM 95-702 Distributed Systems 4MISM 95-702 Distributed Systems 5 Skew and drift • Why can’t we have a global clock in a distributed system? • Because clocks are imperfect: – Clock skew – different times • Two clocks will have two different times. – Clock drift – different speeds • Each clock varies in speedTime • What is a second? – 9,192,631,770 periods of transition between the two hyperfine levels of the ground state of Caesium-133 (Cs133) • Ordinary quartz crystal clocks – Drifts 1 second every 11 days • What can a computer do in a second? – Intel Core i7: ~100 Billion Instructions MISM 95-702 Distributed Systems 6MISM 95-702 Distributed Systems 7 Clocks • Cesium clocks – Expensive • GPS receiver – Less expensive – (GPS system has cesium clock(s))MISM 95-702 Distributed Systems 8 3 Days in the life of my Mac 3/20/13 11:55:00 PM ntpd[26] time reset -1.782968 s 3/21/13 12:47:41 PM ntpd[26] time reset -0.719539 s 3/21/13 4:30:51 PM ntpd[26] time reset +0.327154 s 3/21/13 7:55:42 PM ntpd[26] time reset -0.238545 s 3/21/13 10:29:06 PM ntpd[26] time reset +0.364890 s 3/22/13 11:28:51 AM ntpd[26] time reset -1.058507 s 3/22/13 3:09:51 PM ntpd[26] time reset +0.572059 s 3/22/13 9:33:25 PM ntpd[26] time reset -0.165838 s 3/22/13 10:19:11 PM ntpd[26] time reset +1.000670 s 3/23/13 7:50:47 AM ntpd[26] time reset -0.171427 s 3/23/13 10:10:30 AM ntpd[26] time reset +0.133970 s 3/23/13 11:55:39 AM ntpd[26] time reset -0.136061 s 3/23/13 12:37:57 PM ntpd[26] time reset -0.526902 s 3/23/13 1:09:51 PM ntpd[26] time reset +0.400528 sDemonstrate Internal Synchronization • Informally: – Internally synchronize your watches • Formally: – All clocks agree within some bound D. MISM 95-702 Distributed Systems 9Demonstrate External Synchronization • Informally: – Externally synchronize your watches • Formally: – Each clock Ci is accurate to UTC within some bound D – UTC is Coordinated Universal Time MISM 95-702 Distributed Systems 10MISM 95-702 Distributed Systems 11 Network Time Protocol Design Goals: • Sync with UTC over Internet • Provide reliability via redundancy • Scale to large number of clients and servers • Defend against Mallory Graphic source: http://en.wikipedia.org/wiki/Network_Time_ProtocolNTP Simulation • Work in pairs • Both students should have the clock demo page running – http://tinyurl.com/702clock • Use only ONE sheet • ONE student starts the process – fill in (a) and pass to student TWO • student TWO – fills in (b) upon arrival – then fills in (c) and passes form back to student ONE • student ONE – fills in (d) – calculates (e-i) – puts the value of (i) in their own clock demo (ONE only) • Both students – eyeball your clocks and see if they are nearly synchronized MISM 95-702 Distributed Systems 12MISM 95-702 Distributed Systems 13 a Sent time b Received time c Sent-back time d Returned-back time Calculation UDP Packet (reusable) eTotal round trip time (d-a) f Remote processing time (c-b) g Delay each way (e-f)/2 hOffset relative to remote (d-g) - c i Amount to adjust local clock -h a Sent time b Received time c Sent-back time d Returned-back time Calculation UDP Packet (reusable) eTotal round trip time (d-a) f Remote processing time (c-b) g Delay each way (e-f)/2 hOffset relative to remote (d-g) - c i Amount to adjust local clock -h a Sent time b Received time c Sent-back time d Returned-back time Calculation UDP Packet (reusable) eTotal round trip time (d-a) f Remote processing time (c-b) g Delay each way (e-f)/2 hOffset relative to remote (d-g) - c i Amount to adjust local clock -hMISM 95-702 Distributed Systems 14 Summarize • Summarize in your own words how NTP synchronization works • What is NTP synchronized time good enough for? – Median error is 2-5ms but has a long tail • Source: Chi-Yao Hong , Chia-Chi Lin , Matthew Caesar, Clockscalpel: understanding root causes of internet clock synchronization inaccuracy, Proceedings of the 12th international conference on Passive and active measurement, p.204-213, March 20-22, 2011, Atlanta, GA • What are its shortcomings?Google Time & Leap Smears • What was the problem? • Why is a second important to Google? • What stratum NTP servers do they have internally? • What is their solution? – What is a Leap Smear? – Is it an example of internal or external synchronization? MISM 95-702 Distributed Systems 15Distributed Systems Histories • Mind experiment – Take a set of index cards – List 20 things you did so far today • Ever since you woke up. – Be detailed – Be sure to include interactions with people in this class MISM 95-702 Distributed Systems 16Global State Terminology Define by example (using the cards you just made): • Process history • Global history • Happened-before relation • Cut • Consistent cut • Inconsistent cut • Linearization • I recommend you read Coulouris – And know definitions for final exam MISM
View Full Document
Unlocking...