Unformatted text preview:

1CS677: Distributed OSComputer ScienceLecture 10, page 1Last Class: Naming• Name distribution: use hierarchies• DNS• X.500 and LDAPCS677: Distributed OSComputer ScienceLecture 10, page 2Canonical Problems in Distributed Systems• Time ordering and clock synchronization• Leader election• Mutual exclusion• Distributed transactions• Deadlock detection2CS677: Distributed OSComputer ScienceLecture 10, page 3Clock Synchronization• Time in unambiguous in centralized systems– System clock keeps time, all entities use this for time• Distributed systems: each node has own system clock– Crystal-based clocks are less accurate (1 part in million)– Problem: An event that occurred after another may be assignedan earlier timeCS677: Distributed OSComputer ScienceLecture 10, page 4Physical Clocks: A Primer• Accurate clocks are atomic oscillators (one part in 1013)• Most clocks are less accurate (e.g., mechanical watches)– Computers use crystal-based blocks (one part in million)– Results in clock drift• How do you tell time?– Use astronomical metrics (solar day)• Coordinated universal time (UTC) – international standard basedon atomic time– Add leap seconds to be consistent with astronomical time– UTC broadcast on radio (satellite and earth)– Receivers accurate to 0.1 – 10 ms• Need to synchronize machines with a master or with one another3CS677: Distributed OSComputer ScienceLecture 10, page 5Clock Synchronization• Each clock has a maximum drift rate r• 1-r <= dC/dt <= 1+r– Two clocks may drift by 2r Dt in time Dt– To limit drift to d => resynchronize every d/2r secondsCS677: Distributed OSComputer ScienceLecture 10, page 6Cristian’s Algorithm•Synchronize machines to a timeserver with a UTC receiver•Machine P requests time fromserver every d/2r seconds– Receives time t from server, Psets clock to t+treply where treplyis the time to send reply to P– Use (treq+treply)/2 as an estimateof treply– Improve accuracy by making aseries of measurements4CS677: Distributed OSComputer ScienceLecture 10, page 7Berkeley Algorithm• Used in systems without UTC receiver– Keep clocks synchronized with one another– One computer is master, other are slaves– Master periodically polls slaves for their times• Average times and return differences to slaves• Communication delays compensated as in Cristian’s algo– Failure of master => election of a new masterCS677: Distributed OSComputer ScienceLecture 10, page 8Berkeley Algorithma) The time daemon asks all the other machines for their clock valuesb) The machines answerc) The time daemon tells everyone how to adjust their clock5CS677: Distributed OSComputer ScienceLecture 10, page 9Distributed Approaches• Both approaches studied thus far are centralized• Decentralized algorithms: use resync intervals– Broadcast time at the start of the interval– Collect all other broadcast that arrive in a period S– Use average value of all reported times– Can throw away few highest and lowest values• Approaches in use today– rdate: synchronizes a machine with a specified machine– Network Time Protocol (NTP)• Uses advanced techniques for accuracies of 1-50 msCS677: Distributed OSComputer ScienceLecture 10, page 10Logical Clocks• For many problems, internal consistency of clocks isimportant– Absolute time is less important– Use logical clocks• Key idea:– Clock synchronization need not be absolute– If two machines do not interact, no need to synchronize them– More importantly, processes need to agree on the order inwhich events occur rather than the time at which they occurred6CS677: Distributed OSComputer ScienceLecture 10, page 11Event Ordering• Problem: define a total ordering of all events that occurin a system• Events in a single processor machine are totally ordered• In a distributed system:– No global clock, local clocks may be unsynchronized– Can not order events on different machines using local times• Key idea [Lamport ]– Processes exchange messages– Message must be sent before received– Send/receive used to order events (and synchronize clocks)CS677: Distributed OSComputer ScienceLecture 10, page 12Happened Before Relation• If A and B are events in the same process and A executed before B,then A -> B• If A represents sending of a message and B is the receipt of thismessage, then A -> B• Relation is transitive:– A -> B and B -> C => A -> C• Relation is undefined across processes that do not exhangemessages– Partial ordering on events7CS677: Distributed OSComputer ScienceLecture 10, page 13Event Ordering Using HB• Goal: define the notion of time of an event such that– If A-> B then C(A) < C(B)– If A and B are concurrent, then C(A) <, = or > C(B)• Solution:– Each processor maintains a logical clock LCi– Whenever an event occurs locally at I, LCi = LCi+1– When i sends message to j, piggyback Lci– When j receives message from i• If LCj < LCi then LCj = LCi +1 else do nothing– Claim: this algorithm meets the above goalsCS677: Distributed OSComputer ScienceLecture 10, page 14Lamport’s Logical Clocks8CS677: Distributed OSComputer ScienceLecture 10, page 15Example: Totally-OrderedMulticasting• Updating a replicated database and leaving it in an


View Full Document

UMass Amherst CS 677 - Naming

Download Naming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Naming and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Naming 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?