[lsd0004] branch master updated: use bit, not bucket for Bloom filter bits

[gnunet]

This is an automated email from the git hooks/post-receive script.

grothoff pushed a commit to branch master
in repository lsd0004.

The following commit(s) were added to refs/heads/master by this push:
     new 4418802  use bit, not bucket for Bloom filter bits
4418802 is described below

commit 4418802490a141a64dcea94b6bb0e12090f84d98
Author: Christian Grothoff <grothoff@gnunet.org>
AuthorDate: Sun Aug 20 16:52:17 2023 +0200

    use bit, not bucket for Bloom filter bits
---
 draft-schanzen-r5n.xml | 71 +++++++++++++++++++++++++-------------------------
 1 file changed, 36 insertions(+), 35 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 158ec90..5797c62 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -630,7 +630,7 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
        <em>underlay interface</em> 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 bucket in the routing table is full or if meta-data
+       respective <tt>k</tt>-bucket in the routing table is full or if 
meta-data
        is present that indicates that the peer does not wish to participate
        in routing.
         Peers added to the routing table <tt>SHOULD</tt> be signalled to the
@@ -696,7 +696,7 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
           to drop the shortest-lived connection per <tt>k</tt>-bucket first.
         </t>
         <t>
-          The implementation <bcp14>MAY</bcp14> cache valid <em>addresses</em> 
of disconnected
+          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>
          if the respective <tt>k</tt>-bucket has empty slots.
@@ -705,53 +705,54 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
       <section anchor="find_peer">
         <name>Peer Discovery</name>
         <t>
-          Initially, the implementation depends upon either the Underlay 
providing at
-          least one initial connection to a peer (signalled through
-          <tt>PEER_CONNECTED</tt>), or the application/end-user providing at
+          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 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 Underlay.
+          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 configuration of hardcoded 
bootstrap peers
-          or bootstrap servers either for the Underlay or the R<sup>5</sup>N 
implementation.
+          or bootstrap servers either for the underlay or the R<sup>5</sup>N 
implementation.
           While details on how the first connection is established 
<bcp14>MAY</bcp14>
           depend on the specific implementation, this <bcp14>SHOULD</bcp14> 
usually be done
           by an out-of-band exchange of the information from a <tt>HELLO</tt> 
block.
           Section <xref target="hello_url"/> specifies a URL format for 
encoding HELLO
           blocks as text strings which allow portable, human-readable, 
text-based serialization
-          format that can, for example, be encoded into a QR for dissemination.
+          format that can, for example, be encoded into a QR code for 
dissemination.
           HELLO URLs <bcp14>SHOULD</bcp14> be supported by implementations for 
both import and export
           of <tt>HELLO</tt>s.
         </t>
         <t>
           To discover peers for its routing table, a peer will initiate 
<tt>GetMessage</tt> requests
-          <xref target="p2p_get"/> asking for blocks of type  <tt>HELLO</tt>  
using its own peer address as
-          <tt>QUERY_HASH</tt>.
+          <xref target="p2p_get"/> asking for blocks of type <tt>HELLO</tt> 
using its own peer address as
+          the <em>key</em> provided in the <tt>QUERY_HASH</tt> field of the 
message.
           The <tt>PEER_BF</tt> is initialized and set using the peers own peer 
address as well as the addresses
-          of all currently connected peers.
+          of all currently connected <em>neighbors</em>. <!-- note: we mean 
the identities here! FIX with terminology... -->
           These requests <bcp14>MUST</bcp14> use the <tt>FindApproximate</tt> 
and <tt>DemultiplexEverywhere</tt>
           flags. <tt>FindApproximate</tt> will ensure that other peers will 
reply
           with keys they merely consider close-enough, while 
<tt>DemultiplexEverywhere</tt>
           will cause each peer on the path to respond, which is likely to yield
-          <tt>HELLO</tt> s of peers that are useful somewhere in the routing 
table.
-          The <tt>RECOMMENDED</tt> replication level set in the 
<tt>REPL_LVL</tt> field is 4.
+          <tt>HELLO</tt>s of peers that are useful somewhere in the routing 
table.
+          The <tt>RECOMMENDED</tt> replication level to be set in the 
<tt>REPL_LVL</tt> field is 4.
           The size and format of the result filter is specified in <xref 
target="hello_block"/>.
-          The <tt>XQUERY</tt> is empty.
+          The <tt>XQUERY</tt> <bcp14>MUST</bcp14> be empty.
         </t>
         <t>
           In order to facilitate the above,
-          the Underlay is expected to provide the implementation with one or 
more
+          the underlay is expected to provide the implementation with one or 
more
           addresses signalled through <tt>ADDRESS_ADDED</tt>. Zero addresses 
<bcp14>MAY</bcp14> be
           provided if a peer can only establish outgoing connections and is 
otherwise unreachable.
-          An implementation <bcp14>MUST</bcp14> advertise its addresses 
periodically to its neighbors through <tt>HelloMessage</tt>s.
-          The advertisement interval and expiration should be configurable or 
chosen at the discretion of the implementation based
-          on external factors such as DHCP leases.
+          An implementation <bcp14>MUST</bcp14> advertise its addresses 
periodically to its
+         <em>neighbors</em> through <tt>HelloMessage</tt>s.
+          The advertisement interval and expiration should be configurable or 
chosen at the discretion
+         of the implementation based on external factors such as DHCP leases.
           The specific frequency of advertisements <bcp14>MAY</bcp14> depend 
