Vector stamps
A system has P processes. Each process performs events one after another, and events are numbered in the order they were written to the log: 1, 2, …, E. In addition, an event can receive a message, and then it knows everything the sending event knew at the time of sending. Event a happened before event b if one can get from a to b by moving to the next event of the same process or along a message. If neither a is before b nor b before a, the events are concurrent.
Answer questions about pairs of events. One of the tests is this site’s git history: a commit is an event of its branch, and a merge receives a “message” from the commit being merged.
Input
The first line holds P and E (1 ≤ P ≤ 50, 1 ≤ E ≤ 105). Then E lines: the process number p (from 1 to P), the number k of messages received, and the numbers of the k sending events, all smaller than the number of the current event. The total of k is at most 2·105. Then the number of questions q (1 ≤ q ≤ 105) and q lines with event numbers a and b.
Output
For each question, a character: < if a happened before b; > if after; = if they are the same event; | if they are concurrent.
In the first example a message goes from event 1 (process 1) to event 3 (process 2) and from event 3 to event 4 (process 3), so 1 is before 4. Event 5, a new event of process 1, is passed on to nobody: it is concurrent with both event 4 and event 2.
Examples
Example 1
3 6 1 0 2 0 2 1 1 3 1 3 1 0 3 0 6 1 4 4 1 5 4 2 5 3 3 6 1
< > | | = >
Example 2
2 4 1 0 2 0 1 0 2 0 4 1 3 1 2 3 4 4 2
< | | >
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A walk over the graph of events for each question is up to 105 steps per question. What if each event records in advance how many events of each process it knows?
2The idea
These are vector clocks. An event’s vector has a counter per process: the componentwise maximum of the vector of the previous event of its own process and the vectors of all messages received, then +1 in its own process. Then position q of the vector holds the number of events of process q that happened before (or coincide with the current one, if it is its process).
There is no need to compare whole vectors. Let a be the i-th event of process p. Event b knows a exactly when its vector has at least i in position p: the events of process p form a chain, and knowing the i-th means knowing the first i. One look at one cell.
3Walkthrough
Go through the log. An event’s vector is a copy of the vector of the previous event of its own process (or zeros), the senders’ vectors are added to it by componentwise maximum, and its own position grows by one; its new value is the event’s number within the process. A question: if a = b, “=”; if the vector of b in the position of a’s process is at least a’s number, “<”; symmetrically, “>”; otherwise “|”.
Memory is E · (P + 1) numbers, up to five million: in Go one flat array, in Python a list of lists, and it fits. In this site’s git history, out of twenty thousand random pairs 854 are concurrent, 4.3%.
3+Solution
4Complexity
O(E · P + (sum of k) · P) for the vectors and O(1) per question.
5Common mistakes
- Lamport clocks. If a is before b, a has the smaller Lamport number, but not the other way round: a concurrent event can also have a smaller number. The answer “|” cannot be obtained from them; the first example catches this.
- Forgetting the previous event of one’s own process. An event’s vector is not only the maximum of the senders: everything the process knew before, it still knows.
- Comparing vectors componentwise. Correct, but 50 comparisons per question instead of one; in Python on a hundred thousand questions that is noticeable.
Algorithms behind it
O(1) per event for Lamport, O(n) for vectors
2 problems
GRA
Algorithm
Topological sort
Lines up the vertices of a graph without cycles so that all edges point forward, in O(V + E).
O(V + E)
2 problems