Seminar 5: Lamport Clock Algorithm and Vector Clock Algorithm in python
Goal: To study and practice the concept of logical clocks (Lamport and Vector)
Background: Physical clock timestamps are insufficient to determine the correct execution behavior of distributed applications. As a result, logical clocks are required to enforce ordering of events. A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. It allows global ordering on events from different processes in distributed applications by relying on monotonic counters. In this seminar, we will explore two logical clocks: Lamport clocks and Vector clocks.
- The Happened-before relationship:
- If a and b are events in the same process, and a occurs before b, then a->b is true
- If a is the event of a message being sent by one process, and b is the event of the message being received by another process, then a->b is also true
- Transitive: if a->b and b->c, then a->c
Lamport’s logical clocks:
- All processes agree on time C(e) for every event e
- C must always go forward (increase), never backward (decrease)
- If a -> b , then C(a) < C(b)
- For all distinctive events a and b, C(a) ≠ C(b)
- Implementation (Each process Pi maintains local counter Ci)
- Pi executes Ci= Ci + 1 before executing an event (e.g. sending a message over the network)
- When sending message m to Pj, Pi sets m’s timestamp ts(m)=Ci(after having executed step 1)
- Upon receiving message m, Pj adjusts its own local counter as Cj <- max{Cj, ts(m)}, after which it executes step 1 (Cj= Cj + 1) and delivers the message to application.
- Issue: As shown in figure - Even though C(h) < C(c), we can not say whether h happened before c or not. In other words, we cannot establish the causal relationship between these two events. The solution to this problem is to make use of Vector Clock.
Vector clocks:
- A vector clock uses a vector of integer variables, e.g., depicting each process/node in the system, for determining the partial ordering of events as nodes/processes execute operations and exchange messages. Vector clocks can be used to detect causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's logical clock.
- Capture causality: if VC(a) < VC(b), then event a is known to causally precede event b
- Implementation (Each process Pi maintains a vector clock VCi)
- Pi executes VCi[i] = VCi[i] + 1 before executing an event
- When Pi sends message m to Pi, it sets m’s timestamp ts(m) equal to VCi (after having executed step 1)
- When Pj receives m, it executes VCj[k] = max{VCj[k], ts(m)[k]} for each k, after which it executes step 1 and delivers the message to the application.
- As shown in Figure, VC(h)|||VC(c), VC(f)|||VC(c). (|| Concurrent)
Exercise-1: We will get acquainted with the Lamport clock algorithm in python. To easy get acquaintance with the concept, we have created a graphical interface by tkinter to display the algorithm. The tkinter package (“Tk interface”) is the standard Python interface to the Tcl/Tk GUI toolkit.
- The code for the above implementation is given here for you. (code)
$ python lamport1.py
In function on_click:
x, y = event.x, event.y
# Event ("L", x, process_number) -- Local event
if self.adding_mode.get()=="L":
process_number=self.find_closest(y)
self.create_rhombus(x, self.heights[process_number]) # rhombus means local event
self.events.append(("L", x, process_number))
# Event ("M", from_x, to_x, from, to) -- Message sent
if self.adding_mode.get()=="M":
process_number=self.find_closest(y)
self.current_circle=self.create_circle(x, self.heights[process_number])
self.previous_process=process_number
self.previous_x=x
In function on_release
# message received
self.create_circle(x, self.heights[process_number])
self.canvas.create_line(self.previous_x, self.heights[self.previous_process],
x, self.heights[process_number], arrow=LAST, width=2)
self.events.append(("M", self.previous_x, x, self.previous_process, process_number))
In function calculate_timestamps
# Output #(x, process_number, timestamp)
def calculate_timestamps(self):
# Event ("L", x, process_number)
# Event ("M", from_previous_x, to_x, from previous process, to )
# ->
# ("L", x, process_number) -- Local event for each process
# ("S", x, process_number, msg_num) -- Event for message sent
# ("R", x, process_number, msg_num) -- Event for message received
counter=0
split_events=[]
for event in self.events:
if event[0]=="M":
split_events.append(("S", event[1], event[3], counter))
split_events.append(("R", event[2], event[4], counter))
counter+=1
else:
split_events.append(event)
sorted_events = sorted(split_events, key = lambda x: x[1]) # based on x
messages={} ## message loading
## current_vectors store the timestamps
current_vectors=np.zeros((self.N_PROCESSES, self.N_PROCESSES), dtype=np.uint8)
# Output #(x, process_number, timestamp)
timestamps=[]
for event in sorted_events:
event_type, x, process_number=event[0], event[1], event[2]
if event_type=="L":
current_vectors[process_number, process_number]+=1 # increase by 1
elif event_type=="S":
current_vectors[process_number, process_number]+=1 # increase by 1
messages[event[3]]=current_vectors[process_number,process_number] # timestamp
else:
received_message=messages[event[3]]
result=max(current_vectors[process_number, process_number],received_message)
current_vectors[process_number, process_number]=result+1
timestamps.append((x, process_number, current_vectors[process_number, process_number]))
return timestamps
Task-1: Based on "lamport1.py" in exercise-1, please change the lamport clock algorithm to vector clock algorithm.
- your implementation should achieve a result similar to this screenshot.
Exercise-2: We will get acquainted with another Lamport clock algorithm with threads in python. Threads are used to represent the processes and queues are used as channels of communication for the messages. The logical clocks are simply counters in each thread and using the “resource” is simulated by a sleep. There are 3 processes in total and process “A” is initially granted the resource.
- The code for the above implementation is given here for you (code). The code is from the source link
$ python lamport2.py
In the class module:
# use thread to create process object $ class Process(threading.Thread)
Task-2: From previous seminars, we already learn how to implement some functions with multi-threads by using RPyC ThreadedServer in python. For this task:
- Integrate the function from lamport2.py into the class module of RPyC server communication
- Write codes similar to below lines into client side to invoke the method from the remote server, therefore the server can create 3 threads for 3 processes. In this way, the class Process could be nested into server class.
- t1 = Process("A", initially_granted_proc, list(procs - set("A")))
- t2 = Process("B", initially_granted_proc, list(procs - set("B")))
- t3 = Process("C", initially_granted_proc, list(procs - set("C")))
- Write codes similar to below lines into client side to invoke the method from the remote server, therefore the server can create 3 threads for 3 processes. In this way, the class Process could be nested into server class.
- Note that you can make small changes about the source code while you integrate it in the server side. you can also consider exposed implementations.
- The result in server should be similar to this (No print statement is required in the client side).
Deliverables: For each task, please contain the source python file, and also the screenshot of results in terminals. Then put all the file in a single zip.
- If you use different implementations to achieve task-2 (similar results in the server side), please submit all the implementations you have for more points
Link:
NOTE: Please watch the video or ask us through Slack if something is not clear. Please submit complete homework files, otherwise we deduct more marks.