Receive() can receive dropped messages

ongardie / raft.tla

TLA+ specification for the Raft consensus algorithm

456 stars 74 forks source link

Receive() can receive dropped messages #2

Open dricketts opened 8 years ago

dricketts commented 8 years ago

I don't think that DropMessage is defined correctly. In particular, it does not actually remove messages from the variables messages. Instead, it decrements the counter for the given message, if it already exists in messages. This has two issues:

messages is not a function from Message to Nat, as the comment above message suggests. Instead, it is a function from Message to Int.
Receive only requires that the received message be in the domain of messages, which means that it can continue to receive messages that have been dropped (even if their count drops below zero).

ongardie commented 8 years ago

Hi @dricketts. I think you're right, and I vaguely remember this being a late change to the spec. Care to submit a PR?

dricketts commented 8 years ago

@ongardie I'd be happy to submit a PR. The easiest option that I see is to use the Bags module, but the comment above messages says that Bags is not supported by TLAPS. In what sense is it not supported? I've tried some proofs using Bags, and you can definitely use the definitions and associated theorems from this module: https://tlaps.codeplex.com/SourceControl/latest#library/Bags.tla.

I ask about TLAPS because I'm trying to do the Raft safety proof using TLAPS. I know that it's already been done in Coq, but I'm curious to compare and contrast the proof in the two different formalisms.

ongardie commented 8 years ago

@dricketts, sorry for the delay. I don't remember why I wrote that comment before, but maybe I was wrong or maybe it's changed since. If it's working for you under TLAPS, that's good enough for me. Feel free to switch it to using Bags. Good luck.

wego1236 commented 1 month ago

Hi guys, I also found this problem and wanted to ask if this is now resolved, as I see that the existing version still doesn't seem to be up to date

wego1236 commented 1 month ago

I also want to ask why we don't use set here, it can also indicate the addition and removal of msg which can be indexed by a sequence number?

ongardie commented 1 month ago

Hi @wego1236, I'm still open to receiving a PR for this. I haven't touched TLA+ in many years, so I'm not currently qualified to do it.

liang636600 commented 3 days ago

Hi @ongardie, I'd be happy to submit a PR to fix this issue. I modified the WithoutMessage(m, msgs) action to remove the message m from the messages variable when the counter of the message m is less than or equal to 1.

ongardie commented 2 days ago

Thank you @liang636600. This has been outstanding for a long time. I hope we can find another reviewer to look over the PR.