Published date: November 4th, 2022
Contributed by Arpit Gaur, Software Engineer
The term distributed systems refers to a number of independent computers linked by a network. In it, there are multiple computers that work together in order to achieve one very important common goal which is to keep track of the order of events. Let’s say for example we have two users, User A and B. User A says: ‘‘The earth is made of cheese’’, and User B responds, ‘‘ No, it is not’’. One would normally expect this exact order where the first message comes before the second, right? However, let’s ask ourselves, what if something goes wrong within the system and the timestamps the second message as if it is the first one? That is known as casualty, which refers to a situation where the natural order of events gets mixed up.
This is where logical time has a useful role. Logical clocks, unlike physical ones that measure real world time, are actually designed to remain fully aware and informed about the sequence of events, meaning that it makes sure that if any inconvenience occurs, things are always happening in the right order.
Are Physical Clocks Sufficient?
In distributed systems, sometimes it can happen that physical clocks are unreliable in maintaining the order of events, especially in systems where different parts are spread out over a network.
These kinds of unpredictable instances just happen sometimes, although all clocks are synchronized, delays in communication or slight differences in how clocks are set can occur, which causes problems. As an example, one could send a reply that could end up with an earlier timestamp than the message it is responding to. That is where logical clocks step in to ensure that everything is accurate.
Using Logical Clocks
Logical clocks have nothing to do with the time of the day, they only care about the sequence of events. Whenever an event occurs, the logical clock ticks forward, as if counting steps in a sequence. The main goal is to make sure that if Event A happens before Event B, then Event A gets a lower number (or timestamp) than Event B.
Two types of Logical Clocks: Lamport Clocks and Vector Clocks
There exists two main types of logical clocks used in distributed systems: Lamport and vector clocks. Although the goal of both is to keep events in the right order, the actual process is done slightly differently between the two.
Lamport clocks and its limits
To describe properly how Lamport clocks work requires starting with the basics: they are named after Leslie Lamport, who had the idea in 1978. The idea is rather simple: each computer (or node) in a distributed system keeps a counter that starts at zero. Each time there is an action, the node automatically increases its counter by one. When a node sends a message, it attaches its current counter value to the message as a timestamp. Although these Lamport clocks typically work well enough, they still have some deficiencies.
Vector Clocks: Taking It a Step Further
Vector clocks are somewhat similar to the idea of Lamport clocks, but with more detail. Instead of a single counter, each node keeps a list of counters, a vector, one for each node in the system. Whenever a node processes a new event, it automatically updates in the vector, and then messages carry this whole vector as their timestamp.
Vector Clocks: going a step further
Vector clocks are a little similar to the idea of Lamport clocks, but with more detail. There is actually no single counter per node. Each node in the system keeps a list of counters, a so-called vector of counters, one per node in the system. Then, when a node processes a new event, it will automatically increment its own counter and then messages will carry the whole vector as its timestamp.
There are many advantages when it comes to using such a vector clock. First, it can distinguish several events for being either causally related or happening at the very same time. There are two cases: if one vector is completely less than or equal to another, then the events are causally related. That is to say, one happened before the other. On the other hand, if the vectors under question do not compare, then the events happened at the very same time.
How Vector Clocks Work
Let’s say we have three nodes: A, B, and C. Node A performs two events, updating its vector from [0,0,0] to [2,0,0]. When Node B receives a message from A, it updates its vector based on the information from A. If Node B then performs an event, its vector night might change to [2,1,0]. This way, the system keeps track of all events in a way that reflects their order and relationship.So we can say that in distributed systems, it is not just about when things happen, but in what order they happen.
In conclusion, Logical clocks, whether Lamport or vector clocks, are both essential tools that help maintain this order. Both have significant roles, if Lamport clocks are perfect at preserving the basic order of events, vector clocks are great in offering a more detailed view that lets us distinguish between events that are causally related and not.Therefore, it is very important to understand the probable working of these tools prior to putting them in use so that trusted distributed systems can be made. If any time these systems become more difficult, that is when logical clocks come in to keep everything running smoothly.
