summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMartin Schanzenbach <schanzen@gnunet.org>2021-12-25 12:44:29 +0100
committerMartin Schanzenbach <schanzen@gnunet.org>2021-12-25 12:44:29 +0100
commit898087a43b3ddb5de9bc3d26aabdb3714563b185 (patch)
treef0cffb814af9626051dca8ce95113f802d2d0936
parent9346b9b61174f9b61e86cc5db2cad1e18bf86ffc (diff)
downloadlsd0004-898087a43b3ddb5de9bc3d26aabdb3714563b185.tar.gz
lsd0004-898087a43b3ddb5de9bc3d26aabdb3714563b185.zip
minor update
-rw-r--r--draft-schanzen-r5n.xml42
1 files changed, 34 insertions, 8 deletions
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 9e0d9e4..8a818da 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -458,10 +458,17 @@ see how we can offer even the most minimal protections against peer
458 </t> 458 </t>
459 <!-- Fixme: We may want to propose our modified, optimized XOR metric here or reference Kademlia --> 459 <!-- Fixme: We may want to propose our modified, optimized XOR metric here or reference Kademlia -->
460 <t> 460 <t>
461 The procedure to select a peer for a given message key and bloomfilter 461 R5N stores the information of all connected peers in a a set of lists
462 is defined as follows: 462 similar to the k-buckets data structure of <xref target="Kademlia"/>.
463 The index which determines in which of the k lists to add a given peer
464 is calculated using the FIND-BUCKET procedure (see <xref target="find-bucket"/>.
463 </t> 465 </t>
464 <figure> 466 <t>
467 The buckets serve implicitly as a routing table for messages:
468 In order to select a peer for a given message key and bloomfilter,
469 the <tt>PEER-SELECT</tt> is used (see <xref target="peer-select"/>.
470 </t>
471 <figure anchor="peer-select">
465 <artwork name="" type="" align="left" alt=""><![CDATA[ 472 <artwork name="" type="" align="left" alt=""><![CDATA[
466PEER-SELECT(key, bloomfilter) 473PEER-SELECT(key, bloomfilter)
467 peers := <Select all known peers NOT in message bloomfilter> 474 peers := <Select all known peers NOT in message bloomfilter>
@@ -484,18 +491,23 @@ END
484 The procedure to determine if we are the closest know peer for a given 491 The procedure to determine if we are the closest know peer for a given
485 message key and bloomfilter is defined as follows: 492 message key and bloomfilter is defined as follows:
486 </t> 493 </t>
487 <figure> 494 <figure anchor="find-bucket">
488 <artwork name="" type="" align="left" alt=""><![CDATA[ 495 <artwork name="" type="" align="left" alt=""><![CDATA[
489FIND-BUCKET(peerID, key, buckets) 496FIND-BUCKET(peerID, key, kbuckets)
490 N := MATCHING-BITS (peerID, key) 497 N := MATCHING-BITS (peerID, key)
491 return Nth bucket FROM buckets 498 return Nth bucket FROM kbuckets
492END 499END
493AM-CLOSEST-PEER(key, myPeerID, bloomfilter, buckets) 500 ]]></artwork>
501 </figure>
502 <t>The FIND-BUCKET Procedure.</t>
503 <figure>
504 <artwork name="" type="" align="left" alt=""><![CDATA[
505AM-CLOSEST-PEER(key, peerID, bloomfilter, buckets)
494 closestPeersBucket := FIND-BUCKET (myPeerID, key, buckets) 506 closestPeersBucket := FIND-BUCKET (myPeerID, key, buckets)
495 IF key == myPeerID 507 IF key == myPeerID
496 return TRUE 508 return TRUE
497 END 509 END
498 myDistance := XOR(myPeerID, key) 510 myDistance := XOR(peerID, key)
499 FOR EACH p IN closestPeersBucket 511 FOR EACH p IN closestPeersBucket
500 IF XOR(p, key) < myDistance 512 IF XOR(p, key) < myDistance
501 return FALSE 513 return FALSE
@@ -508,6 +520,7 @@ AM-CLOSEST-PEER(key, myPeerID, bloomfilter, buckets)
508END 520END
509 ]]></artwork> 521 ]]></artwork>
510 </figure> 522 </figure>
523 <t>The AM-CLOSEST-PEER Procedure.</t>
511 524
512 525
513 </section> 526 </section>
@@ -1158,6 +1171,19 @@ Purpose | Name | References | Description
1158 <date year="2011"/> 1171 <date year="2011"/>
1159 </front> 1172 </front>
1160 </reference> 1173 </reference>
1174 <reference anchor="Kademlia" target="http://css.csail.mit.edu/6.824/2014/papers/kademlia.pdf">
1175 <front>
1176 <title>Kademlia: A peer-to-peer information system based on the xor metric.</title>
1177 <author initials="P." surname="Maymounkov" fullname="Petar Maymounkov">
1178 </author>
1179
1180 <author initials="D." surname="Mazieres"
1181 fullname="David Mazieres">
1182 </author>
1183 <date year="2002"/>
1184 </front>
1185 </reference>
1186
1161 <reference anchor="cadet" target="https://doi.org/10.1109/MedHocNet.2014.6849107"> 1187 <reference anchor="cadet" target="https://doi.org/10.1109/MedHocNet.2014.6849107">
1162 <front> 1188 <front>
1163 <title>CADET: Confidential ad-hoc decentralized end-to-end transport</title> 1189 <title>CADET: Confidential ad-hoc decentralized end-to-end transport</title>