Client request the server and get the exact time in return
Tnew = Tserver + T1 + T2/2
Algorithm
Let S be the time server and Ts be its time
Process P requests the time
S prepares response and appends the time Ts from its own clock and sends it back to P
It is a centralized algorithm
Berkeley algorithm
Algorithm
Server sends query to each slave along with its own time
Slaves returns the offset time
Server then calculates the average offset and sends the value to slaves and itself
Slaves sets the time according to the offset given
It is a centralized algorithm
Network Time Protocol
NTP is a standard followed by synchronization clocks on the internet
Synchronizes all participating computers within a few milliseconds of UTC
Survive lengthy losses of connectivity
Authenticate source of data
It is a decentralized algorithm
Logical
Implementing a protocol on all machines within your DS, so that machines are able to maintain consistent ordering of events within some virtual timespan
Methods
Synchronize time between the machines
Assign timestamps to machines => Must be following Causality
Algorithms
Lamport algorithm
Happen Before Relationship => Event happening later should always be assigned with greater timestamp
Transitive relationship
Causally ordered relation
Affect on one event will also affect other event
Concurrent event
Events happening simultaneously
Vector clock
Timestamps (Vector) are in the form [a, b, c, ...] initialized with [0, 0, ...]
Increment vector when event occurs, a for 1st event, b for 2nd event and so on
Timestamp will get updated at receiver during communication by comparing both and taking maximum values of a, b, c, ... respectively
Election Algorithm
Bully algorithm
Every process can be a coordinator
Biggest process can become a coordinator
A dead process is not considered
A process can initiate a election algorithm
Every process is given a unique identifier
Message Sent: Election, Coordinate, Ok
Ring algorithm
When a node notifies that the coordinator is dead it builds and sends election message to nodes
At every step nodes keeps on adding it sown id at the end of the list
The process stops when the initiator receives the message it sent
Node with highest ID is declared to be coordinator
Initiator announces the coordinator by sending messages to nodes
Message Sent: Election, Coordinate
Less space utilization and more efficient than Bully
