Groups keyboard shortcuts have been updated
Dismiss
See shortcuts

Confusion about Raft Safety Argument

55 views
Skip to first unread message

Hao Peng

unread,
Nov 23, 2024, 2:03:54 AM11/23/24
to raft-dev
Hi team, I want to ask a question about raft safety argument.

There is a paragraph in 5.4.3 Safety argument chapter of raft paper.

7.Otherwise, leaderU’s last log term must have been larger than the voter’s. Moreover, it was larger than T, since the voter’s last log term was at least T (it contains the committed entry from term T). The earlier leader that created leaderU’s last log entry must have contained the committed entry in its log (by assumption). Then, by the Log Matching Property, leaderU’s log must also contain the committed entry, which is a contradiction.

What makes me confused is that how to know the earlier leader that created leaderU’s last log entry must have contained the committed entry in its log? Is this inferred based on any rules or  mentioned before in Raft? 

Thanks for giving any ideas on how to understand it.

Diego Ongaro

unread,
Nov 28, 2024, 2:19:29 AM11/28/24
to raft...@googlegroups.com
Hi Hao Peng,

I can see how this might seem magical or circular, but I think it's not.

In the setup for the safety argument (the first paragraph of 5.4.3, above #1), we defined U as the smallest term greater than T whose leader (leaderU) does not store the committed log entry. So we can say that the leaders of T+1, T+2, ..., U-1 (if those terms exist), did store the committed log entry by assumption or, more clearly, by the definition of U.

By paragraph 7, we know "the voter" stored the committed entry from term T when it voted for leaderU, and we're in the case that leaderU's last log term is greater than the voter's. Well, one of those earlier leaders (T+1, T+2, ..., U-1) had to have created leaderU's last log entry, but then since they had the committed entry from term T, they would have had to replicate that entry in the log preceding that last log entry. So then leaderU would also contain the committed log entry. That contradicts the definition of U, which said that leaderU does not have that entry, and that contradiction is what we were trying to show.

Hope this helps,
Diego

--
You received this message because you are subscribed to the Google Groups "raft-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to raft-dev+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/raft-dev/5df2d504-9e1a-41f6-9702-22b3c47783ddn%40googlegroups.com.

peng ghost

unread,
Dec 4, 2024, 8:37:28 PM12/4/24
to raft...@googlegroups.com
 Hi Diego. Thanks for replying.

So we can say that the leaders of T+1, T+2, ..., U-1 (if those terms exist), did store the committed log entry by assumption or, more clearly, by the definition of U.
 
This is the key for explaining my issue, I think safety argument #7 now makes sense for me. 

Best regards,
Hao

Diego Ongaro <onga...@gmail.com> 于2024年11月28日周四 15:19写道:
Reply all
Reply to author
Forward
0 new messages