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

Piers Powlesland <pierspowlesland@gmail.com> Tue, 23 October 2018 11:59 UTC

Return-Path: <pierspowlesland@gmail.com>
X-Original-To: din@ietfa.amsl.com
Delivered-To: din@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 8D129130DFE for <din@ietfa.amsl.com>; Tue, 23 Oct 2018 04:59:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id eByfm5p2svyO for <din@ietfa.amsl.com>; Tue, 23 Oct 2018 04:59:52 -0700 (PDT)
Received: from mail-lf1-x12f.google.com (mail-lf1-x12f.google.com [IPv6:2a00:1450:4864:20::12f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6D51E130DE2 for <din@irtf.org>; Tue, 23 Oct 2018 04:59:52 -0700 (PDT)
Received: by mail-lf1-x12f.google.com with SMTP id c16so891293lfj.8 for <din@irtf.org>; Tue, 23 Oct 2018 04:59:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=pGwG/HL0sYfWC/uk/0S4MeCBPApFwA4ofpQEaZGX64w=; b=TPyXPJI1deW3/8a9/GM2h/UYTb4qhVVTqZeI3jCvT0VjeRa2hucIbFNGZjGZJ0zOmJ V9nxAG16VEjG2ToO+417RICvrqx5QxhMJuCKterVMHk3MOnGEdOQ6phlFhXQmvk8g/03 qQqHynA1xI+dE5lT28FRcSDbFL8LN/LmaqjzHv+EE6llyU9DXJ2KL7QZ7kp1RpoCcqdt 2PwFa1nOcqRyEFQqUJHLzD4zvsT+Kr8a6umL4hdATqm9cBFg+3i/zx/beLBnpVNS/NGv Gg3lZ3T5bnobIwKe71hcOy/aD5Gr0nbXyWBNQlTdiqv2AAZGpsQhwa1ibHzdBAi5rKgu 8Ncg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=pGwG/HL0sYfWC/uk/0S4MeCBPApFwA4ofpQEaZGX64w=; b=dUN+ZOmjI9amLPwwhq1Mh2I3tmWyJN9SIIDlkC+lZUCt0YsS5Ljefv/+ehDnJ4Dg/S Kq9yEl1Mdi/ovwa/bPLH7OtVCQZ/fuLCVp9NOBiFjNMGLF1uo3uuZZBpyF8OgKo/+Z8W jrj+HriXe/XuFB4hpBQRtQP3QsmNSSaUa/VXevpdvtX8jIySZUMeWiD7ljRgFcDbbHGx g0/Ao/7ukgxIC9A3xWSVnAkVqLvqqx1w5fKpNBo+KmJdXYreOA2qTAitW0MkJXVzqMPN 5e2wb30Be+FC45SC7U/OIR/kA9qRBhq1cRuXLckiPCdzoSE6lxzfP1qhTgrqBJJrcEij tY3Q==
X-Gm-Message-State: ABuFfogq9PPeB9dctmtLxxhBLHwh+CFbXcO5Nhs6lxwICGTqNNTjZhOR i1Oi0Fwk/RY17urYT5A9LyW71D07A9V4mMd2S/Aa/M0A
X-Google-Smtp-Source: ACcGV60jyEDaEvK+SvvKF9mFAgC94aPX5RjIu2NmeN8ld/n3s/vJSCO8nuppkLhSGCnETK4uZBHeoawajBC/ZTt0qrc=
X-Received: by 2002:a19:639b:: with SMTP id v27mr10857497lfi.95.1540295990036; Tue, 23 Oct 2018 04:59:50 -0700 (PDT)
MIME-Version: 1.0
From: Piers Powlesland <pierspowlesland@gmail.com>
Date: Tue, 23 Oct 2018 12:59:39 +0100
Message-ID: <CAFXacXkndhMcrLJrgkytr9EJGSkCJaLANDCyFni53CW=u5K8Dw@mail.gmail.com>
To: din@irtf.org
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/din/VbRunBNsw0TgB8dUm97fBQAtK10>
Subject: [Din] draft-mazieres-dinrg-scp-04 (page 16) transitioning from prepare to commit.
X-BeenThere: din@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Discussion of distributed Internet Infrastructure approaches, aspects such as Service Federation, and underlying technologies" <din.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/din>, <mailto:din-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/din/>
List-Post: <mailto:din@irtf.org>
List-Help: <mailto:din-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/din>, <mailto:din-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 23 Oct 2018 11:59:55 -0000

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

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!