Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) Potential improvement to balloting protocol, setting cCounter

[David Mazieres <[e-mail]>]

Piers Powlesland <[e-mail]> writes:

> I think it may be possible to improve the chances of nodes being able
> to accept ballots as committed during the prepare phase.
>
> The following instructions are given to update cCounter.
>
>> * If either "(prepared > c && prepared.value != c.value)" or
>>   "(preparedPrime > c && preparedPrime.value != c.value)", then
>>   reset "c = NULL".
>>
>> * If "c == NULL" and "hCounter == ballot.counter" (meaning
>>    "ballot" is confirmed prepared), then set "c" to "ballot".
>
>
> If we consider an example where a node has the following state.
>
> ballot = (8,x)
> prepared = (8,x)
> preparedPrime = (3,y)
> cCounter = 4
> hCounter = 8
>
> If the node accepts prepared (4,z) then using the update steps above c
> will be set to NULL and then c will be set to ballot.

That's correct.  This is because the messages only encode cCounter
instead of c.  Since c.value is implicit, you don't want to vote to
commit the wrong ballot.  (In fact, I will change preparedPrime to be
preparedPrimeCounter in the next version, too.)

> This means that the node will transition from voting to commit ballots
> with value == x and counters 4...8 to just the single ballot (8,x).

You mean transition to voting to commit nothing?  (Though still
vote-or-confirm (n,x) for 4 <= n <= 8.)

> Out of the ballots that the node was previously voting to commit only
> (4,x) has been accepted aborted due to setting preparedPrime = (4,z),
> so it seems that it would still be legal to vote to commit ballots
> with value == x and counters 5...8.

Not necessarily.  Whether or not it's safe to commit (5,x) depends on
history.  It's only safe to vote to commit a ballot b if ballot == b at
the time b was confirmed prepared.  If, for instance, hCounter jumps
from 0 to 8 in the history, then the node has no memory of whether it
is, say voted to prepare (4,z), which would make it illegal to vote to
commit (4,x).

> So I am proposing that the first part of the above update step is
> changed to the following, to allow for that.
>
>> * If c != NULL set c.counter to the counter of the lowest ballot with value ==
>>   h.value and not accepted aborted according to p and p'. If c.counter >
>>   hCounter, then set c=NULL

To be correct, you might also need to raise h such that you've never
voted to abort anything between h and the new c, but I don't think nodes
have enough state to do that.  So the current algorithm is safe but
"wasteful" of potentially useful ballots.

David