commit 2d43555b1b43b62cc7efb6f234e42f6d2b936335
parent 5814d45f30017bde86f3750f30a57ec395c98b66
Author: Christian Grothoff <christian@grothoff.org>
Date: Thu, 11 Jul 2024 23:33:10 +0200
cite Kleinberg
Diffstat:
1 file changed, 24 insertions(+), 11 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -379,17 +379,22 @@
retrieve data in the proximity of its local minima.
</t>
<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 number of repetitions expected to cover all local minima depends on the
- current network size and this one of the parameters of the R<sup>5</sup>N
- routing algorithm.
+ 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.
</t>
</section>
<section numbered="true" toc="default">
@@ -2977,6 +2982,14 @@ Type | Name | References | Description
<date year="2002"/>
</front>
</reference>
+ <reference anchor="Smallworld" target="https://www.nature.com/articles/35022643">
+ <front>
+ <title>Navigation in a small world</title>
+ <author initials="J." surname="Kleinberg" fullname="Jon M. Kleinberg">
+ </author>
+ <date year="2000"/>
+ </front>
+ </reference>
<reference anchor="cadet" target="https://doi.org/10.1109/MedHocNet.2014.6849107">
<front>
<title>CADET: Confidential ad-hoc decentralized end-to-end transport</title>