on available bandwidth,
           the set of already connected neighbors,  the workload of the system 
and other factors which are at the discretion of
           the developer, but <bcp14>SHOULD</bcp14> be a fraction of the 
expiration period.
           Whenever a peer receives such a  <tt>HELLO</tt>  message from 
another peer that is
           already in the routing table, it must cache it as long as that peer 
is in its routing table
           (or until the <tt>HELLO</tt> expires) and serve it in response to
-          GET requests for <tt>HELLO</tt> blocks (see <xref 
target="p2p_get_processing"/>).
+          <tt>GET</tt> requests for <tt>HELLO</tt> blocks (see <xref 
target="p2p_get_processing"/>).
           This behaviour makes it unnecessary to initiate dedicated 
<tt>PutMessages</tt> containing
           <tt>HELLO</tt> blocks by the implementation.
         </t>
@@ -760,9 +761,9 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
         <name>Peer Bloom Filter</name>
         <t>
           As DHT <tt>GetMessage</tt>s and <tt>PutMessage</tt>s traverse a 
random path through the network for the
-          first N hops, it is essential that routing loops are avoided.
-          This peer Bloom filter is constant in size at <tt>L=1024</tt> 
buckets (128 bytes) and
-          <tt>k=16</tt> buckets per element.
+          first <tt>L2NSE</tt> hops, it is essential that routing loops are 
avoided.
+          This peer Bloom filter is constant in size at <tt>L=1024</tt> bits 
(128 bytes) and
+          <tt>k=16</tt> bits set per element.
           The peer Bloom filter is part of the routing metadata in
           messages in order to prevent circular routes and is updated at each 
hop with the hops
           peer identity.
@@ -788,7 +789,7 @@ Connectivity | |Underlay|  |Underlay|  | Underlay | ...
         <t>
           The element <tt>e</tt> is hashed using SHA-512.
           The resulting byte string is interpreted as a string of k=16
-          32-bit integers in network byte order which are used to set and 
check the bucket bits
+          32-bit integers in network byte order which are used to set and 
check the bits
           in <tt>B</tt> using <tt>BF-SET</tt> and <tt>BF-TEST</tt>.
         </t>
         <t>
@@ -2386,7 +2387,7 @@ BEGIN
          <t>
            The RESULT_FILTER for <tt>HELLO</tt> blocks is implemented using a
             Bloom filter following the definition from <xref 
target="bloom_filters"/>
-            and consists of a variable number of buckets <tt>L</tt>.
+            and consists of a variable number of bits <tt>L</tt>.
             <tt>L</tt> depends on the number of connected peers <tt>|E|</tt> 
known to
             the peer creating a <tt>HELLO</tt> block from its own addresses:
            <tt>L</tt> is set to the minimum of
@@ -2407,9 +2408,9 @@ BEGIN
           <t>
             <tt>M</tt> is an identity function and returns the 512-bit XOR 
result unmodified.
             This resulting byte string is interpreted as k=16 32-bit
-            integers in network byte order which are used to set and check the 
bucket bits in
+            integers in network byte order which are used to set and check the 
bits in
             <tt>B</tt> using <tt>BF-SET</tt> and <tt>BF-TEST</tt>.
-            The 32-bit Mutator is prepended to the L-bit Bloom filter bucket 
field  <tt>HELLO_BF</tt> containing <tt>B</tt>
+            The 32-bit Mutator is prepended to the L-bit Bloom filter field 
<tt>HELLO_BF</tt> containing <tt>B</tt>
             to create the result filter for a <tt>HELLO</tt> block:
           </t>
           <figure anchor="hello_rf" title="The HELLO Block Result Filter.">
@@ -2430,7 +2431,7 @@ BEGIN
             </dd>
             <dt>HELLO_BF</dt>
             <dd>
-              The L-bit Bloom filter buckets byte array.
+              The L-bit Bloom filter array.
             </dd>
           </dl>
           <t>
@@ -2856,8 +2857,8 @@ Type    | Name            | References | Description
         a BF is either "no" or "maybe".
       </t>
       <t>
-        Bloom filters are defined as a string of <tt>L</tt> bits called 
"buckets".
-        The buckets are initially always empty, meaning that the bits are set 
to
+        Bloom filters are defined as a string of <tt>L</tt> bits.
+        The bits are initially always empty, meaning that the bits are set to
         zero.
         There are two functions which can be invoked on the Bloom filter "bf":
         BF-SET(bf, e) and BF-TEST(bf, e) where "e" is an element that is to
@@ -2865,9 +2866,9 @@ Type    | Name            | References | Description
       </t>
       <t>
         A mapping function M is used to map each ID of each element from the 
set to a
-        subset of k buckets.
+        subset of k bits.
         In the original proposal by Bloom, M is non-injective and can thus map 
the same
-        element multiple times to the same bucket.
+        element multiple times to the same bit.
         The type of the mapping function can thus be described by the following
         mathematical notation:
       </t>
@@ -2876,9 +2877,9 @@ Type    | Name            | References | Description
         ------------------------------------
         # M: E->B^k
         ------------------------------------
-        # L = Number of buckets
-        # B = 0,1,2,3,4,...L-1 (the buckets)
-        # k = Number of buckets per element
+        # L = Number of bits
+        # B = 0,1,2,3,4,...L-1 (the bits)
+        # k = Number of bits per element
         # E = Set of elements
         ------------------------------------
         Example: L=256, k=3

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.