CS计算机代考程序代写 database compiler distributed system algorithm COMP3221: Distributed Systems

COMP3221: Distributed Systems
Time Synchronization
Unit Coordinator
Dr Nguyen Tran
School of Computer Science
The University of Sydney
Page 1

Time matters…ex. (1)
– A bank replicates two copies of an account database in New York City (NYC) and San Francisco (SF) so that a query is always forwarded to the nearest city while updates must be carried out at both sites
– In a centralized system,
– Process A makes a system call to get the time.
– Later, process B makes a system call for time, which is will be higher or equal to the time returned to process A.
SF NYC
– A client in SF adds $100 to his account which currently contains $1000 while the bank add 1% interest in NYC.
– Updating a replicated database and leaving it in an inconsistent state: $1111 in SF and $1110 in NYC
– The problem is that both sites perceive the updates in different order leading to inconsistencies The University of Sydney
Page 2

Time matters…ex. (2)
– In a distributed system, if there is no global agreement on time, each machine may have slightly different time.
– Compiler will not run as the time of last complied version is greater than latest source code.
The University of Sydney Page 3

Outline
– Time
– Physical Time
– Logical Time
– Multicast
– Mutual exclusion – Leader election
The University of Sydney
Page 4

Synchronization
Physical Time
The University of Sydney Page 5

Time
• Solar day: Interval between two consecutive events of the sun’s reaching its highest apparent point in the sky = 24 hours = 3600 seconds.
• Basis for the Greenwich Mean Time (GMT) standard The University of Sydney
– Howtimeisactuallymeasured?
– Timehasbeenmeasuredastronomically
Page 6

