Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) transitioning from prepare to commit.
Piers Powlesland <firstname.lastname@example.org> Thu, 25 October 2018 13:43 UTC
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5075F120072 for <email@example.com>; Thu, 25 Oct 2018 06:43:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
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 ([220.127.116.11]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FB68W74j4S8P for <firstname.lastname@example.org>; Thu, 25 Oct 2018 06:43:26 -0700 (PDT)
Received: from mail-lf1-x134.google.com (mail-lf1-x134.google.com [IPv6:2a00:1450:4864:20::134]) (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 8430F130E5A for <email@example.com>; Thu, 25 Oct 2018 06:43:24 -0700 (PDT)
Received: by mail-lf1-x134.google.com with SMTP id n3-v6so6829861lfe.7 for <firstname.lastname@example.org>; Thu, 25 Oct 2018 06:43:24 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=FkA3GpWL1Zxv4JJavWcUjQXw2FTocGT7kLd4J6NV31c=; b=W5mD0bNowwQQerf3K3lRzNn2qRXtmWONN3PME+Jgpfq1Dq+/3VyNWGxlx8w7i+pAFz H+z+3hYkHPonm7UJlRW/MpS8wViYV6EVUGYn1U9jO+NU8QaqgZUYpurOFSF/igRg9IUF n+xmjG/J+xknvRoXG30S1ecTwCzLKjUjoiEL/VQvrvomvfWA8azzeEIdW5mawSrZfoiK 6ldsetcG22B8kPffzfbtINm5FUc7XAreO8jWL/VvJbfQh/CrHab04ImGo7Pl2HVePm12 QNSxLTeG/EvSRj1FsF2lRvfSdljOleIw4ACBDRc3dw1prgnIWenhPbz7015neICpWnGP NWOQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=FkA3GpWL1Zxv4JJavWcUjQXw2FTocGT7kLd4J6NV31c=; b=sd45JcnPLAAZb83emDvH97VGKfpn9Y74XQxMd2EVaILlGKwH86werqZx65XPJjfder ZDeHM3T0ooC+D0MWwmcBRvguxvVkHPtnx1gwnmojWNQdsHhFsEtYSbt3qHWyqvLaJsmg 88gt37QxIevMsqw6CH02c+yzGVX7SPP+2ETXka0R+J4ouMr1Rr0pZwrSoYzDJJkOdWLZ lYj7hJorsX1T/yk6sCTYc7vYjbzaxrr7P7Z0RelOGcEjehm6J4L1skkxEsm3p4vlxcXg 7c+GF58ByKrbdHsn/1wZeaOmqpiNUyboQ9GbjdeBUfmKmHif9BGPpeseY3bi66rLLv0d iMdQ==
X-Gm-Message-State: AGRZ1gJR2VLr3EUrfx/SeKfY+wv4cULA481p0txIJ4/FYY8nE6OIIa07 GBs2eRGOENaY/8sOZlir+liWf+p1lERS6AdhglCekuee
X-Received: by 2002:ac2:434d:: with SMTP id o13-v6mr1248979lfl.129.1540475002292; Thu, 25 Oct 2018 06:43:22 -0700 (PDT)
From: Piers Powlesland <email@example.com>
Date: Thu, 25 Oct 2018 14:43:11 +0100
Content-Type: text/plain; charset="UTF-8"
Subject: Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) transitioning from prepare to commit.
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:firstname.lastname@example.org?subject=unsubscribe>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/din>, <mailto:email@example.com?subject=subscribe>
X-List-Received-Date: Thu, 25 Oct 2018 13:43:28 -0000
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 <firstname.lastname@example.org> 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
- [Din] draft-mazieres-dinrg-scp-04 (page 16) trans… Piers Powlesland
- Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) t… Piers Powlesland