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

Piers Powlesland <pierspowlesland@gmail.com> Thu, 08 November 2018 17:02 UTC

Return-Path: <pierspowlesland@gmail.com>
X-Original-To: din@ietfa.amsl.com
Delivered-To: din@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6C0701310A9 for <din@ietfa.amsl.com>; Thu, 8 Nov 2018 09:02:49 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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, URIBL_BLOCKED=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 ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vgmPbXEWJknU for <din@ietfa.amsl.com>; Thu, 8 Nov 2018 09:02:42 -0800 (PST)
Received: from mail-lj1-x236.google.com (mail-lj1-x236.google.com [IPv6:2a00:1450:4864:20::236]) (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 97E33130F62 for <din@irtf.org>; Thu, 8 Nov 2018 09:02:41 -0800 (PST)
Received: by mail-lj1-x236.google.com with SMTP id j4-v6so18621658ljc.12 for <din@irtf.org>; Thu, 08 Nov 2018 09:02:41 -0800 (PST)
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 :cc; bh=+yDCPDNiDid9Y9zr8ao9FwSnCBKUM9TzV9PzmgDmhC4=; b=Nt6Xw+/v6rNm/sGK+tW5WMVa8ETE6YuVlRo11C3bYxGrhQM+clCsjWau2UpWKKSzMA oVIM2Q5ZIRWkcwEbRvjC+hZMBKzjScFbmV8g9oXbyGWmYNIsbdJOmbsgfDhJ/gpYq550 PpqUbpE8qlI+vfPH9PtUoxvPnhkYcXY5bQKEvNRdJHp0Nt4fo/4oUr5wfzwjgS+pkXBs p1eQDDwgk6p3VJ4u3j1H9ll1Z/ilHtSM9UUg4KqmJvT4AncQec3GBlmKhQjoo5BNvooK lNRHdyEOGERd8Adl9Wf+aMrqg/N0ZVbC7gJNK8XH7w5EvpbWyc6zYuyOtz9BYcLaVmul 7m3Q==
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:cc; bh=+yDCPDNiDid9Y9zr8ao9FwSnCBKUM9TzV9PzmgDmhC4=; b=Ax+RU0snKU5HcgvBTrmq35M/ZbK1uRjl8S35eNE7JAk3f43Ae0YupObAXG0f7sYPiK ppK2LjN9jR5UEfris+5A+g4h97Hq3EGpbltPZ46G4w412D/CMqE4S1o5gz0oT575Mj6p TLzX/lq5V6vr7aTRsRIVWaiowdt2wuCqk/5cQE6rr5TdiU1T1mFGUGfYItIblYfA6ptw LGTQPo6dzhaMbI5i7DHWPZhZL95pHuJziBBVhXyheoGD9GfyDcVV4tPaxWySV03XucEk 0h4mWghuk3PsYki3p/GHcTo6pyaGB6efUv9xjVMC/x3TyWUhWWikQSXDnBuUenK33XsN he8A==
X-Gm-Message-State: AGRZ1gK1X0AS+4UvV0eF6XYdNkTkuIpDIlDFxgCyBLE/vIoL/+FhkGi6 aqFulrb6Sb53OlHrGuKDt+velyD6HKlcch2/fCVcN4DF
X-Google-Smtp-Source: AJdET5fUtHEeH1cEWQfqIS5HVYuLmHfgPlGsoGOeETZk4vmajRx21RgahxD0EaC7QxDoDoiwA5UoSjFkMAcOOEk3l3M=
X-Received: by 2002:a2e:9e10:: with SMTP id e16-v6mr3366057ljk.169.1541696559426; Thu, 08 Nov 2018 09:02:39 -0800 (PST)
MIME-Version: 1.0
References: <CAFXacXm5U6VNEyQ3ienwgcGaAj1yQ1YVJNFT1eY9EMRsNFZ9hA@mail.gmail.com> <87va5fsexn.fsf@ta.scs.stanford.edu> <CAFXacXnWJN8d8SutKEj0OyvUWKnp7EgnpX-bA8SBPcX=K-zsdQ@mail.gmail.com> <875zxezkus.fsf@ta.scs.stanford.edu> <CAFXacXnXihDveCZSRBk4ESiFS1j1inS+5H=hAO0AiFwc2=BY7A@mail.gmail.com> <87muqj7jkp.fsf@ta.scs.stanford.edu>
In-Reply-To: <87muqj7jkp.fsf@ta.scs.stanford.edu>
From: Piers Powlesland <pierspowlesland@gmail.com>
Date: Thu, 8 Nov 2018 17:02:28 +0000
Message-ID: <CAFXacX=D_rGy5LLp0-PWUON4w4dvGMTiZqnNSy=w=NYLFiZLiw@mail.gmail.com>
To: mazieres-sy3tdz4cdzgjttyvjih579mqfw@temporary-address.scs.stanford.edu
Cc: din@irtf.org
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/din/YbIEAU17SsBqqGNycMZZROW5DgI>
Subject: Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) Potential improvement to balloting protocol, setting cCounter
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: Thu, 08 Nov 2018 17:02:53 -0000

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
<dm-list-ietf-ilc@scs.stanford.edu> wrote:
>
> Piers Powlesland <pierspowlesland@gmail.com> 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