5 - Sync and Clocks Flashcards
Temporal Ordering
Exact time not needed but order is important
UTC
Universal Coordinated Time
International Atomic TIme (TAI) is based on
electron transition frequency of calcium 133
UTC = TAI - ????
leap seconds
Precision
Keep deviation within specified bound
Accuracy
Keep deviation from actual time within specified bound
Internal Sync
Sync clocks to improve precision but not neccessarily accuracy
Berkeley Algorithm
Time server sends time to all,
difference is returned,
average is calculated,
average - each computers difference is sent back to each computer
Negative Time adjustments are bad. Why?
Timestamps are not monotonically increasing and events on the same computer can have smaller timestamps than earlier events
Lamport Clock
Each process maintains and adjusts local counter.
Weak consistency
Lamport Clock: Event is within Pi
Ci is incremented by 1.
Lamport Clock: Message is sent by Pi
timestamp ts(m)=Ci is attached.
Lamport Clock: Message is sent by Pj
local counter Cj is set to max{Cj,ts(m)}; then Ci +1 before passing m to app
Weak Consistency Guarantee
a -> b => ts(a) < ts(b)
if a happened before b, always smaller timestamp but if a timestamp is smaller, not necessarily before b
Strong Consistency Guarantee
a->b <=> ts(a) < ts(b)