[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] branch master updated: work on sec 5
|
From: |
gnunet |
|
Subject: |
[lsd0003] branch master updated: work on sec 5 |
|
Date: |
Sat, 12 Jun 2021 23:38:42 +0200 |
This is an automated email from the git hooks/post-receive script.
grothoff pushed a commit to branch master
in repository lsd0003.
The following commit(s) were added to refs/heads/master by this push:
new f3c44bd work on sec 5
f3c44bd is described below
commit f3c44bdac90c96bb64c0539dada96676c5f2b2e3
Author: Christian Grothoff <christian@grothoff.org>
AuthorDate: Sat Jun 12 23:35:59 2021 +0200
work on sec 5
---
draft-summermatter-set-union.xml | 191 +++++++++++++++++++++------------------
1 file changed, 101 insertions(+), 90 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index d8dbb49..5b6dfa7 100644
--- a/draft-summermatter-set-union.xml
+++ b/draft-summermatter-set-union.xml
@@ -880,97 +880,108 @@ hashSum | 0x0101 | 0x5151 | 0x5050 |
0x0000 |
<section anchor="modeofoperation" numbered="true" toc="default">
<name>Mode of Operation</name>
<t>
- The set union protocol uses IBFs and SEs as primitives.
- Depending on the state of the two sets there are different
strategies or operation modes how to efficiently
- determinate missing elements between the two sets.
- </t>
-
- <t>
- The simplest mode is the "full" synchronisation mode. The idea
is that if the difference between the sets of the two
- peers exceeds a certain threshold, the overhead to determine
which elements are different outweighs
- the overhead of sending the complete set. In this case, the
most efficient method can be just to
- exchange the full sets.
+ Depending on the state of the two sets the set union
+ protocol uses different modes of operation to efficiently
+ determinate missing elements between the two sets.
</t>
<t>
- <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/full_state_machine.png";>Link
to the statemachine diagram</eref>
+ The simplest mode is the <em>full synchronisation mode</em>.
+ If the difference between the sets of the two
+ peers exceeds a certain threshold, the overhead to determine
+ which elements are different would outweigh the overhead of
+ simply sending the complete set. Hence, the protocol may
+ determine that the most efficient method is to exchange the full
sets.
</t>
<t>
- The second possibility is that the difference of the sets is
small compared to the set size.
- In this case, an efficient "differential" synchronisation mode
is more efficient. These two possibilities given,
- the first steps of the protocol are used to determine which
mode MUST be used.
+ The second possibility is that the difference between the sets
+ is relatively small compared to the set size.
+ In this case, the <em>differential synchronisation mode</em> is
more efficient.
+ Given these two possibilities, the first steps of the protocol
are used to
+ determine which mode MUST be used.
</t>
-
<t>
- Thus, the set synchronisation protocol always begins with the
following operation mode independent steps.
+ Thus, the set union protocol always begins with the following
operation mode independent steps:
</t>
<t>
- The initiating peer begins in the <strong>Initiating
Connection</strong> state and the receiving peer in the <strong>Expecting
Connection</strong>
- state. The first step for the initiating peer in the protocol
is to send an <em><xref target="messages_operation_request" format="title"
/></em> to the receiving peer and
- transition into the <strong>Expect SE</strong> state. After
receiving the <em><xref target="messages_operation_request" format="title"
/></em> the receiving peer
- transitions to the <strong>Expecting IBF</strong> state and
answers with the
- <em><xref target="messages_se" format="title" /></em> message.
When the initiating peer receives the <em><xref target="messages_se"
format="title" /></em> message,
- it decides with some heuristics which operation mode is likely
more suitable for the estimated set difference and the application-provided
latency-bandwidth tradeoff.
- The detailed tradeoff between the <xref
target="modeofoperation_full-sync" format="title" /> and the <xref
target="modeofoperation_individual-elements" format="title" />
- is explained in the section <xref
target="modeofoperation_combined-mode" format="title" />.
+ The initiating peer begins in the <strong>Initiating
Connection</strong> state and the receiving peer in the <strong>Expecting
Connection</strong>
+ state. The first step for the initiating peer in the protocol is
to send an <em><xref target="messages_operation_request" format="title" /></em>
to the receiving peer and
+ transition into the <strong>Expect SE</strong> state. After
receiving the <em><xref target="messages_operation_request" format="title"
/></em> the receiving peer
+ transitions to the <strong>Expecting IBF</strong> state and
answers with the
+ <em><xref target="messages_se" format="title" /></em> message.
When the initiating peer receives the <em><xref target="messages_se"
format="title" /></em> message,
+ it decides with some heuristics which operation mode is likely
more suitable for the estimated set difference and the application-provided
latency-bandwidth tradeoff.
+ The detailed algorithm used to choose between the <xref
target="modeofoperation_full-sync" format="title" /> and the <xref
target="modeofoperation_individual-elements" format="title" />
+ is explained in the section <xref
target="modeofoperation_combined-mode" format="title" /> below.
</t>
<section anchor="modeofoperation_full-sync" numbered="true"
toc="default">
- <name>Full Synchronisation Mode</name>
- <t>
- When the initiating peer decides to use the full
synchronisation mode and it is better that the other peer sends his set first,
the initiating
- peer sends a <em><xref target="messages_request_full"
format="title" /></em> message, and transitions from <strong>Expecting
SE</strong> to the <strong>Full Receiving</strong> state.
- If it has been determined that it is better that the
initiating peer sends his set first, the initiating peer sends a <em><xref
target="messages_send_full" format="title" /></em> message followed by all
- set elements in <em><xref target="messages_full_element"
format="title" /></em> messages to the other peer, followed by the <em><xref
target="messages_full_done" format="title" /></em> message, and transitions
into the <strong>Full Sending</strong> state.
- </t>
- <t>
- <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/state_machine_full.png";>Link
to the statemachine diagram</eref>
- </t>
- <t><strong>The behavior of the participants the different
state is described below:</strong></t>
- <dl>
- <dt><strong>Expecting IBF:</strong></dt>
- <dd>
- If a peer in the <strong>Expecting IBF</strong> state
receives a <em><xref target="messages_request_full" format="title" /></em>
message from the other peer, the
- peer sends all the elements of his set followed by a
<em><xref target="messages_full_done" format="title" /></em> message to the
other peer, and transitions to the
- <strong>Full Sending</strong> state. If the peer
receives an <em><xref target="messages_send_full" format="title" /></em>
message followed by
- <em><xref target="messages_full_element"
format="title" /></em> messages, the peer processes the element and transitions
to the <strong>Full Receiving</strong> state.
- </dd>
- <dt><strong>Full Sending:</strong></dt>
- <dd>
- While a peer is in <strong>Full Sending</strong> state
the peer expects to continuously receive elements from the other
- peer. As soon as a the <em><xref
target="messages_full_done" format="title" /></em> message is received, the
peer transitions into
- the <strong>Finished</strong> state.
- </dd>
- <dt><strong>Full Receiving: </strong></dt>
- <dd>
- While a peer is in the <strong>Full Receiving</strong>
state, it expects to continuously receive elements from the other
- peer. As soon as a the <em><xref
target="messages_full_done" format="title" /></em> message is received, it sends
- the remaining elements (those it did not receive) from
his set to the other
- peer, followed by a <em><xref
target="messages_full_done" format="title" /></em>.
- After sending the last message, the peer transitions
into the <strong>Finished</strong> state.
- </dd>
- </dl>
+ <name>Full Synchronisation Mode</name>
+ <t>
+ When the initiating peer decides to use the full
synchronisation mode and it is better that the other peer sends his set first,
the initiating
+ peer sends a <em><xref target="messages_request_full"
format="title" /></em> message, and transitions from <strong>Expecting
SE</strong> to the <strong>Full Receiving</strong> state.
+ If it has been determined that it is better that the
initiating peer sends his set first, the initiating peer sends a <em><xref
target="messages_send_full" format="title" /></em> message followed by all
+ set elements in <em><xref target="messages_full_element"
format="title" /></em> messages to the other peer, followed by the <em><xref
target="messages_full_done" format="title" /></em> message, and transitions
into the <strong>Full Sending</strong> state.
+ </t>
+ <t>
+ A state diagram illustrating the state machine used during
full synchronization
+ is provided
+ <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/state_machine_full.png";>here</eref>.
+ </t>
+ <t><strong>The behavior of the participants the different state
is described below:</strong></t>
+ <dl>
+ <dt><strong>Expecting IBF:</strong></dt>
+ <dd>
+ If a peer in the <strong>Expecting IBF</strong> state
receives a <em><xref target="messages_request_full" format="title" /></em>
message from the other peer, the
+ peer sends all the elements of his set followed by a
<em><xref target="messages_full_done" format="title" /></em> message to the
other peer, and transitions to the
+ <strong>Full Sending</strong> state. If the peer receives an
<em><xref target="messages_send_full" format="title" /></em> message followed by
+ <em><xref target="messages_full_element" format="title"
/></em> messages, the peer processes the element and transitions to the
<strong>Full Receiving</strong> state.
+ </dd>
+ <dt><strong>Full Sending:</strong></dt>
+ <dd>
+ While a peer is in <strong>Full Sending</strong> state the
peer expects to continuously receive elements from the other
+ peer. As soon as a the <em><xref target="messages_full_done"
format="title" /></em> message is received, the peer transitions into
+ the <strong>Finished</strong> state.
+ </dd>
+ <dt><strong>Full Receiving: </strong></dt>
+ <dd>
+ While a peer is in the <strong>Full Receiving</strong>
state, it expects to continuously receive elements from the other
+ peer. As soon as a the <em><xref target="messages_full_done"
format="title" /></em> message is received, it sends
+ the remaining elements (those it did not receive) from his
set to the other
+ peer, followed by a <em><xref target="messages_full_done"
format="title" /></em>.
+ After sending the last message, the peer transitions into
the <strong>Finished</strong> state.
+ </dd>
+ </dl>
</section>
<section anchor="modeofoperation_individual-elements"
numbered="true" toc="default">
<name>Differential Synchronisation Mode</name>
<t>
- When the initiating peer in the <strong>Expected
SE</strong> state decides to use the differential synchronisation mode, it
- sends a <em><xref target="messages_ibf" format="title"
/></em> to the receiving peer and transitions into the <strong>Passive
Decoding</strong> state.
+ The message format used by the protocol limits the maximum
message size to
+ 64 kb. Given that L can be large, an IBF will not always fit
within that
+ size limit. To deal with this, larger IBFs are split into
multiple messages.
</t>
<t>
- The receiving peer in the <strong>Expecting IBF</strong>
state receives the
- <em><xref target="messages_ibf" format="title" /></em>
message from
- the initiating peer and transitions into the
<strong>Expecting IBF Last</strong> state when there
- are multiple <em><xref target="messages_ibf"
format="title" /></em> messages to sent,
- when there is just a single <em><xref
target="messages_ibf" format="title" /></em> message the receiving peer
- transitions directly to the <strong>Active
Decoding</strong> state.
+ When the initiating peer in the <strong>Expected SE</strong>
state decides to use the differential synchronisation mode, it
+ sends an IBF, which may
+ consist of several <em><xref target="messages_ibf"
format="title" /></em> messages,
+ to the receiving peer and transitions into the
<strong>Passive Decoding</strong> state.
</t>
<t>
- The peer that is in the <strong>Active Decoding</strong>,
<strong>Finish Closing</strong> or in the <strong>Expecting IBF Last</strong>
- state is called the active peer and the peer that is in
either the <strong>Passive Decoding</strong> or the <strong>Finish
Waiting</strong> state
- is called the passive peer.
+ The receiving peer in the <strong>Expecting IBF</strong>
state receives the
+ first <em><xref target="messages_ibf" format="title" /></em>
message from
+ the initiating peer, and transitions into the
<strong>Expecting IBF Last</strong> state
+ if the IBF was split into multiple <em><xref
target="messages_ibf" format="title" /></em>
+ messages. If there is just a single <em><xref
target="messages_ibf" format="title" /></em>
+ message, the receiving peer
+ transitions directly to the <strong>Active Decoding</strong>
state.
</t>
<t>
- <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/differential_state_machine.png";>Link
to the statemachine diagram</eref>
+ The peer that is in the <strong>Active Decoding</strong>,
<strong>Finish Closing</strong> or in the <strong>Expecting IBF Last</strong>
+ state is called the active peer, and the peer that is in
either the <strong>Passive Decoding</strong> or the <strong>Finish
Waiting</strong> state
+ is called the passive peer.
+ </t>
+ <t>
+ A state diagram illustrating the state machine used during
differential synchronization
+ is provided
+ <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/differential_state_machine.png";>here</eref>.
</t>
<t><strong>The behavior of the participants the different
states is described below:</strong></t>
<dl>
@@ -990,25 +1001,26 @@ hashSum | 0x0101 | 0x5151 | 0x5050 |
0x0000 |
that are missing from the active peer's set.
In this case the passive peer answers with
<em><xref target="messages_offer" format="title" /></em> messages
which contain the SHA-512 hash of the
requested element. If the passive peer does not have an element with
- a matching element ID, it MUST ignore the
inquiry. If multiple elements match the 64 bit element ID, the passive
+ a matching element ID, it MUST ignore the
inquiry (in this case, a bucket was falsely classified as pure, decoding the
IBF will eventually fail, and roles will be swapped). <!-- FIXME: should we not
remember that this happened and FAIL if the other peer sends DONE instead of an
IBF? -->
+ If multiple elements match the 64 bit element
ID, the passive
peer MUST send offers for all of the matching
elements.
</dd>
<dt><em><xref target="messages_demand"
format="title" /></em> message:</dt>
<dd>
The <em><xref target="messages_demand"
format="title" /></em> message
- is received if the active peer requests a
complete element that is missing in the active peers set. If the requested
element is valid
+ is received if the active peer requests a
complete element that is missing in the active peers set in response to an
offer. If the requested element is known and has not yet been transmitted
the passive peer answers with an <em><xref
target="messages_elements" format="title" /></em> message which contains the
full,
application-dependent data of the requested
element. If the passive peer receives a demand for a SHA-512 hash for which
- it has no element, a protocol violation is
detected and the protocol MUST be aborted.
- Implementations MAY strengthen this and forbid
demands without previous matching offers.
+ it has no corresponding element, a protocol
violation is detected and the protocol MUST be aborted.
+ Implementations MUST also abort when facing
demands without previous matching offers or for which the passive peer
previously transmitted the element to the active peer.
</dd>
<dt><em><xref target="messages_offer"
format="title" /></em> message:</dt>
<dd>
The <em><xref target="messages_offer"
format="title" /></em> message
- is received if the active peer has decoded an
element that is present in the active peers set and may be missing in the
+ is received if the active peer has decoded an
element that is present in the active peers set and is likely be missing in the
set of the passive peer. If the SHA-512 hash
of the offer is indeed not a hash of any of the elements from the set of
the passive peer, the passive peer MUST answer
with a <em><xref target="messages_demand" format="title" /></em> message
- for that SHA-512 hash and remember that it
issued this demand. The send demand need to be added to a list with unsatisfied
demands.
+ for that SHA-512 hash and remember that it
issued this demand. The demand thus needs to be added to a list with
unsatisfied demands.
</dd>
<dt><em><xref target="messages_elements"
format="title" /></em> message:</dt>
<dd>
@@ -1016,16 +1028,16 @@ hashSum | 0x0101 | 0x5151 | 0x5050 |
0x0000 |
<em><xref target="messages_demand"
format="title" /></em> for the element has been sent
and the demand is still unsatisfied.
If the element has been demanded the peer
checks the element for validity, removes it from the list
- of pending demands and then saves the element
to the set otherwise the peer
- rejects the element.
+ of pending demands and then saves the element
to the set. Otherwise the peer
+ ignores the element.
</dd>
<dt><em><xref target="messages_ibf" format="title"
/></em> message:</dt>
<dd>
If an <em><xref target="messages_ibf"
format="title" /></em> message is received, this
indicates that decoding of the IBF on the
active site has failed and roles will be swapped.
The receiving passive peer transitions into
the <strong>Expecting IBF Last</strong> state,
- and waits for more <em><xref
target="messages_ibf" format="title" /></em> messages
- or the final <em><xref
target="messages_ibf_last" format="title" /></em> message to be received.
+ and waits for more <em><xref
target="messages_ibf" format="title" /></em> messages.
+ There, once the final <em><xref
target="messages_ibf_last" format="title" /></em> message has been received, it
transitions to <strong>Active Decoding</strong>.
</dd>
<dt><em><xref target="messages_ibf_last"
format="title" /></em> message:</dt>
<dd>
@@ -1052,16 +1064,15 @@ hashSum | 0x0101 | 0x5151 | 0x5050 |
0x0000 |
</t>
<t>
If the IBF decodes a positive (1) pure bucket, the
element is missing on the passive peers site.
- Thus the active peer sends an <em><xref
target="messages_offer" format="title" /></em> to the passive peer.
+ Thus, the active peer sends an <em><xref
target="messages_offer" format="title" /></em> to the passive peer.
A negative (-1) pure bucket indicates that an
element is missing in the active peers set, so the active peer
sends a <em><xref target="messages_inquiry"
format="title" /></em> to the passive peer.
</t>
<t>
- In case the IBF does not successfully decode
anymore, the active peer sends a new IBF to the passive peer
+ In case the IBF does not successfully decode
anymore, the active peer sends a new IBF computed with a different IBF-salt to
the passive peer
and changes into <strong>Passive Decoding</strong>
state. This initiates a role swap.
- To reduce overhead and prevent double transmission
of offers and elements the new IBF is created
- on the new complete set after all demands and
inquiries have been satisfied.
-
+ To reduce overhead and prevent double transmission
of offers and elements, the new IBF is created
+ on the local set after updating it with the all of
the elements that have been successfully demanded. Note that the active peer
MUST NOT wait for all active demands to be satisfied, as demands can fail if a
bucket was falsely classified as pure.
</t>
<t>
As soon as the active peer successfully finished
decoding the IBF, the active peer sends a
@@ -1079,8 +1090,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 |
0x0000 |
the active peer. If a inquiry has been sent and
the offered element is missing in the active
peers set,
the active peer sends a <em><xref
target="messages_demand" format="title" /></em> message to the
- passive peer. The sent demand needs to be
added to a list with unsatisfied demands.
- In case the received offer is for an element
that is already in the set of the peer the offer is ignored.
+ passive peer. The demand needs to be added to
a list of unsatisfied demands.
+ In case the received offer is for an element
that is already in the set of the peer, the offer MUST BE ignored.
</dd>
<dt><em><xref target="messages_demand"
format="title" /></em> message:</dt>
<dd>
@@ -1089,6 +1100,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 |
0x0000 |
the active peer. The active peer satisfies the
demand of the passive peer by sending
<em><xref target="messages_elements"
format="title" /></em> message if a offer request
for the element has been sent.
+ <!-- FIXME: I do not understand. How can this
happen, even with impure buckets? => too late, look at tomorrow! -->
In case the demanded element does not exist in
the
set, there was probably a bucket decoded that
was not pure. Potentially all <em><xref target="messages_offer" format="title"
/></em>
and <em><xref target="messages_demand"
format="title" /></em> messages sent later are invalid.
@@ -3013,9 +3025,8 @@ Type | Name | References |
Description
<section anchor="contributors" numbered="true" toc="default">
<name>Contributors</name>
<t>
- The original GNUnet implementation of the byzantine fault
tolerant set reconciliation
- protocol has mainly been
- written by Florian Dold and Christian Grothoff.
+ The GNUnet implementation of the byzantine fault tolerant set
reconciliation
+ protocol was originally implemented by Florian Dold.
</t>
</section>
</middle>
--
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: work on sec 5,
gnunet <=