Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) transitioning from prepare to commit.

[Piers Powlesland <[e-mail]>]

Thinking about this more I realise I made a mistake in my reasoning, please
disregard my previous reasoning. I set out below a new description. It would be
great to know if it is correct. I am still not clear on why a node needs to
confirm prepare(b) and accept commit(b) when nodes can change slice mid
protocol?

At the point that a node accepts commit(b) they have seen a quorum vote
commit(b). Seeing a node vote commit(b) lets us know that it has confirmed
prepare(b).

We can know at this point that the network cannot come to agree on any value
other than b.value and that it also will not get stuck as long as messages are
not delayed indefinitely.

We can see that the network cannot come to agree on any other value since there
are only 2 ways that new values can be introduced to a node. Either a new
composite value is produced via nomination or a node accepts prepared a ballot
via blocking threshold. Since nomination terminates once a node confirms
prepare(b) no new values can be introduced via nomination. Given that we have
seen a quorum of nodes confirm prepare(b) we know that for each node they must
have at least one quorum slice contained entirely within the quorum. This means
that none of the nodes in the quorum can reach blocking threshold for any other
value than the one they prepared. So we can see that the nodes in the quorum
that voted to commit(b) cannot change their value. Given that there will be at
least one of the nodes who have confirmed prepare(b) in all other quorums we
can see that the network cannot agree on any other value.

How do we know that the network will come to agree on the value that has been
accepted committed? Theorem 10 shows that any subset of nodes that also contain
a quorum is v-blocking for at least one node not in the subset. If we expand
the subset to include the v-blocked node the subset will still be v-blocking
for at least one node outside the subset. We can continue this process till the
entire network is contained in the subset, and hence all nodes have accepted
the same value.

On Tue, Oct 23, 2018 at 12:59 PM Piers Powlesland
<[e-mail]> wrote:
>
> At the end of section 3.6 there is the following statement.
>
>    A node leaves the PREPARE phase and proceeds to the COMMIT phase when
>    there is some ballot "b" for which the node confirms "prepare(b)" and
>    accepts "commit(b)".  (If nodes never changed quorum slice mid-
>    protocol, it would suffice to accept "commit(b)".  Also waiting to
>    confirm "prepare(b)" makes it easier to recover from liveness
>    failures by removing Byzantine faulty nodes from quorum slices.)
>
> I'm trying to understand how we know that when a node accepts
> commit(b), the network will come to agreement on b.value. I'm
> considering the case where nodes do not change slice mid-protocol
> where a node accepts commit(b) via quorum threshold.
>
> So far I have come up with this:
>
> We know that the quorum of nodes nodes that have voted to commit(b)
> cannot vote for another ballot, although they potentially could accept
> commit for a different ballot and they could also abort their vote for
> commit(b).
>
> But we know that a vote to commit(b) indicates that these nodes have
> left the nomination phase and therefore can only change the value in
> their ballots through accepting incompatible ballots via blocking
> threshold, since we have seen a quorum of nodes vote commit(b) we know
> that there is at least one of these nodes in all quorums and therefore
> no quorum could accept,  prepared or committed, any ballot with a
> value other than b.
>
> So we can say securely that the nodes we have seen vote commit(b),
> cannot accept a commit with a different value or abort their vote.
>
> Now I'm wondering how do we know at this point that the network will
> not get stuck? For instance how do we know that a quorum that contains
> one of the nodes that has voted to commit(b), may not have nodes that
> vote for a higher incompatible ballot, that they can never accept?
>
> So my thinking thus far is that:
>
> The node that has voted to commit(b) in this quorum must have seen
> every node in the quorum accept prepare(b). If we consider any one of
> those nodes that have accepted prepare(b), in order for it to accept a
> new ballot prepared it will need to hear from the rest of its quorum
> and when it does hear from the rest of its quorum, it will in fact
> confirm prepare(b) at which point the node stops considering new
> values for its ballots. So we can see that nodes will not get stuck
> voting for higher incompatible ballots.
>
> It would be good to know if I'm on the right track or If I have gone
> off the deep end? And also I'm still not clear at all on why nodes
> changing mid slice makes it necessary to confirm prepare(b) and accept
> commit(b) so any explanation of that would be great!
>
> Thanks,
>
> Piers