-
@ Ceker liu
2024-01-16 10:34:41How do we determine if an event happens before another event? In our everyday life, we use time to order different events. For example, if event A happened at 8AM and event B happened at 8:30AM, then we say event A happened before event B.
Using physical time to order events works well when the clocks to provide the timestamps are synchronized, i.e., they always show the exact same time. In reality, physical clocks are not perfectly synchronized for two reasons. Firstly, clocks progress at slightly different rate due to physical properties of the oscillators. This phenomenon is commonly referred to as “clock drift”. Clock drifts can range from several minutes a year (for cheap crystal oscillators) to several hundred nanoseconds a year (for expensive atomic clocks). Nevertheless, some amount of clock drifts always happen between two clocks. Many techniques have been proposed to synchronize physical clocks. The most commonly used time synchronization protocol is the Precision Time Protocol (PTP). Unfortunately, these protocols can only reduce clock drift, but not eliminate them. The second reason is more fundamental. As explained by Einstein’s theory of relativity, time on two clocks with non-zero relative velocity or relative gravitational potential will elapse at different rate, a phenomenon termed “time dilation”. Compared to clock drift, the scale of time dilation is negligible for clocks on earth, and therefore are usually ignored.
Logical Time
If physical clocks cannot be used to accurately determine the order of events, what are some alternative approaches? Here comes logical time, the main topic of this article series. Logical time does not progress at some constant rate like physical time. Instead, it “ticks” when certain event happens. For instance, suppose a node maintains a logical clock that starts from zero. When event A happens, the node increments the clock and assigns logical time 1 to event A; and when event B happens later, the clock is incremented again to assign time 2 to event B. Now, we can use logical time to order the two events, i.e., event A happened before event B since logical time 1 is smaller than logical time 2.
But how to determine the order of events occurred on different nodes, each maintaining their own logical clock? For example, event A happened on node P and is assigned logical time 1, while event C happened on node Q and is also assigned logical time 1. What is the order between A and C?
Leslie Lamport in his famous article “Time, Clocks, and the Ordering of Events in a Distributed System” defines a new happens-before relationship that discusses this issue. In this happens-before definition, the ordering of events is a partial order, not a total order, meaning not every two events have an order between them. Only events that have potential causal dependency are ordered by the happens-before relation; events without any possible causality are not ordered, i.e., they are “concurrent”. So what does this causal dependency mean? Event B is causally dependent on event A if the occurrence of B depends on the occurrence of A (and applying the definition, A happens before B). To give a real-life example, if event A is cooking some meal and event B is eating the meal, then event B is causally dependent on event A. In the context of distributed systems, if event A and B happen on the same node and A is executed before B (considering a sequential execution mode), then B is causally dependent on A; if event A is sending a message and event B is receiving the message on another node, then B is causally dependent on A. Since this happens-before relationship is a partial order, it also has a transitive property: if A happens before B and B happens before C, then A happens before C.
Lamport Clock
Now we have a new ordering definition, one that hinges on causality, the next question is how to design a logical clock system that is in accordance with the happens-before relation. By accordance, I mean if event A happens before event B, then the logical clock of A is smaller than that of B. Here comes the Lamport clock (introduced in the same article). Each node maintains a local clock (the clock can start from any value, but by convention, it starts from 0). Each time a local event happens, the node increments its local clock and assigns the resulting clock value as a timestamp to the event. When a node P sends a message to node Q, it attaches the local clock value to the message. When Q receives the message, it updates its local clock to the bigger value between the received clock value and Q’s local clock (plus one, as receiving a message is also a local event). Readers can verify that the Lamport clock protocol guarantees accordance with the happens-before relation.
Vector Clock
There is one issue with the Lamport clock — it can not be used to infer the happens-before relation. By inference, I mean we can correctly infer the happens-before relationship between any two events by only comparing their logical clock timestamp. Lamport clock does not satisfy this property. For instance, say we have two nodes, P and Q. Event A happened on P and is assigned timestamp 1; event B and C happened on Q and are assigned timestamp 1 and 2 respectively. No messages are sent nor received in this example. Now, we take event A and event C. Event A’s timestamp (1) is smaller than that of event C (3). If we use Lamport clock, we will deduce that event A happens before event C. However, the two events are concurrent by the definition of happens-before relation, since there is no causal dependency between the two events.
To handle this issue, another logical clock construct, the vector clock, has been proposed. Using vector clock, instead of a single clock, each node maintains a vector of clock values (thus the name, vector clock), with vector size equal to the number of nodes in the system. Each node is also assigned a unique index of the vector. For instance, if the system has only two nodes P and Q, then the vector clock has size 2 (represented by [a, b], where a and b are integer values), P could be the first number in the vector then Q is the second number in the vector (the other way is also fine). Each node initiates the clock to [0, 0]. When local event happens, the node increments the number in the local vector clock corresponding to its index, and assigns the resulting vector clock value to the event. Messages similarly are attached with the current local vector clock. When receiving a message, the node performs an element-wise maximum between the received vector and its local vector (for the number corresponding to its own index, the node adds one to the number for the receiving event).
It is fairly easy to see that the vector clock protocol preserves the happens-before accordance rule. Now let’s see if we can use vector clock to correctly infer happens-before relation. We use the same Lamport clock example as above. When event A happens on node P, it updates its clock to [1, 0]; when event B and C happens on node Q, it assigns clock values [0, 1] and [0, 2] to each event respectively. Now let’s compare the clock value of A ([1, 0]) and that of C ([0, 2]). Note that neither clock is equal or greater element-wise to the other clock (the first number in A is greater than that of B, and the second number of B is greater than that of A). In this case, the two clocks are not comparable, and therefore the two events are concurrent. Voila! Readers can construct other examples to check if vector clocks can correctly infer happens-before/concurrency between any two events.
Logical Clock in Open P2P Network
Logical clocks are extremely useful in building distributed systems and applications. They have been used to construct causally consistent and eventually consistent data stores, detecting data races in concurrent applications, building consistent distributed snapshots, etc.
Unfortunately, existing logical clocks can not be used in an open peer-to-peer (P2P) network, such as a permissionless blockchain, a L2 rollup system, a decentralized storage or file sharing system, or a decentralized social application such as Nostr. There are two reasons. Firstly, in an open P2P system, nodes can join and leave at any time, and the number of active nodes in the system can be arbitrarily large. This makes vector-clock-based constructs ineffective, as they are designed for a static network with fixed membership, and the clock size increases proportionally to the number of nodes in the network. The second issue is the possibility of malicious behaviors in an open P2P network. Correctness of the above logical clock protocols (accordance and inference) relies on all the participants following the protocol as is. Any protocol deviation will result in guarantee violations. For instance, say we use the same two node (P and Q) vector clock example. This time, Q is an adversary, and when event B happens, it updates its local clock as [2, 0] (instead of [0, 1]). Now, when we compare the vector clock of A ([1, 0]) and B ([2, 0]), we will incorrectly infer that B happens after A, even though in reality A and B are concurrent events.
How do we design a logical clock system that can work properly in an open P2P network with potential adversaries? Stay tuned for our second article in the Secure Logical Time in P2P Network series.