Seminar 4: Physical clock synchronization methods with gRPC in python
Goal: To study the importance of clock synchronization between threads by using the Cristian's algorithm concept
Background: Why is the physical clock synchronization between computer nodes needed?
1. There is no shared global clock
2. The need for synchronization originates when node/processes need to execute concurrent events following a partial order that is bounded to time (lower and upper time bounds). For instance, consider two threads competing for locking the access to a resource, e.g., database. Assuming that there is no deadlock, once a thread has locked the resource (completely), it can use the resource indefinitely (if there is not time-outs). Thus, time can allow the system to configure limited access time (time-out) to a resource, such that the system does not starve.
In Distributed systems, time is synchronized so that multiple nodes/processes can:
- Cooperate and schedule operations
- Agree on the ordering of events
- Determine validity of data
- Record the lifespan of an event
- Analyze the system performance
Typically, GPS and NTP are available time source mechanisms to synchronize a distributed system (when connectivity to Internet is available). Other mechanisms are also available when there is not Internet connectivity (We will explore these later ones in this seminar).
Berkeley algorithm: Berkeley algorithm is a clock synchronization technique used in distributed systems. The algorithm assumes that each machine node in the network either doesn’t have an accurate time source or doesn’t possess an UTC server. It is mainly for systems with no access to external accurate timing signal.
Cristian Algorithm: Cristian algorithm is a clock synchronization algorithm is used to synchronize time with a time server by client processes. This algorithm works well with low-latency networks where Round Trip Time is short as compared to accuracy while redundancy-prone distributed systems/applications do not go hand in hand with this algorithm.
Cristian's algorithm works between a process P, and a time server S connected to a time reference source. Put simply:
- Client requests the time from server at time t0.
- After receiving the request from client, server prepares a response and appends the time T from its own clock.
- Client receives the response at time t1 then sets its time to be T + RTT/2, where RTT=t1-t0.
Prerequisites: Python (Python Download) or Python Installation: https://realpython.com/installing-python/ and gRPC
Exercise: We will get acquainted with the Cristian Algorithm by using a thread in python, and understand how to interconnect threads later. Also we would implement multiple threads using gRPC to understand how the Cristian algorithm works.
The code for the above implementation is given here. (Code)
- clock_sync.py
Running this simple code gives an understanding of the Cristian algorithm to synchronize time between a client and a server.
Task 1: To familiarize ourselves with the concept, implement a similar clock synchronization with a clock-update function to show the current clock time with five (5) threads using gRPC in python.
Task 2: In Seminar 3, we already learn how to implement Exponential back-off function with multi-threads by using gRPC. You should implement the last seminar exercise (your defined function) to achieve the Cristian algorithm by passing arguments either from the server or client sides.
- The result of your implementation should be similar to this (here I had an example on datetime function in seminar 3)
Note: This is just an illustration
- Server Implementation
- Client Implementation
Deliverables: For each task, please include the source python file, and also the screenshot of results in terminals. Then put all the file in a single zip.
For more reads: