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

David Mazieres <> Fri, 02 November 2018 14:59 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 7E61E12785F for <>; Fri, 2 Nov 2018 07:59:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.001
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: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 0_dZ6d9IBzTw for <>; Fri, 2 Nov 2018 07:59:50 -0700 (PDT)
Received: from ( [IPv6:2001:470:806d:1::9]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 29E941294D7 for <>; Fri, 2 Nov 2018 07:59:50 -0700 (PDT)
Received: from (localhost []) by ( with ESMTP id wA2ExmW4061271; Fri, 2 Nov 2018 07:59:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=scs; t=1541170788; bh=jAjUAuQheXoYqh3+fq0S4IecS99jGBd9UIwFysA+kfk=; h=From:To:Subject:In-Reply-To:References:Date:Message-ID: MIME-Version; b=j4L3J7qnSBuNvp8qUStnf/u/szxEFR0pvGGrR0NKZmxnoZ94m7HZNyF1Ce7iDZhgC jo+YZNCadaeLxYbQFZfA0cb5g/m4heNrpqX6zuhwXEwTlWkzhW+4pxflKLYPKKF1Qp qKPSI+nQSmTkXYKTDSeT9tjPNZ2KoMUdIm2LzxU8=
Received: (from dm@localhost) by ( id wA2ExmkN015649; Fri, 2 Nov 2018 07:59:48 -0700 (PDT)
From: David Mazieres <>
To: Piers Powlesland <>,
In-Reply-To: <>
References: <>
Reply-To: David Mazieres expires 2019-01-31 PST <>
Date: Fri, 02 Nov 2018 07:59:48 -0700
Message-ID: <>
MIME-Version: 1.0
Content-Type: text/plain
Archived-At: <>
Subject: Re: [Din] draft-mazieres-dinrg-scp-04 (page 16) Potential improvement to balloting protocol, setting cCounter
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Discussion of distributed Internet Infrastructure approaches, aspects such as Service Federation, and underlying technologies" <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 02 Nov 2018 14:59:52 -0000

Piers Powlesland <> writes:

> I think it may be possible to improve the chances of nodes being able
> to accept ballots as committed during the prepare phase.
> The following instructions are given to update cCounter.
>> * If either "(prepared > c && prepared.value != c.value)" or
>>   "(preparedPrime > c && preparedPrime.value != c.value)", then
>>   reset "c = NULL".
>> * If "c == NULL" and "hCounter == ballot.counter" (meaning
>>    "ballot" is confirmed prepared), then set "c" to "ballot".
> If we consider an example where a node has the following state.
> ballot = (8,x)
> prepared = (8,x)
> preparedPrime = (3,y)
> cCounter = 4
> hCounter = 8
> If the node accepts prepared (4,z) then using the update steps above c
> will be set to NULL and then c will be set to ballot.

That's correct.  This is because the messages only encode cCounter
instead of c.  Since c.value is implicit, you don't want to vote to
commit the wrong ballot.  (In fact, I will change preparedPrime to be
preparedPrimeCounter in the next version, too.)

> This means that the node will transition from voting to commit ballots
> with value == x and counters 4...8 to just the single ballot (8,x).

You mean transition to voting to commit nothing?  (Though still
vote-or-confirm (n,x) for 4 <= n <= 8.)

> Out of the ballots that the node was previously voting to commit only
> (4,x) has been accepted aborted due to setting preparedPrime = (4,z),
> so it seems that it would still be legal to vote to commit ballots
> with value == x and counters 5...8.

Not necessarily.  Whether or not it's safe to commit (5,x) depends on
history.  It's only safe to vote to commit a ballot b if ballot == b at
the time b was confirmed prepared.  If, for instance, hCounter jumps
from 0 to 8 in the history, then the node has no memory of whether it
is, say voted to prepare (4,z), which would make it illegal to vote to
commit (4,x).

> So I am proposing that the first part of the above update step is
> changed to the following, to allow for that.
>> * If c != NULL set c.counter to the counter of the lowest ballot with value ==
>>   h.value and not accepted aborted according to p and p'. If c.counter >
>>   hCounter, then set c=NULL

To be correct, you might also need to raise h such that you've never
voted to abort anything between h and the new c, but I don't think nodes
have enough state to do that.  So the current algorithm is safe but
"wasteful" of potentially useful ballots.