Lesson plan
Vector clock
A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's logical clock. A vector clock of a system of n processes is a vector (equivalently, a 1-dimensional array) of n logical clocks, one clock per process. Besides maintaining its own clock, every process also keeps track of the largest value of each of the other processes' clocks that it has so far been informed of. The clock updates proceed as follows, where VC_i denotes the value of the vector clock maintained by process i : * Initially all clocks are zero. * Each time a process experiences an internal event, it increments its own logical clock in the vector by one. For instance, upon an event at process i , it updates VC_{i}[i] \leftarrow VC_{i}[i] + 1 . * Each time a process sends a message, it increments its own logical clock in the vector by one (as in the bullet above, but not twice for the same event) then it pairs the message with a copy of its own vector and finally sends the pair.…
Article summary
A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's logical clock. A vector clock of a system of n processes is a vector (equivalently, a 1-dimensional array) of n logical clocks, one clock per process. Besides maintaining its own clock, every process also keeps track of the largest value of each of the other processes' clocks that it has so far been informed of. The clock updates proceed as follows, where VC_i denotes the value of the vector clock maintained by process i : * Initially all clocks are zero. * Each time a process experiences an internal event, it increments its own logical clock in the vector by one. For instance, upon an event at process i , it updates VC_{i}[i] \leftarrow VC_{i}[i] + 1 . * Each time a process sends a message, it increments its own logical clock in the vector by one (as in the bullet above, but not twice for the same event) then it pairs the message with a copy of its own vector and finally sends the pair.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.