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

From: Piers Powlesland <[email-masked]>
Date: Tue, 23 Oct 2018 12:59:39 +0100

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

---

From: Piers Powlesland <[email-masked]>
Date: Thu, 25 Oct 2018 14:43:11 +0100

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.