Who can become the leader
A Raft cluster of n servers has survived a failure: some servers are down, and the network may have split into groups that cannot hear each other. An election begins. All that is known about each server’s log is its last entry: its term and number.
A candidate votes for itself. Another server gives it a vote if it is up itself, hears the candidate (they are in the same group), and the candidate’s log is not behind its own: the term of the candidate’s last entry is greater, or the term is the same and the number no less. A candidate wins if it has more than half the votes of all n servers, including those that are down. Assume that nobody has voted for anyone yet in the new term. For each cluster print all the servers that can become leader.
Input
The first line holds the number of clusters q (1 ≤ q ≤ 105). For each, the number of servers n (1 ≤ n ≤ 9) and n lines “t i u g”: the term and number of the last entry (1 ≤ t, i ≤ 109), 1 if the server is up and 0 if it is down, and the number of its network group (from 1 to n). There are at most 3·105 servers across all clusters.
Output
For each cluster, the numbers of the servers (from one) that can win the election, in increasing order separated by spaces, or 0 if there are none.
The first example is Figure 8 of the Raft paper. In the first cluster the leader S1 is down, and its entry of term 2 is already on S2 and S3; S5, whose last entry is of term 3, can also win, and then it will overwrite the entry of term 2. In the second cluster S1 managed to get its term-4 entry to S2 and S3, and S5 can no longer win.
Examples
Example 1
2 5 2 2 0 1 2 2 1 1 2 2 1 1 1 1 1 1 3 2 1 1 5 4 3 0 1 4 3 1 1 4 3 1 1 1 1 1 1 3 2 1 1
2 3 5 2 3
Example 2
2 5 5 40 1 1 5 40 1 1 5 38 1 2 4 30 1 2 5 39 1 2 3 3 7 1 1 3 7 1 1 3 7 1 1
5 1 2 3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 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
More than half of n votes are needed, not of the group: a group of two servers in a cluster of five will never elect a leader. And who within the group gives a vote depends only on comparing last entries.
2The idea
For each working candidate c, count how many working servers of its group (including itself) have a last entry no newer than its own: a pair (term, number) no greater than its pair in lexicographic order. If there are more than n/2 of them, c can win. This is exactly the election restriction from the article: it is what guarantees that a new leader knows all committed entries.
3Walkthrough
A cluster has at most nine servers, and comparing each with each is 81 comparisons. Compare by term and then number, in exactly that order: a log whose last entry has a later term is newer, even if it is shorter. In the second example, in a group of three servers only S5 with the last entry (5, 39) wins: S3 has (5, 38) and gets two votes, S4 has term 4 and gets only its own.
Why the restriction works. A committed entry is held by a majority. Any majority intersects the majority that will vote for the new leader: at least one server is in both. That server votes only for a log no worse than its own, and its log has the committed entry; so the winner has it too.
3+Solution
4Complexity
O(n²) per cluster, O(Σn²) in all.
5Common mistakes
- No log comparison. If anyone can get a vote, a server that missed committed entries becomes leader and erases them from the others.
- A majority of the group. More than half of all n servers is needed: those that are down or cut off count in the denominator too.
- Comparing by length. First the term of the last entry, then the number: a short log with a later term is newer than a long one.