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

David Mazieres <dm-list-ietf-ilc@scs.stanford.edu> Thu, 08 November 2018 14:03 UTC

Return-Path: <dm-list-ietf-ilc@scs.stanford.edu>
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 DFDD2126CB6 for <din@ietfa.amsl.com>; Thu, 8 Nov 2018 06:03:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.001
X-Spam-Level:
X-Spam-Status: No, score=-2.001 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=scs.stanford.edu
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 EU3WGnc687mY for <din@ietfa.amsl.com>; Thu, 8 Nov 2018 06:03:21 -0800 (PST)
Received: from market.scs.stanford.edu (www.scs.stanford.edu [IPv6:2001:470:806d:1::9]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 21B3D126BED for <din@irtf.org>; Thu, 8 Nov 2018 06:03:21 -0800 (PST)
Received: from market.scs.stanford.edu (localhost [127.0.0.1]) by market.scs.stanford.edu (8.16.0.29/8.16.0.21) with ESMTP id wA8E3Jv9047842; Thu, 8 Nov 2018 06:03:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=scs.stanford.edu; s=scs; t=1541685799; bh=+hOJCkDiZOlMaiKEaue7fKKWXBN1wcLlO/+FRnyQtvg=; h=From:To:Subject:In-Reply-To:References:Date:Message-ID: MIME-Version; b=c/w0O18a3GZCN6Otzt644xrutI9+ztZqtKuQccAr7AvXDnPzMzsYti1uy1c0VGVVH 6A5+p7B189hyHviEtJTN11OXlwo26LwVGSerdr2NH53PHRAsyBizepVKtabEApdtgm 8VNpi5R/GuoKegXMNerUcvR4Z3j82z259FyMp74A=
Received: (from dm@localhost) by market.scs.stanford.edu (8.16.0.29/8.16.0.29/Submit) id wA8E3JoE070175; Thu, 8 Nov 2018 06:03:19 -0800 (PST)
From: David Mazieres <dm-list-ietf-ilc@scs.stanford.edu>
To: Piers Powlesland <pierspowlesland@gmail.com>
Cc: din@irtf.org
In-Reply-To: <CAFXacXnXihDveCZSRBk4ESiFS1j1inS+5H=hAO0AiFwc2=BY7A@mail.gmail.com>
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>
Reply-To: David Mazieres expires 2019-02-06 PST <mazieres-sy3tdz4cdzgjttyvjih579mqfw@temporary-address.scs.stanford.edu>
Date: Thu, 08 Nov 2018 06:03:18 -0800
Message-ID: <87muqj7jkp.fsf@ta.scs.stanford.edu>
MIME-Version: 1.0
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/din/aeVPsR3i3me6OAJ89mMPTNFERuo>
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 14:03:23 -0000

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