commit 696c84f74ae45b3ca89e3249c70fbeca9bd220b9
parent 0d4577cd9759c791185fff8ef2ba10c11ac9c7f6
Author: Christian Grothoff <christian@grothoff.org>
Date: Fri, 12 Jul 2024 09:14:46 +0200
add more references, justify path length
Diffstat:
1 file changed, 50 insertions(+), 23 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -178,7 +178,7 @@
We assume that the network is open and thus a fraction of
the participating peers is malicious. Malicious peers may
create, alter, delay or drop messages. We also assume that
- an adversary can control (or fake) many peers, thus any kind
+ an adversary can control (or fake) many peers <xref target="Sybil"/>, thus any kind
of voting or punishment of malicious peers would be rather
pointless.
</t>
@@ -381,20 +381,30 @@
<t>
R<sup>5</sup>N addresses this problem by prepending a random
walk before a classical, deterministic XOR-based routing
- algorithm is employed. If the network exhibits the
- properties of a small world topology, such a random walk
- will cause the algorithm to land on a random node in the
- network. Consequently, the deterministic part of the
- algorithm will encounter a random local minimum. It is then
- possible to repeat this process in order to store or
- retrieve data in the context of all or at least multiple
- local minima. The required length of the random walk and
- the number of repetitions expected to cover all local minima
- depends on the network topology. Our design assumes
- that the benign subset of the network forms a small-world
- topology <xref target="Smallworld"/> in which case it is
- sufficient to use an estimate of the current network
- size for the length of the random walk.
+ algorithm is employed. The optimal number of random hops
+ taken is equal to the mixing time of the graph. The mixing
+ time for various graphs is well known; for small-world
+ networks <xref target="Smallworld"/>, the mixing time has
+ been shown to be around <tt>O(log n)</tt> where <tt>n</tt>
+ is the number of nodes in the network
+ <xref target="Smallworldmix"/>.
+ </t>
+ <t>
+ Thus, if the network exhibits the properties of a small
+ world topology <xref target="Smallworld"/>, a random walk of
+ length <tt>O(log n)</tt> will cause the algorithm to land on
+ a random node in the network. Consequently, the
+ deterministic part of the algorithm will encounter a random
+ local minimum. It is then possible to repeat this process
+ in order to store or retrieve data in the context of all or
+ at least multiple local minima. The ideal length of the
+ random walk and the number of repetitions expected to cover
+ all local minima depends on the network topology. Our
+ design assumes that the benign subset of the network forms a
+ small-world topology <xref target="Smallworld"/> and then
+ obtains an estimate of the current number of nodes
+ <tt>n</tt> in the network and then uses <tt>log n</tt> for
+ the actual length of the random walk.
</t>
</section>
<section numbered="true" toc="default">
@@ -794,11 +804,12 @@ Connectivity | |Underlay| |Underlay| | Underlay | ...
</t>
<t>
In order to select peers which are suitable destinations for
- routing messages, R<sup>5</sup>N uses a hybrid approach:
- Given an estimated network size <tt>L2NSE</tt> retrieved using <tt>ESTIMATE_NETWORK_SIZE ()</tt>,
- the peer selection for the first <tt>L2NSE</tt> hops is random. After the initial
- <tt>L2NSE</tt> hops, peer selection
- follows an XOR-based peer distance calculation.
+ routing messages, R<sup>5</sup>N uses a hybrid approach: Given
+ an estimated network size <tt>L2NSE</tt> retrieved using
+ <tt>ESTIMATE_NETWORK_SIZE ()</tt>, the peer selection for the
+ first <tt>L2NSE</tt> hops is random. After the initial
+ <tt>L2NSE</tt> hops, peer selection follows an XOR-based peer
+ distance calculation.
<xref target="routing_functions"/>
describes the corresponding routing functions.
</t>
@@ -2764,9 +2775,9 @@ BEGIN
If an upper bound to the maximum number of neighbors in a
k-bucket is reached, the implementation <bcp14>MUST</bcp14>
prefer to preserve the oldest working connections instead of
- new connections. This makes Sybil attacks less effective
- as an adversary would have to invest more resources over time
- to mount an effective attack.
+ new connections. This makes Sybil attacks <xref
+ target="Sybil"/> less effective as an adversary would have to
+ invest more resources over time to mount an effective attack.
</t>
<t>
The <tt>ComputeOutDegree</tt> function limits the
@@ -3004,6 +3015,22 @@ Type | Name | References | Description
<date year="2002"/>
</front>
</reference>
+ <reference anchor="Sybil" target="https://link.springer.com/chapter/10.1007/3-540-45748-8_24">
+ <front>
+ <title>The Sybil Attack</title>
+ <author initials="J." surname="Douceur" fullname="John R. Douceur">
+ </author>
+ <date year="2002"/>
+ </front>
+ </reference>
+ <reference anchor="Smallworldmix" target="https://api.semanticscholar.org/CorpusID:44240877">
+ <front>
+ <title>A Measurement of Mixing Time in Social Networks</title>
+ <author initials="M." surname="Dell'Amico" fullname="Matteo Dell'Amico">
+ </author>
+ <date year="2009"/>
+ </front>
+ </reference>
<reference anchor="Smallworld" target="https://www.nature.com/articles/35022643">
<front>
<title>Navigation in a small world</title>
