Synchronization Problem
In single CPU systems, synchronization problems can be solved with locks / semaphores. Different in a distributed system environment.
Clock Synchronization
Time is unambiguous in a centralized system.
However, in a distributed system, if there was no global agreement on time, clocks might not be synchronized.
The machine with the compiler might believe input.o is up-to-date and hence not recompile it.
Physical Clocks
Every computer has a timer. It is consisted of a precisely machined quartz crystal, it oscillates at a well-defined frequency. It is associated with two registers, the counter and the holding register. The counter decrements by one each time the crystal oscillates and there is an interrupt each time the counter gets to zero. Then the counter gets its value back from the holding register. Each interrupt is called one clock tick.
At every clock tick, the time stored in memory will be incremented by one.
Different crystals do not oscillate at the same frequency, hence causing differences which is called clock skew.
Basis for keeping global time is called UTC (Universal Coordinated Time). It is a worldwide standard. Offers accuracy of 50 nsec. Many computers are equipped with UTC receivers to obtain UTC time.
Clock Synchronization Algorithms
If one machine has UTC receiver, other machines try to keep synchronize with this machine. If no machines has UTC receivers, each machine tracks its own time and try to keep all machines together as well as possible.
TO READ
Network Time Protocol
Cristian’s algorithm
Let clients contact time server (equipped with UTC receiver) for time. However, there are message delays and we need to estimate them.
The Berkeley Algorithm
When no machine has UTC receiver.
Time server polls every machine periodically to ask what time is there and computes the average time.
The time daemon’s time must be set manually by the operator periodically.
Logical vs Physical Clocks
Some algorithms only need internal consistency of clock logical clock
Goal is for processes to agree on the order in which events occur.
Lamport Algorithm
Corrections to time can be made by adding a positive value, never by subtracting one.
When process that receives message realize its clock is less than sender’s clock, receiver’s clock is increased by one.
Total-ordered multicast
Can be solved using Lamport logical clocks.
When node receives a message, add message to queue ordered by timestamp.
Vector Clocks
Problem is that Lamport clocks do not capture causality.
Constructed by letting each process maintain a vector clock with
- is the number of events that have occurred so far at - logical clock at
- , then knows that k events have occurred at /
Mutual Exclusion
Token-based solution
Only one token, and it is passed around, whoever has the token has access to the shared resource. Issue is that token can be lost.
A centralized algorithm
Elect one process as coordinator. Other processes ask coordinator for permission. Issue is that coordinator is a single point of failure .
A distributed algorithm
To access a critical section:
- Builds a message with
- name of critical section
- process number
- current time
- Sends the message to all other processes
When a process receives a request message
- If it is not in critical region and does want to enter, reply OK
- If it is inside, does not reply
- If it is not inside and wants to enter, compares timestamp and the lowest one wins.
Problem is that it has n points of failure
A token ring algorithm
Processes form a cycle, once a process gets the token
- if it wants to enter the critical section, enter, does the work, release and pass the token
- otherwise, just pass the token
Problem:
- Token can be lost, and detection is challenging
A decentralized algorithm
Similar to distributed algorithm, but only needs the majority vote.
Comparison
Election Algorithms
Bully Algorithm
Node with highest id wins
A ring algorithm
When a process notice the coordinator is not functioning
- Builds ELECTION message containing its own process id
- It sends it to the next node on the ring
- At each step, the node adds its own id
- When the message makes a cycle, type is changed to COORDINATOR and circulated once more to inform who is the new coordinator.