commit f3c44bdac90c96bb64c0539dada96676c5f2b2e3
parent fa6c0d634c3d16e70eb57c589b3f32d8248e2f20
Author: Christian Grothoff <christian@grothoff.org>
Date: Sat, 12 Jun 2021 23:35:59 +0200
work on sec 5
Diffstat:
1 file changed, 101 insertions(+), 90 deletions(-)
diff --git 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>
