Getting To Know Logical Clocks By Implementing Them
Physical clocks can't capture causality. This blog post discusses two kinds of logical clocks (Lamport Clocks and Vector Clocks), how they are able to capture causality and achieve consensus on the ordering of events, and how to implement them.
A single node system has no problem deciding what time it is and which order the events inside the system happened. The node has a timer, called clock, and any process that needs to make use of time makes a call to the operating system. If process \(a\) makes use of time before a second process \(b\), the time read by \(a\) will be smaller than the time read by \(b\). In a more formal way,
This is a very natural condition. If something happens before another thing, it is expected that the time at the first thing occurred to be smaller. The operator \( \to \) is called happened-before, and it is defined as: 1. If \(a\) and \(b\) are events in the same process, and \(a\) occurs before \(b\), then \(a \to b\) 2. If event \(a\) is the sending of a message from a process, and event \(b\) is the receiving of the same message by another process, then \(a \to b \) 3. If \(a \to b\) and \(b \to c\), then \(b \to c\)
In a distributed system, however, the above condition is not so easy to maintain. We have multiple nodes. Each with its own clock. A clock is an electronic circuit present in the hardware made of a crystal that oscillates at a constant frequency. We call physical clocks this kind of clock that measures real-time. The problem in a distributed system is that there is no guarantee that the rate at which each one of the clocks oscillates will be the same, a phenomenon known as clock drift. This is the clock synchronization problem. Nodes can't agree on which time it is. Of course, measuring the real-time is important to many applications, so solutions to coordinate the clocks as NTP have been in use. However, even when using something like NTP and node's physical clock times becoming very close within a bounded range, it is still possible that an event happening before another to have a superior timestamp. There are many applications that it is important to have an agreement on the order of events. These applications cannot rely on physical clocks.
