In Raft, an entry stored on a majority of nodes can still be erased

In Raft, a leader commits an entry once a majority of nodes store it. Figure 8 of the paper shows an entry stored on a majority that still gets erased. How can that be legal?

Take five nodes. Slot 2 holds entry A from term 2 on some nodes and entry B from term 3 on n5. The leader from term 2 comes back as leader in term 4 and finishes replicating its old entry, so A now sits on n1, n2 and n3: three of five.

Then that leader crashes, and n5 runs for election. A node votes for a candidate whose log is at least as up to date as its own, and Raft judges that by the term of the last entry first, using log length only to break a tie. n3's last entry is from term 2; n5's is from term 3. So n3 votes for n5, even though n3 holds the majority-replicated entry. n4 votes too, and with its own vote n5 has three of five. As leader, n5 makes every follower's log match its own, and A is overwritten everywhere.

So A was never committed, however many copies existed. Counting replicas of an entry from an older term proves nothing. The fix in §5.4.2 is that a leader only counts replicas for entries from its own current term. Older entries commit indirectly, once a current-term entry after them commits. In practice a new leader appends an empty no-op entry in its own term, just to have something it's allowed to count.

My own first fix was to re-append A stamped with term 4. That works, but the same command now appears in the log twice. Raft's no-op is that idea with the payload removed.

The paper is Ongaro and Ousterhout, "In Search of an Understandable Consensus Algorithm"; Figure 8 and §5.4.2 are the relevant part.