Question: Assuming all nodes have reached n-f RBCs at this moment, for a node i that has not completed its RBC, all nodes initiate ABA(i,0). Then, some nodes enter mainvote(i,0). Suddenly, all nodes complete RBC_i and initiate repropose_ABA(i,1). Can termination be achieved?

[greenSnot]

Another case: Some nodes decided on 0 after calling ABA(i, 0). Then other nodes repropose ABA(i, 1). Can termination be achieved?

Thanks.

[fififish]

yes termination in such a case is guaranteed by RABA (biased termination property). In this case, it is hard to say whether 0 or 1 will be raba-decided though.

[greenSnot]

Assuming we have 4 nodes (A, B, C, D) running on Quadratic-RABA. According to the Quadratic-RABA protocol:

time	A	B	C(byz)	D
0	propose 0	propose 0	propose 0	propose 1
...	...	...	...	...
100	final vote 0	final vote 0	broadcast final vote 0 for A and final vote 1 for the others	final vote 1
102	decide 0	r+1, prevote 1(coin in the first round is 1)	r+1, prevote 1	r+1, prevote 1

It seems to decide1 in the next round for the others.

[fififish]

Correct nodes will not send inconsistent final votes (but it's possible that one sends final vote v and others send final vote *). This is mainly because we ask each node to consider a main-vote for v valid only after it sees f+1 vote v (line 19 of Figure 3), and consider a final-vote for v valid only after it sees f+1 main-vote v (line 23). This is also crucial for Quadratic-ABA to avoid the expensive RBC instances in Cubic ABA (and Bracha's ABA). See lemma 13 and 14 for the proofs.

[greenSnot]

08 func broadcast-vote(v)
09    if pre-vote0(v) has not been sent, broadcast pre-vote0(v)
10    if v = 1
11       bset0 ← bset0 ∪ {1}
12       if vote0() has not been sent, broadcast vote0(1)
13       if main-vote0() has not been sent, broadcast main-vote0(1)
14       if final-vote0() has not been sent, broadcast final-vote0(1)

Would it send an inconsistent final vote via fast path？

[fififish]

ah, I see your point. There should indeed be another change to the protocol for round 0. Every replica decides v only if v=coin (for round 0 only). This is reflected in Lemma 38 but not in the pseudocode. Will change the eprint version accordingly. Thanks!

[greenSnot]

May it have a similar problem with the Quadratic-ABA protocol?

time	A	B	C(byz)	D
0	propose 0	propose 0	propose 1	propose 1
1	prevote 0	prevote 0	prevote 1	prevote 1
2	prevote 1	prevote 1	prevote 0	prevote 0
3	vote 1	vote 1	vote 1 for A,B; vote 0 for D	vote 0
4	mainvote 1	mainvote 1	mainvote 1 for A,B; mainvote 0 for D	mainvote *
5	finalvote 1	finalvote 1	finalvote 1 for A; finalvote vote 0 for B, D	finalvote *(if only recv mainvote from B,C)
6	decide 1	r+1,prevote 0(local coin)	r+1,prevote 0	r+1,prevote 0(local coin)

If B and D both get local coin 0, next round seems to decide 0.

[fififish]

For Cubic-RABA it's not an issue. In the final vote round, all replicas use RBC to disseminate their votes, so the Byz node cannot equivocate.

[greenSnot]

For Cubic-RABA it's not an issue. In the final vote round, all replicas use RBC to disseminate their votes, so the Byz node cannot equivocate.

I see. So I edit that comment to Quadratic-ABA.

[fififish]

This will not happen. Double check lemma 13-15.

[greenSnot]

This will not happen. Double check lemma 13-15.

Sorry I missed the condition:

"upon receiving n - f finalvote_r() such that for each finalvote_r(v), at least f +1 main-voter(v) have been received..."

Currently, I am working on implementing Waterbear with TLA+. It helps me find the fast-path issue above. It may be helpful for your further research.

[fififish]

Ah, that sounds interesting! I'd be happy to learn more about it. Can you shoot me an email when the draft is ready?

[greenSnot]

Ah, that sounds interesting! I'd be happy to learn more about it. Can you shoot me an email when the draft is ready?

Sure.

[greenSnot]

Ah, that sounds interesting! I'd be happy to learn more about it. Can you shoot me an email when the draft is ready?

https://github.com/fififish/waterbear/pull/6

The TLA+ specifications of Quadratic-ABA and Quadratic-RABA will be done soon.