[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] branch master updated: Added some graphics
|
From: |
gnunet |
|
Subject: |
[lsd0003] branch master updated: Added some graphics |
|
Date: |
Mon, 21 Dec 2020 11:40:30 +0100 |
This is an automated email from the git hooks/post-receive script.
elias-summermatter pushed a commit to branch master
in repository lsd0003.
The following commit(s) were added to refs/heads/master by this push:
new 0a5f335 Added some graphics
0a5f335 is described below
commit 0a5f335a2201319a6e2b6a27e17a6fa8a22dce33
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Mon Dec 21 11:40:01 2020 +0100
Added some graphics
---
draft-summermatter-set-union.xml | 129 ++++++++++++++++++++++++++++++++++++---
1 file changed, 121 insertions(+), 8 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index 18f2248..8d3737b 100644
--- a/draft-summermatter-set-union.xml
+++ b/draft-summermatter-set-union.xml
@@ -143,16 +143,21 @@
<section anchor="ibf_format" numbered="true" toc="default">
<name>Format</name>
<t>
- The storage format of an IBF is a "two-component data
structure" that stores a value
+ The storage format of an IBF is a "two-component data
structure" that stores a hash value
and a signed counter in a bucket. For every bit of the
defined output length of the used hash functions
there is a value and a count stored.
- The count component is increased by one if on the given
bit has been hit by the #### ANSCHAUEN REDUNDANT
- insert operation and is decreased by one if an bit has
been hit by the delete operation. #### ILUSTRATONEN
- If the bucket is pure (|counter| = 1) the value contains
the hash value of an element otherwise in the
- value field is empty (counter= 0) or a XOR product of all
previously written hashes of elements
- (|counter| > 1)
- ### SOME GRAPHIC OF THE FORMAT ###
</t>
+ <figure anchor="figure_ibf_format">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+-------
+ count | COUNTER | COUNTER | COUNTER | COUNTER | C...
+ +-------------+-------------+-------------+-------------+------
+ value | HASH VALUE | HASH VALUE | HASH VALUE | HASH VALUE | H...
+ +-------------+-------------+-------------+-------------+-------
+ ]]></artwork>
+ </figure>
+
</section>
<section anchor="ibv_operations" numbered="true" toc="default">
<name>Operations</name>
@@ -164,6 +169,43 @@
bit positions with a one of the hash output the
counter is increased by one and the value
field is updated with the XOR product of the new hash
and the previously stored value.
</t>
+ <t>
+ In the following example the insert operation for the
element [0101] with the hash 4242 and
+ the element [1100] with the hash 0101 is demonstrated.
+ </t>
+ <t>Empty IBF:</t>
+ <figure anchor="figure_ibf_insert_0">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 0 | 0 | 0 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 0000 | 0000 | 0000 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>Insert first element: [0101] with hash 4242:</t>
+ <figure anchor="figure_ibf_insert_1">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 4242 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>Insert second element: [1100] with hash 0101:</t>
+ <figure anchor="figure_ibf_insert_2">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0101 | 4343 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
</section>
<section anchor="ibv_operations_remove" numbered="true"
toc="default">
<name>Remove Element</name>
@@ -173,6 +215,31 @@
two-component data structure is reduced by one and the
resulting hash is XORed with the value field
and is written to the value field again.
</t>
+ <t>
+ In the following example the insert operation for the
element [1100] with the hash 0101 is demonstrated.
+ </t>
+ <t>IBF with encoded elements:</t>
+ <figure anchor="figure_ibf_remove_0">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0101 | 4343 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>Remove element [1100] with hash 0101 from the IBF:</t>
+ <figure anchor="figure_ibf_remove_1">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 4242 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
</section>
<section anchor="ibv_operations_decode" numbered="true"
toc="default">
<name>Decode IBF</name>
@@ -184,6 +251,52 @@
in the section "Remove Element" from the pure buckets
from the filter creating new pure buckets
until the IBF is completely empty and all elements
have been decoded.
</t>
+ <t>
+ In the following example the successful decoding of an
IBF containing the two elements previously
+ added.
+ </t>
+ <t>
+ IBF with the two encoded elements:
+ </t>
+ <figure anchor="figure_ibf_decode_0">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0101 | 4343 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>
+ In the IBF are two pure buckets to decode (bit-1 and
bit-4) we choose to start with decoding bucket 1,
+ we decode the element with the hash 1010 and we see
that there is a new pure bucket created (bit-2)
+ </t>
+ <figure anchor="figure_ibf_decode_1">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 4242 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>
+ In the IBF only pure buckets are left, we choose to
continue decoding bucket 2 and decode element
+ with the hash 4242. Now the IBF is empty (all buckets
have count 0) that means the IBF has successfully
+ decoded.
+ </t>
+ <figure anchor="figure_ibf_decode_2">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 0 | 0 | 0 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 0000 | 0000 | 0000 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
</section>
<section anchor="ibv_operations_setdiff" numbered="true"
toc="default">
<name>Set difference</name>
@@ -262,7 +375,7 @@
<t>
In full synchronisation mode, if the set of the initiating
peer is bigger than the set of the receiving peer, the initiating ###
Nachrichten und states ander darstellen
- peer sends a "Request Full" message and change from
"Expecting SE" in "Full Receiving" State. ###
Refferenz auf nachrichten & all elements = message type anstat beschreibung
+ peer sends a "Request Full" message and change from
"Expecting SE" in "Full Receiving" State. ###
Refferenz auf nachrichten und all elements = message type anstat beschreibung
In all other cases the initiating peer sends all set
elements to the other peer
followed by the "Full Done" message and changes into "Full
Sending" State.
</t>
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [lsd0003] branch master updated: Added some graphics,
gnunet <=