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
- [Din] draft-mazieres-dinrg-scp-04 (page 16) Poten… Piers Powlesland
- Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) P… David Mazieres
- Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) P… Piers Powlesland
- Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) P… David Mazieres
- Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) P… Piers Powlesland
- Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) P… David Mazieres
- Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) P… Piers Powlesland