if for a given proposal at least one accepter has accepted it but not a quorum does, then that value might (but that's not guaranteed either) be replayed (and committed) by another proposer

Why not have the new leader require a quorum of replicas to say "I have this unfinished business" before replaying it?

(I'm pretty sure I had this logic in originally but you talked me out of it in the name of code simplification.)

Okay, so the problem is not the retry per se, but when we have a "split decision" on the nodes that reply. We can reduce the likelihood of that happening by waiting for all known live endpoints if that's required to hear from a majority.

If we still don't hear from a majority, we can return a timeout; it's valid for a transaction to be committed after a timeout.

Patch for the above attached.

Unfortunately, I think this is a little grimmer than that. The problem is that a proposer shouldn't move on unless the propose was successful (in which case it returns to the client) or it is sure that the propose will not be replayed (if it is sure of that, then retrying the proposed value with a newer ballot is safe; the current problem is that we retry with a newer ballot when we're not sure of that). In other words, we should timeout unless we are either successful or all nodes have answered and none have accepted. I'm attaching a v2 doing that (but still tries to timeout as little as possible without compromising correctness).

Unfortunately, this mean we'll timeout as soon as a proposer gets a propose reject but at least one acceptor had accepted it, which is not an extremely rare condition even with moderate contention. That being said, the current behavior is plain wrong, so unless someone has a much better idea that is easy to implement, we should probably go ahead with this for now.

It looks to me like both uses of requiredTargets should actually be totalTargets. v3 attached.

I don't follow. getSuccessful/getAcceptCount is supposed to returned how many successful accepts we got. So that's how much time we decremented remainingRequired, i.e. its initial value (requiredTargets) minus it's current value. Similarly, in isFullyRefused, we want to validate that remainingRequired was never decremented (no-one accepted), so we want to compare it's current value with its initial value, requiredTargets (comparing to totalTargets will in fact always fail).

I guess the code is more straightforward if we keep the number of accepts instead of the number of remaining accept: attaching v4 with that version (which is equivalent to v2, but with the updated comment of v3).

+1

Committed, thanks