11.Time & Clocks Flashcards
What is “clock drift”?
The DIFFICULTY of maintaining synchronization once achieved
What is Christian’s Clock Synchronization?
“Time server”
-Client set their own time = reply + rtt/2
(assume time-out = time-back)
What is the Berkeley algorithm for calculating time?
- Master processor
- polls slaves
- average results +own time
What do the slaves receive after Berkeley calculation?
it’s own delta (+/-)
What happens if master in Berkeley algorithm fails?
Distributed election algorithm to elect replacement from slaves
What kind of networks are Cristian’s and Berkeley algorithm used in ?
Intranet
What is the protocol used for calculating time in a larger scale internet?
Network Time Protocol (NTP)
What two types of servers are the in a network with NTP?
- Primary (UTC clock)
- Secondary(Synchronized with primary)
Ways to synchronise server in NTP network?
- Multicast mode
- Procedure call mode
- Symmetric mode
What method of synchronization is used on high-speed LAN, how does it work?
Multicast
- Server broadcasts time to all secondaries at once
- Each clock resets (+small delay)
How does the procedure call mode for synchronization work?
- Christians Algorithm
- server replies with time
When is procedure call synchronzation used?
- when multicast unsupported
- for higher accuracy
What synchronization mode do we use when the highest accuracy is required?
Symmetric mode
How does symmetric mode for synchronization work?
- Messages exchanged
- data built up
- improve sync over time
- each message contains timing info about the previous message received
What can we calculate with the timing info in symmetric mode sync messages?
OFFSET (between 2 clocks)->
oi -di /2 <=o<=oi+di/2
where di: transmission time of two messages
How do NTP servers measure the reliability of the other server?
Identify lowest d value my filtering successive (o,d) values
How can every event in a single processor be uniquely ordered in time?
using the local clock
Why not use local clock to order events in distributed system?
synchronisation is not sufficiently good
What are some simple principles for deducing the order of events?
-Two events happen in the same process? The occur in the order given by the process
-If message is sent from one process to another?
Sending before receiving
What is a logical clock?
a monotonically increasing software counter
Where is a logical clock L?
Within a process
What is a logical clock L used for?
timestamping events
How is the logical clock L used?
- L++ before event
- each message contains current L (t)
- Each message received set : = max(L,t)+1
What can we deduce about the logical clocks L(e1),L(e2) if e1 happens before e2? (Lamport’s clock)
L(e1)
Can we deduce the ordering of events from their timestamps? (Lamport’s clock)
nope
What is a vector clock in a system with n processes?
an array of n integers
Where does a vector clock exist?
Each process has it’s own
What are the initial values in a vector clock?
all zeroes
What happens when an event occurs in process i (Vector clocks)?
V[i]= V[i]+1
How do the other processes know an event has occurred in a different process?
- they shall receive message from the process
- message contains their vector clock
- merge it with processes vector clock
What do Vector clocks capture that Lamport’s do not?
causality
What can we deduce about the vector clocks V(e1),V(e2) if e1 happens before e2? (Vector clock)
V(e1)
Can we deduce the ordering of events from their timestamps? (Vector clock)
YA
What is an advantage of vector clocks?
We don’t end up with arbitrary, unnecessary orders
What is the cost of vector clocks?
extra amount of data in a timestamp