Subject: [Din] draft-mazieres-dinrg-scp-04 peer priority algorithm

From: Piers Powlesland <[email-masked]>
Date: Tue, 7 Aug 2018 17:58:10 +0100

Hello,

On page 10 of https://tools.ietf.org/pdf/draft-mazieres-dinrg-scp-04.pdf
an algorithm is described to determine the priority of peers for a
given node.

Peers are selected from a set "neighbours" based on a priority
calculated for each peer. The "neighbours" set is constructed by
taking the set of peers that constitute the quorum slices for a node
and then filtering them to remove any peer for which

sha-256(slot_number || 1 || nomination_round || peer_id ) < 2^256 *
weight(peer_id)

Where "||" means concatenation of serialised values and
"weight(peer_id)" is the fraction of slices containing peer_id.

As I understand, this filtering could lead to a situation where the
neighbours set is empty, since there is no guarantee that any hash
calculated above will be less than '2^256 * weight(peer_id)'. Is this
intentional? Also what is the motivation for creating the "neighbours"
set as opposed to simply selecting a peer from all peers based on
their priority weighted by their weight?

---

From: David Mazieres <[email-masked]>
Date: Tue, 07 Aug 2018 13:02:27 -0700

Piers Powlesland <[email-masked]> writes:

> intentional?

There is a guarantee, because a node must belong to all of its own
quorum sets.  So even if a node has no other neighbors, it will still be
its own neighbor... which highlights the fact that maybe "neighbor" is a
misleading term here?  Or maybe at least suggests we should mention
this.

> Also what is the motivation for creating the "neighbours"

The goal of this neighbor/priority scheme is twofold:

   1. Ensure that nodes that are not very important (because they appear
      only in a few quorum slices) also do not very often get to dictate
      the consensus value.

   2. Make it likely for nodes to listen to the same nodes for
      nomination values, so as to minimize the number of different
      values nominated.

The neighbor selection achieves #1, while the prioritization achieves
#2.  You seem to be proposing a unified mechanism that would ideally
achieve both goals at once, but don't think actually does.

As an example, suppose that my quorum slices consist of myself plus one
of 4 US nodes, plus one of 100 Chinese nodes.  (Assume the US and
Chinese nodes depends on one another in a robust way so the system is
safe.)  With your scheme, I will usually nominate my own value,
sometimes listen to one of the US nominated values, and almost never
listen to a Chinese node (because my own hash value would have to be
less than 0.01*2^256 and the US nodes would all have to be less then
0.04*2^256 for any Chinese node to have a chance).  In reality, my
quorum slice selection indicates that I consider Chinese nodes, in
aggregate, as important as US nodes--there just happen to be more
Chinese nodes.  So your scheme doesn't properly reflect the importance
of the nodes.

Does that make sense?

David

---

From: David Mazieres <[email-masked]>
Date: Tue, 07 Aug 2018 13:08:24 -0700

> misleading term here?  Or maybe at least suggests we should mention

I went to clarify this in the draft and realize it's not clear at all
because of the way slices are defined.  (You implicitly have to be in a
quorum, but it never says you are in every slice.)  So I propose the
following wording on neighbors:

   o  Define the set of nodes "neighbors(n)" as the set of nodes v for
      which "Gi(1 || n || v) < 2^{256} * weight(v)", where "1" and "n"
      are both 32-bit XDR "int" values.  Note that a node is always its
      own neighbor because conceptually a node belongs to all of its own
      quorum slices.

David

---

From: Piers Powlesland <[email-masked]>
Date: Fri, 10 Aug 2018 18:14:24 +0100

Hi David,

The new wording looks good to me.

And thanks for clarifying the 2 stage approach to choosing a preferred
peer, I can see now that my approach would not correctly reflect the
importance nodes as they appear in SCPSlices.
On Tue, Aug 7, 2018 at 9:08 PM David Mazieres