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

[Piers Powlesland <[e-mail]>]

So to clarify

> I think this is correct, but not necessarily more efficient.  If h is
> the highest confirmed prepared ballot, then prepared >= h.  So if you
> suddenly raise prepared to be greater than and incompatible h, that
> means you are now trying to confirm something prepared that has a
> different value from h, meaning h.value is no longer your best guess as
> to the value to externalize, so I don't see much point in continuing to
> vote to commit ballots with value h.value.

In the case where either prepared or preparedPrime are greater than or
incompatible to h then c is set to NULL, so the node stops voting for
anything.

The case where I envisage this being a win is:

After a node confirms c and has subsequently gone on to confirm
several higher and compatible ballots, such that the node is now
voting to commit several ballots. The node then accepts a
preparedPrime that is greater than and incompatible to c but less than
h. Rather than dropping everything and starting to vote to commit just
the highest ballot that it was previously voting to commit, it just
stops voting to commit any ballots that are now considered aborted due
to the new preparedPrime. In this case everyone is still working on
confirming committed c.value, we have just updated our "lower bound"
below which we consider everything aborted.

Using this approach provides more opportunities for the network to
come to agreement and so in certain situations, I think, could reduce
the time taken to agree on a value.

On Thu, Nov 8, 2018 at 2:03 PM David Mazieres
<[e-mail]> wrote:
>
> Piers Powlesland <[e-mail]> writes:
>
> > Yes I did mix up the hCounters in my example, your interpretation was
> > correct. Your last explanation does make sense but seems to be at odds with
> > your previous statement which confused me.
> >
> >>It's only safe to vote to commit a ballot b if
> >>ballot == b at the time b was confirmed prepared
> >
> > I think that statement is too strict, since it precludes voting to commit
> > ballots (3,x)...(7,x) from my previous example. In fact I think this
> > statement would be correct if it is describing the point at which a node
> > starts voting to commit a ballot. (I.E when c changes from NULL to some
> > integer)
> >
> > So instead we can say it is only safe to vote to commit a ballot if the
> > ballot has been confirmed prepared and we have not voted or accepted abort
> > for it.
>
> Yes, what you say is correct, but not possible to verify with the fixed
> amount of state that SCP keeps around.  So the rule I stated is a
> conservative approximation.  Maybe I shouldn't have said only.  I should
> have said it is safe to vote in this case, and you can check this case.
>
> > So put simply, my original suggestion, was to modify the algorithm to vote
> > to commit all confirmed prepared ballots that have not been voted or
> > accepted aborted. I see that my proposed update step doesn't quite achieve
> > that, since as you pointed out it might set c such that we are voting to
> > commit a ballot that we previously voted to abort.
> >
> > I've modified the update step again, I think this would work correctly.
> >
> > Replacing the first update step for c with the following three steps.
> >
> >> * If "c != NULL" and "(preparedPrime > c && preparedPrime.value !=
> > c.value)"
> >>   raise c.counter to the lowest value such that c > preparedPrime.
> >>
> >> * If "c != NULL" and "(prepared > c && prepared.value != c.value)"
> >>   raise c.counter to the lowest value such that c > prepared.
> >>
> >> * If c.counter > hCounter then reset "c = NULL"
>
> I think this is correct, but not necessarily more efficient.  If h is
> the highest confirmed prepared ballot, then prepared >= h.  So if you
> suddenly raise prepared to be greater than and incompatible h, that
> means you are now trying to confirm something prepared that has a
> different value from h, meaning h.value is no longer your best guess as
> to the value to externalize, so I don't see much point in continuing to
> vote to commit ballots with value h.value.
>
> With preparedPrime, there is a similar argument, that after confirming c
> prepared, a quorum confirmed an incompatible preparedPrime prepared.  So
> maybe by coincidence after that everyone went back to c.value, but
> c.value is no more likely to be the ultimate consensus value than
> anything else.
>
> Basically the only reason it might be a win to avoid setting c to NULL
> is if you still think everyone is working on confirming c.value, which
> won't be the case if something incompatible but higher was prepared.
>
> David