Time
– Earth is slowing down. Period of earth’s rotation is not constant – Due to tidal friction, atmospheric drag.
– Astronomers introduced Mean solar second (averaged over large # of days)
– Physicists took over in 1958 with the invention of the atomic clock.
– By counting the transitions of the cesium 133 atom
The University of Sydney First atomic clock [http://www.npl.co.uk/people/louis-essen] Page 7

Time
– Second = Time it takes the cesium 133 atom to make exactly 9,192,631,770 transitions.
– Major laboratories in the world periodically update the Bureau of International de l’Heure (BIH) in Paris on how many times its clock has ticked. BIH averages these to produce International Atomic Time (TAI).
– 9,192,631,770 number of transitions was selected to make the atomic second was equal to mean solar second.
– Can you think of any potential problem ?
The University of Sydney Page 8

Time
– Atomic seconds are of constant length, unlike solar seconds.
– Leap seconds are introduced when necessary to keep in phase
with the sun.
– If the discrepancy between atomic time and solar time grows to 800msec, BIH introduces a leap second.
– This corrected time system is called Universal Coordinated Time (UTC).
The University of Sydney Page 9

Leap Seconds
– Computerized systems could malfunction if leap seconds are not handled properly.
– RedHat crash in 2012. THE INSIDE STORY OF THE EXTRA SECOND THAT CRASHED THE WEB, [https://www.wired.com/2012/07/leap-second- glitch-explained/]
– Operating systems must have special software to account for leap seconds as they announced.
– Electric power companies raise their frequency to 61Hz to synchronize the timing of their 60Hz clocks to UTC.
– 37 leap seconds were added so far. – The most recent one was on 31/12/2016
The University of Sydney
Page 10

Accurate time broadcasters
– Atomic clocks
– Expensive to have one in every computer
– GPS
– 29 satellites circulating around the orbit
– Originally developed for US military
– Each GPS satellite has up to four atomic clocks
– Satellites continuously broadcasts its position and time
– Short radio wave stations transmit a short pulse at the start of every UTC second
– NIST WWV station from Fort Collins, Colorado
The University of Sydney Page 11

Computer Clocks (Timers)
– Precisely machined quartz crystal.
– When kept under tension, quartz crystals oscillate at the defined frequency depending on;
– The kid of crystal
– Howitiscut
– The amount of tension
The University of Sydney
Page 12

Computer Clocks (Timers)
– Hardware clock
– At each clock tick, one is added to the time stored in a battery-backed
up CMOS RAM
– When the CPU is turned off, the time in the CMOS RAM keep being incremented
– Software clock
– It starts running at boot time and synchronize to the hardware clock
– Used by the operating system to indicate a rough approximation of time
– Multiple CPUs means multiple clocks
– The frequency of two crystals cannot be exactly the same
– Software clocks progressively get out of synch
– The difference returned by two clock values is called clock skew
The University of Sydney
Page 13

Computer Clocks (Timers)
– Realtimerscauseaninterrupt (ticks) H times every second.
– e.g.H=60shouldgenerate216,000 ticks per hour. In practice, it will be in the range of 215,998 – 216,002.
– Maximumdriftrateisspecifiedby the manufacturer
– Therelationbetweenclocktime and UTC when clocks tick at different rates (Ideally, C(t) = t)
– TheskewoftheclockisdC/dt-1 – Two problems
1. How do we synchronize them with real-world clocks ?
2. How do we synchronize the clocks with each other ?
The University of Sydney
Page 14

Algorithm 1 : Network Time Protocol
–
– 1. 2. 3. 4.
Clients synchronize its time with a time server which have an accurate time, e.g. an atomic clock.
– How do we account for propagation delays ?
Cristian’s algorithm [1989]
A sends a message to B with its timestamp T1 set to its local clock value
Upon reception, B records the current time T2 of its local clock
B returns a response message to A with T2 and the current time T3 of its clock Upon reception, A records the current time T4 of its local clock
The University of Sydney
Page 15

Algorithm 1 : Network Time Protocol
Cristian’s algorithm [1989]
– If clock rate increases monotonically (without even decreasing) and
– If both message transmissions take roughly the same time
– Round-trip time = (T2-T1)+(T4-T3)
– OffsetofArelativetoB=T4 -T3 -RTT/2
– A can re-adjust its time to T3 + RTT/2
– This result is not accurate but gives an acceptable approximation
The University of Sydney
Page 16

Algorithm 1 : Network Time Protocol
–
1. 2.
–
– –
–
NTP is set up pair-wise between servers
– i.e. B will also probe A for its current time
Run Cristian’s algorithm 8 times and records the 8 output pairs i (0 ≤ i < 8) The pair with the minimum RTT/2 is chosen as the most precise offset To avoid servers with accurate clocks to adjusting their clocks, Servers are divided into strata A server having an atomic clock operates at stratum 0 A server synchronized with a server at stratum j operates at stratum j+1 Accuracy is in the range of 1-50msec The University of Sydney https://www.ntp-zeit.de/index-en.htm Page 17 Algorithm 2 : The Berkeley Algorithm – What if there is no server of stratum 0? Can we still relatively synchronize? – Server is active, it starts the algorithm periodically to resynchronize nodes 1. Time server (a.k.a., daemon) sends a “what time is it?” request to all nodes 2. The nodes answer with their local clock value 3. Once the server has received values from the nodes – It computes an average value – It sends it to the nodes for them to adjust – The time can be far from the UTC, hence the time is not absolutely synchronized – This relative synchrony is sufficient in many cases The University of Sydney Page 18 Algorithm 2 : The Berkeley Algorithm – (a) the time daemon sends a request to all nodes – (b) the nodes answer the time daemon about their local clock – (c) the server computes the average and tells nodes to adjust their clock The University of Sydney Page 19 Pros and Cons of Physical Time – Pros: very powerful – Universal representation of the occurrence time of all distributed events – All events are made comparable (total order) – Cons: hard to achieve – This physical time instruments are difficult to synchronize • They require the message transmission to have an upper-bounded duration • They sometimes require message duration to be similar (also lower bounded) – In large-scale system, the message delay is typically • High (in seconds) and the synchronization can be biased by message delays • Heterogeneous(LAN:milliseconds,WAN:seconds)3ordersofmagnitudefar apart • Unpredictable, unbounded message delays and message can be delivered in disorder – Let’s look at logical time instead, where events may not always be comparable (partial order) The University of Sydney Page 20 Synchronization Logical Time The University of Sydney Page 21 Logical time – It is not always necessary to synchronize all nodes the same as physical (real) time – E.g. it is adequate that two nodes agree that input.o is outdated by a new version of input.c to properly compile. – Keeping track of the order of events is what matters ! – Lamport (in 1978) showed that; – If two processes do not interact, it is not necessary that their clocks be synchronized – What usually matters is that they agree on the order in which events occur, not what time it is. The University of Sydney Page 22 Logical time – Definition of the relation called “happens-before” – “a happens before b”, denoted by a → b, is true if: – a and b are events from the same process such that a occurs before b, or – if a is the event of a message being sent by one process and b is the event of the same message being received by another process, or – it exists some event c such that a → c and c → b (i.e., transitive closure) – If two events, x and y, happen in different processes that do not exchange messages (not even indirectly via third parties); – thenx→yisnottrue,butneitherisy→x. – In this case, x and y are said to be Concurrent The University of Sydney Page 23 Lamport’s logical clocks – Goal:tomakethe“happens-before”relationvisibletoprocesses – Keyidea: – eachprocessshouldkeeptrackoftheorderinwhicheventsappeartotake place locally – let’sintroduceafunctionlogicalclockC:events↦integers – Lamport’slogicalclocksalgorithm: – 1. Each process pa maintains a local counter Ca. 2. Before executing an event (i.e. sending a message to another process or an internal event), pa increments Ca, i.e. Ca ← Ca + 1. 3. When process pa sends a message m to process pb, it sends Ca as the time stamp of the message. 4. Upon the receipt of a message, process pb adjust its own local counter as Cb ← max{Ca, Cb} 5. pb executes step 2 and delivers the message to the application Result:IfPa →Pb thenCa → < new local clock> to illustrate the clock value after the reception of an ack.
7.3 represents the message was received at process 3 at clock 7. Then, max{local, received} is taken to reach the new local clock.
4 5 6 7.3->7 6.1->7 7.2->7 p13ACBAB C
7.3->7 7.2->7 p2 2 B A B C A C
3 4 6.1->6 7
567
7.2->7 7.3->7 6.1->7
p3 4
Messages are delivered in the order of their clocks, B, C, A, everywhere (lower
BCA
CAB
–
timestamps and IDs order)
The University of Sydney Page 36

Multicast
Causal ordered multicast
– Goal: broadcasting messages that got delivered only if all causally preceding messages have already been delivered
– Each process maintains a vector clock (similar as before) and a priority queue of messages (waiting to be delivered to the top layer)
– Process pi increments VCi[i] only when sending a message (not when receiving) and pj adjusts VCj when receiving a message.
– pj postpones delivery of m from pi until both conditions are met: 1. ts(m)[i] = VCj[i] + 1
2. ts(m)[k] ≤ VCj[k] for k ≠ i
The University of Sydney Page 37

Multicast
Causal ordered multicast (con’t)
– TakeVC2=[0,2,2],ts(m)=[1,3,0]fromp0.Whatinformationdoesp2 have, and what will it do when receiving m (from p0)?
The University of Sydney Page 38

Synchronization
Mutual Exclusion
The University of Sydney Page 39

Mutual exclusion
– Concurrent access to the same resource may corrupt the resource, or make it inconsistent.
– Problem: Multiple processes in a distributed system want exclusive access to some resource
The University of Sydney Page 40

Mutual exclusion
Centralized algorithm
– Fairandeasytoimplement
– Requiresonlythreemessagesperuseofresource(request,grant,
release)
– No process ever waits foreveràno starvation
– But,singlepointoffailure The University of Sydney
Page 41

Mutual exclusion
Decentralized algorithm
– Principle. Assume every resource is replicated n times, with each replica having its own coordinator ⇒ access requires a majority vote from m > n/2 coordinators. A coordinator always responds immediately to a request.
– Assumption: When a coordinator crashes, it will recover quickly, but will have forgotten about permissions it had granted.
– Problem: A coordinator may grant permission to some node whereas it already did it to another node
The University of Sydney Page 42

Mutual exclusion
Distributed algorithm – Ricart and Agrawala algorithm
– Principle.Thesameasbeforeexceptthatacknowledgmentsarenot sent. Instead, replies (i.e., grants) are sent only when
– Thereceiverhasnointerestinthesharedresourceor
– Thereceiveriswaitingfortheresource,buthaslowerpriority(knownthrough
comparison of timestamps)
– Twoprocesseswanttoaccessasharedresourceatthesamemoment
– Process0hasthelowesttimestamp,soitwins.
– Whenprocess0isdone,itsendsanOKalso,so2cannowgoahead.
The University of Sydney Page 43

Mutual exclusion
– Distributed algorithm – Ricart and Agrawala algorithm
– Single point of failure is replaced by n-point of failures – More message exchanges
– Getting permission from everyone is really an over-kill
The University of Sydney
Page 44

Mutual exclusion
Token ring algorithm
– Principle.Organizeprocessesinalogicalring,andletatokenbe passed between them. The one that holds the token is allowed to accessing the resource (if it wants to).
The University of Sydney
Page 45

Mutual exclusion
Comparison of the last four solutions
– Messages and delay are necessary to get granted the permission to access the resource (this means entering the critical section) or to release the permission (exiting it)
The University of Sydney Page 46

Conclusion
– Time matters in distributed systems
– Physical time
– It is expensive to have accurate physical time on every computer
– Synchronization with someone who knows the accurate time
• NetworkTimeProtocolandBerkeleyAlgorithm
– Logical time
– Keepingtrackoftheorderofeventsiswhatmatters!
– To make the “happens-before” relation visible to processes à Logical clocks
– To make also the “did-not-happen-before” relation visible à Vector clocks
– Ordered multicasting deliver messages in the same order at all nodes
– Providing exclusive access and leader election are practical challenges for many distributed systems
The University of Sydney Page 47

What’s Next ?
– Tutorial 5 on Wednesday.
– Assignment 1 is available – Good Luck !
– Next week: Consistency in distributed systems – See you all next week !
The University of Sydney
Page 48