Daily Code 5: Lamport Clocks
Lamport clocks are one of the simplest, but most critical elements of distributed systems theory. This is because they attempt to define time, a concept which is foundational to the way we think about nearly everything, but lack an intuitive definition in the space of a distributed system, where machines will not be synchronized. Not only will machines not be synchronized, sometimes we simply cannot determine whether an event A or event B occurred first. It is based on these realizations that the logical clock (often referred to as the “Lamport Clock”) was theorized.
Lamport clocks are a means by which we can define a “partial ordering” of events in a multi-process environment. They are a logical clock, which refers to a means by which we can establish ordering of events without the need for a physical clock, and simply assigns numbers to each event, defining a causal order for the events in the system. We define a clock C_i for each process, and refer to the set of clocks for all processes as C (C_i(a) = C(a) implies event a is part of process i). These clocks map each event in a process to a timestamp. We can define events more specifically as:
- a local process event
- a message sent to another process
- a message received from another process
upon any pending event, the process increments its timestamp. This ensures that every event in a process has a different timestamp, and allows us to make our first conclusion:
- if events a and b occur in the same process, and a occurs before b, then C_i(a) < C_i(b)
furthermore, processes send their own local timestamp when messaging another process, and the receiving process will increase its timestamp to one greater than that of the sending process, if it is greater than the receiving process’s existing timestamp. Now we can make our second conclusion:
- if event a is a message being sent by process i, and event b is the receiving of the message in process j, then C_i(a) < C_j(b)
from these two conclusions, we can conclude one the following criterion for ordering events. We can conclude that an event A happens before an event B (A < B) if either:
- a and b are instructions in the same process, and a occurs before b
- a is the event of sending a message, and b is the event of receiving that message
this is more formally known as the clock condition. Additionally, we can derive from our definition of happen before relation the reason that this is a partial ordering. There are examples of possible events which cannot be compared, for example, consider the space-time diagram below
In this diagram, each vertical line represents a distinct process, the dots represent events, and the squiggly lines represent the sending and receiving of messages. We cannot compare events p3 and q3, as process P only receives a message from process Q at event p4, thus, neither of the clock condition are satisfied for this set of events, and we refer to them as concurrent. Nevertheless, we should recognize that the ordering of events is transitive, meaning that if a < b, and b < c, then a < c in logical order.
modeling a Lamport clock in Go
Although Lamport clocks are typically associated with message passing and process execution over a distributed system, we can still design and simulate an analogue, which timestamps events of concurrent threads in a program. I chose to do so, and used go routines to simulate local events on processes (represented just by their logical clock) and the sending of messages from one process to another. The structure of this simulation is as follows:
- structs were used to represent a Lamport clock, which includes a current timestamp, a process ID, and a list of existing events tracked by the clock, as well as to represent an event, which consists of an event timestamp, an event type, and an ID (which ties it to a specific clock)
- functions were defined to simulate each type of event, updating time stamps accordingly, and appending events to process event chains
- go routines were used to simulate non-sequential message passing
although this sandboxed version of Lamport time-stamping is not indicative of the powerful value of logical ordering of events, which is mainly useful in an environment where time cannot be synchronized, and the time to pass messages is not trivial in the grand scheme of ordering events (and is ordering messages that were not created synthetically), it still shows the power of Lamport clocks in coordinating amongst a group of processes, while also making it clear that Lamport clocks alone only can give us a partial ordering, where there are a variety of different universal orders which could be derived.
Credit: Time, clocks, and ordering of events in a distributed system, Leslie Lamport
