I understand that vector clocks are preferred over lamport clocks because sometimes lamport clocks cannot account for the casuality and we use extra space to store the timestamps in the vector clocks. What i dont understand is about the resetting of the vector clocks. Why do the vector clocks overflow and how the resetting is done in such scenario?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Vector clocks overflow for the same reason that regular integers do. Vector clocks generally maintain a fixed number of bits per process to capture the event count for each respective process. There is naturally a maximum value that each of these bit strings can represent. Any one of these values can potentially be increased beyond their capacity, and thus overflow. For example, if we presume that one process has the following vector clock:
$\vec{P3} = (5, 3, 7) = (101_2, 011_2, 111_2)$
And then $P3$ has an internal event, increasing their event count from 7 to 8:
$111_2+1=000_2$
This number is too large to be represented with only 3 bits. And so the clock overflows back to zero. This will prevent us from properly computing causal ordering in this system, and undermines the consistency of the distributed system.
We can of course allocate many bits to each process to reduce this risk. However, since the vector clocks are regularly passed between processes, we would like to minimise this since it reduces the throughput of communication channels (regardless of whether it is a network, file, shared memory etc).
Therefore we require a mechanism to safely reset clocks within the system, such that we can maintain the constraints of the distributed algorithm. From my understanding this can be done in a few ways:
Blocking Globally
If a process detects that its own counter is about to overflow, it sends a message to every other process informing them to reset their event count for that process on their local clocks. This will halt the distributed algorithm until the process that initiated the reset receives confirmation from every other process.
Consensus Protocols
Depending on how the distributed algorithm is structured, we may not require the full event history to ensure causal ordering for events. Some distributed algorithms have rounds of consensus which allow us to repeatedly incrementally work from a point of stability. These are like rounds in a card game, and offer natural opportunities to reset clocks. This is particularly true of Gossip algorithms. This is very similar to the global blocking algorithm above, but does not wait until an overflow to reset clocks.
There might be some other vector clock reset mechanisms that I am not aware of. It is also possible to organically grow the number of bits used per process as required (which might actually be easiest).
You can read more on these topics with the following academic papers:
