lsd0004

LSD0004: R5N Distributed Hash Table
Log | Files | Refs

commit bfc35b90931460b506f797f4104d6b411311449c
parent 4ad3f38f90b2720df4b54568223c6b33a0ab3324
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date:   Mon, 15 Jul 2024 12:14:42 +0200

remove unnecessary emphasis

Diffstat:
Mdraft-schanzen-r5n.xml | 102++++++++++++++++++++++++++++++++++++++++----------------------------------------
1 file changed, 51 insertions(+), 51 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml @@ -261,10 +261,10 @@ It includes logic for enforcing storage quotas, caching strategies and block validation. </dd> - <dt>Block-Type</dt> + <dt>Block Type</dt> <dd> A unique 32-bit value identifying the data format of a <em>block</em>. - <em>Block-types</em> are either private or registered in the GANA block type registry (see + <em>Block types</em> are either private or registered in the GANA block type registry (see <xref target="gana_block_type"/>). </dd> <dt>Bootstrapping</dt> @@ -470,15 +470,15 @@ </t> <ul> <li> - <tt>PUT</tt>: This operation stores a <em>block</em> - under a <em>key</em> on one or more <em>peers</em> with - the goal of making the <em>block</em> availiable for queries using the <tt>GET</tt> operation. + <tt>PUT</tt>: This operation stores a block + under a key on one or more peers with + the goal of making the block availiable for queries using the <tt>GET</tt> operation. In the classical definition of a dictionary interface, this operation would be called "insert". </li> <li> - <tt>GET</tt>: This operation queries the network of peers for any number of <em>blocks</em> - previously stored under or near a <em>key</em>. + <tt>GET</tt>: This operation queries the network of peers for any number of blocks + previously stored under or near a key. In the classical definition of a dictionary interface, this operation would be called "find". </li> @@ -489,11 +489,11 @@ outlined in <xref target="overlay"/>. </t> <t> - A <em>peer</em> does not necessarily need to expose the above - operations to <em>applications</em>, but it commonly will. A - <em>peer</em> that does not expose the above operations could - be a host purely used for <em>bootstrapping</em>, - <em>routing</em> or supporting + A peer does not necessarily need to expose the above + operations to applications, but it commonly will. A + peer that does not expose the above operations could + be a host purely used for bootstrapping, + routing or supporting the overlay network with resources. </t> <t> @@ -502,10 +502,10 @@ data. Examples for such hosts would be mobile devices with limited bandwidth, battery and storage capacity. Such hosts may be used to run applications that use the DHT. However, we - will not refer to such hosts as <em>peers</em>. + will not refer to such hosts as peers. </t> <t> - In a trivial scenario where there is only one <em>peer</em> (on the local host), + In a trivial scenario where there is only one peer (on the local host), R<sup>5</sup>N operates similarly to a dictionary data structure. However, the default use case is one where nodes communicate directly and indirectly in order to realize a distributed storage mechanism. @@ -525,26 +525,26 @@ <!-- consider moving some of this back into sec considerations --> <t> Specifics about the protocols of the underlays implementing - the <em>underlay interface</em> or the <em>applications</em> + the underlay interface or the applications using the DHT are out of the scope of this document. </t> <t> To establish an initial connection to a network of R<sup>5</sup>N peers, at least one initial, addressable - <em>peer</em> is required as part of the - <em>bootstrapping</em> process. Further <em>peers</em>, - including <em>neighbors</em>, are then learned via a peer + peer is required as part of the + bootstrapping process. Further peers, + including neighbors, are then learned via a peer discovery process as defined in <xref target="find_peer"/>. </t> <t> Across this document, the functional components of an R<sup>5</sup>N implementation are divided into - <em>routing</em> (<xref target="routing"/>), <em>message - processing</em> (<xref target="p2p_messages"/>) and + routing (<xref target="routing"/>), message + processing (<xref target="p2p_messages"/>) and block processing (<xref target="blockstorage"/>). - <em>Applications</em> that require application-specific - <em>block</em> payloads are expected to register a - <em>Block-Type</em> in the GANA <em>Block-Type</em> registry + Applications that require application-specific + block payloads are expected to register a + block type in the GANA Block Type registry (<xref target="gana_block_type"/>) and provide a specification of the associated block operations (<xref target="block_functions"/>) to implementors of @@ -591,12 +591,12 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... expose a QUIC endpoint, or both. While the specific addressing options and mechanisms are out of scope, it is necessary to define a universal addressing format in order to facilitate the - distribution of <em>address</em> information to other - <em>peers</em> in the DHT overlay. This standardized format - is the <em>HELLO Block</em> (described in <xref + distribution of address information to other + peers in the DHT overlay. This standardized format + is the HELLO block (described in <xref target="hello_block"/>), which contains sets of addresses. If the address is a URI, it may indicate which - underlay understands the respective <em>address</em>. + underlay understands the respective address. </t> <!-- 1) The current API is always fire+forget, it doesn't allow for flow @@ -632,7 +632,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... <t> It is expected that the underlay provides basic mechanisms to manage peer connectivity and addressing. - The essence of the <em>underlay interface</em> is + The essence of the underlay interface is captured by the following set of API calls: </t> <dl> @@ -727,7 +727,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... peer. Underlays may include meta-data about the connection, for example to indicate that the connection is from a resource-constrained host that does not intend to function - as a full <em>peer</em> and thus should not be considered + as a full peer and thus should not be considered for routing. </dd> <dt> @@ -774,7 +774,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... To enable routing, any R<sup>5</sup>N implementation must keep information about its current set of neighbors. Upon receiving a connection notification from the - <em>underlay interface</em> through a + underlay interface through a <tt>PEER_CONNECTED</tt> signal, information on the new neighbor <bcp14>MUST</bcp14> be added to the routing table, except if the respective <tt>k</tt>-bucket in the routing table is full or if meta-data @@ -792,7 +792,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... the data structure for managing neighbors and their metadata <bcp14>MUST</bcp14> be implemented using the k-buckets concept of <xref target="Kademlia"/> as defined in <xref target="routing_table"/>. - Maintenance of the routing table (after <em>bootstrapping</em>) is + Maintenance of the routing table (after bootstrapping) is described in <xref target="find_peer"/>. </t> <t> @@ -826,17 +826,17 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... the underlay, the respective peer is considered for insertion into the routing table. The routing table consists of an array of <tt>k</tt>-buckets. Each - <tt>k</tt>-bucket contains a list of <em>neighbors</em>. + <tt>k</tt>-bucket contains a list of neighbors. The i-th <tt>k</tt>-bucket stores neighbors whose peer public keys are between XOR-distance 2<sup>i</sup> and 2<sup>i+1</sup> from the local peer; <tt>i</tt> can be directly computed from the two peer identities using the <tt>GetDistance()</tt> function. System constraints will typically force an implementation to impose some upper limit - on the number of <em>neighbors</em> kept per + on the number of neighbors kept per <tt>k</tt>-bucket. Upon insertion, the implementation <bcp14>MUST</bcp14> call <tt>HOLD()</tt> on the respective - <em>neighor</em>. + neighor. </t> <t> Implementations <bcp14>SHOULD</bcp14> try to keep at least @@ -851,14 +851,14 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... <t> If a system hits constraints with respect to the number of active connections, an implementation - <bcp14>MUST</bcp14> evict <em>neighbours</em> from those <tt>k</tt>-buckets with the + <bcp14>MUST</bcp14> evict neighbours from those <tt>k</tt>-buckets with the largest number of neighbors. The eviction strategy <bcp14>MUST</bcp14> be to drop the shortest-lived connection per <tt>k</tt>-bucket first. </t> <t> - Implementations <bcp14>MAY</bcp14> cache valid <em>addresses</em> of disconnected - <em>peers</em> outside of the routing table and sporadically or periodically try to (re-)establish connection - to the <em>peer</em> by making <tt>TRY_CONNECT()</tt> calls to the <em>underlay interface</em> + Implementations <bcp14>MAY</bcp14> cache valid addresses of disconnected + peers outside of the routing table and sporadically or periodically try to (re-)establish connection + to the peer by making <tt>TRY_CONNECT()</tt> calls to the underlay interface if the respective <tt>k</tt>-bucket has empty slots. </t> </section> @@ -867,13 +867,13 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... <t> Initially, implementations depend upon either the underlay providing at least one initial connection to a - <em>neighbor</em> (signalled through - <tt>PEER_CONNECTED</tt>), or the <em>application</em> or + neighbor (signalled through + <tt>PEER_CONNECTED</tt>), or the application or even end-user providing at least one working <tt>HELLO</tt> which is then in turn used to call <tt>TRY_CONNECT()</tt> on the underlay in order to trigger a subsequent - <tt>PEER_CONNECTED</tt> signal from the <em>underlay - interface</em>. This is commonly achieved through the + <tt>PEER_CONNECTED</tt> signal from the underlay + interface. This is commonly achieved through the configuration of hardcoded bootstrap peers or bootstrap servers either for the underlay or the R<sup>5</sup>N implementation. The first connection <bcp14>SHOULD</bcp14> be established @@ -899,7 +899,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... <bcp14>MUST</bcp14> be initialized to filter the peer's own peer identity as well as the peer identities of all currently connected - <em>neighbors</em>. These requests <bcp14>MUST</bcp14> use + neighbors. These requests <bcp14>MUST</bcp14> use the <tt>FindApproximate</tt> and <tt>DemultiplexEverywhere</tt> flags. <tt>FindApproximate</tt> will ensure that other peers @@ -922,7 +922,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... provided if a peer can only establish outgoing connections and is otherwise unreachable. An implementation <bcp14>MUST</bcp14> advertise its addresses periodically to - its <em>neighbors</em> through <tt>HelloMessages</tt>. The + its neighbors through <tt>HelloMessages</tt>. The advertisement interval and expiration <bcp14>SHOULD</bcp14> be configurable. If the values are chosen at the discretion of the @@ -1075,7 +1075,7 @@ Connectivity | |Underlay| |Underlay| | Underlay | ... </dt> <dd> <t> - This function computes the number of <em>neighbors</em> + This function computes the number of neighbors that a message should be forwarded to. The arguments are the desired replication level (<tt>REPL_LVL</tt>), the <tt>HOPCOUNT</tt> of the message so far and @@ -1179,13 +1179,13 @@ BEGIN An implementation will process messages either because it needs to transmit messages as part of routing table maintenance, or due to requests from local applications, or - because it received a message from a <em>neighbor</em>. + because it received a message from a neighbor. If instructed through an application-facing API such as the one outlined - in <xref target="overlay"/>, a peer acts as an <em>initiator</em> + in <xref target="overlay"/>, a peer acts as an initiator of <tt>GetMessages</tt> or <tt>PutMessages</tt>. The status of initiator is relevant for peers when processing <tt>ResultMessages</tt> - due to the required handover of results to the originating <em>application</em>. + due to the required handover of results to the originating application. </t> <t> The implementation <bcp14>MUST</bcp14> listen for <tt>RECEIVE(P, M)</tt> signals @@ -1228,7 +1228,7 @@ BEGIN </dd> <dt>2: FindApproximate</dt> <dd> - This bit asks peers to return results even if the <em>key</em> + This bit asks peers to return results even if the key does not exactly match the query hash. </dd> <dt>3: Truncated</dt> @@ -3599,12 +3599,12 @@ bchar = *(ALPHA / DIGIT) </artwork> </figure> <t> - It specifies that the peer with the <em>pid</em> "1MVZ..." + It specifies that the peer with the <tt>pid</tt> "1MVZ..." is reachable via "foo" at "example.com" and "bar+baz" at "1.2.3.4" on port 5678 until 1708333757 seconds after the Epoch. Note that "foo" and "bar+baz" here are underspecified and just used as a simple example. - In practice, the <em>addr-name</em> refers to a scheme supported by a + In practice, the <tt>addr-name</tt> refers to a scheme supported by a DHT underlay. </t> </section>