diff options
author | Christian Grothoff <christian@grothoff.org> | 2020-08-19 13:17:01 +0200 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2020-08-19 13:17:01 +0200 |
commit | 6531e03875f8b3dba0eface2ac8ea195e9a80d86 (patch) | |
tree | 40cb1bc17372f67679d8cc767f8557f6748b4db8 /doc | |
parent | 6c1e93877194aa2c0cbd50a3636a1532dd521e3b (diff) | |
download | gnunet-6531e03875f8b3dba0eface2ac8ea195e9a80d86.tar.gz gnunet-6531e03875f8b3dba0eface2ac8ea195e9a80d86.zip |
break out chapters on SETI and SETUI from SET chapter
Diffstat (limited to 'doc')
-rw-r--r-- | doc/handbook/chapters/developer.texi | 522 |
1 files changed, 520 insertions, 2 deletions
diff --git a/doc/handbook/chapters/developer.texi b/doc/handbook/chapters/developer.texi index 6d8ddd3c2..0ff222f25 100644 --- a/doc/handbook/chapters/developer.texi +++ b/doc/handbook/chapters/developer.texi | |||
@@ -71,6 +71,8 @@ new chapters, sections or insightful comments. | |||
71 | * PEERINFO Subsystem:: | 71 | * PEERINFO Subsystem:: |
72 | * PEERSTORE Subsystem:: | 72 | * PEERSTORE Subsystem:: |
73 | * SET Subsystem:: | 73 | * SET Subsystem:: |
74 | * SETI Subsystem:: | ||
75 | * SETU Subsystem:: | ||
74 | * STATISTICS Subsystem:: | 76 | * STATISTICS Subsystem:: |
75 | * Distributed Hash Table (DHT):: | 77 | * Distributed Hash Table (DHT):: |
76 | * GNU Name System (GNS):: | 78 | * GNU Name System (GNS):: |
@@ -6535,10 +6537,13 @@ destroyed as well. | |||
6535 | @node SET Subsystem | 6537 | @node SET Subsystem |
6536 | @section SET Subsystem | 6538 | @section SET Subsystem |
6537 | 6539 | ||
6538 | 6540 | The SET subsystem is in process of being replaced by the SETU and | |
6541 | SETI subsystems, which provide basically the same functionality, | ||
6542 | just using two different subsystems. SETI and SETU should be used | ||
6543 | for new code. | ||
6539 | 6544 | ||
6540 | The SET service implements efficient set operations between two peers | 6545 | The SET service implements efficient set operations between two peers |
6541 | over a mesh tunnel. | 6546 | over a CADET tunnel. |
6542 | Currently, set union and set intersection are the only supported | 6547 | Currently, set union and set intersection are the only supported |
6543 | operations. Elements of a set consist of an @emph{element type} and | 6548 | operations. Elements of a set consist of an @emph{element type} and |
6544 | arbitrary binary @emph{data}. | 6549 | arbitrary binary @emph{data}. |
@@ -6907,6 +6912,519 @@ All Bloom filter operations use a salt to mingle keys before hashing them | |||
6907 | into buckets, such that future iterations have a fresh chance of | 6912 | into buckets, such that future iterations have a fresh chance of |
6908 | succeeding if they failed due to collisions before. | 6913 | succeeding if they failed due to collisions before. |
6909 | 6914 | ||
6915 | |||
6916 | |||
6917 | |||
6918 | |||
6919 | |||
6920 | |||
6921 | |||
6922 | @cindex SETI Subsystem | ||
6923 | @node SETI Subsystem | ||
6924 | @section SETI Subsystem | ||
6925 | |||
6926 | The SET service implements efficient set intersection between two peers | ||
6927 | over a CADET tunnel. | ||
6928 | Elements of a set consist of an @emph{element type} and | ||
6929 | arbitrary binary @emph{data}. | ||
6930 | The size of an element's data is limited to around 62 KB. | ||
6931 | |||
6932 | @menu | ||
6933 | * Local Sets:: | ||
6934 | * Set Modifications:: | ||
6935 | * Set Operations:: | ||
6936 | * Result Elements:: | ||
6937 | * libgnunetseti:: | ||
6938 | * The SET Client-Service Protocol:: | ||
6939 | * The SET Intersection Peer-to-Peer Protocol:: | ||
6940 | @end menu | ||
6941 | |||
6942 | @node Local Sets | ||
6943 | @subsection Local Sets | ||
6944 | |||
6945 | Sets created by a local client can be modified (by adding additional elements) | ||
6946 | and reused for multiple operations. If elements are to be removed, a fresh | ||
6947 | set must be created by the client. | ||
6948 | |||
6949 | @node Set Modifications | ||
6950 | @subsection Set Modifications | ||
6951 | |||
6952 | Even when set operations are active, one can add elements | ||
6953 | to a set. | ||
6954 | However, these changes will only be visible to operations that have been | ||
6955 | created after the changes have taken place. That is, every set operation | ||
6956 | only sees a snapshot of the set from the time the operation was started. | ||
6957 | This mechanism is @emph{not} implemented by copying the whole set, but by | ||
6958 | attaching @emph{generation information} to each element and operation. | ||
6959 | |||
6960 | @node Set Operations | ||
6961 | @subsection Set Operations | ||
6962 | |||
6963 | Set operations can be started in two ways: Either by accepting an | ||
6964 | operation request from a remote peer, or by requesting a set operation | ||
6965 | from a remote peer. | ||
6966 | Set operations are uniquely identified by the involved @emph{peers}, an | ||
6967 | @emph{application id} and the @emph{operation type}. | ||
6968 | |||
6969 | The client is notified of incoming set operations by @emph{set listeners}. | ||
6970 | A set listener listens for incoming operations of a specific operation | ||
6971 | type and application id. | ||
6972 | Once notified of an incoming set request, the client can accept the set | ||
6973 | request (providing a local set for the operation) or reject it. | ||
6974 | |||
6975 | @node Result Elements | ||
6976 | @subsection Result Elements | ||
6977 | |||
6978 | The SET service has two @emph{result modes} that determine how an | ||
6979 | operation's result set is delivered to the client: | ||
6980 | |||
6981 | @itemize @bullet | ||
6982 | @item @strong{Return intersection.} All elements of set resulting from the set | ||
6983 | intersection are returned to the client. | ||
6984 | @item @strong{Removed Elements.} Only elements that are in the local | ||
6985 | peer's initial set but not in the intersection are returned. | ||
6986 | @end itemize | ||
6987 | |||
6988 | @cindex libgnunetseti | ||
6989 | @node libgnunetseti | ||
6990 | @subsection libgnunetseti | ||
6991 | |||
6992 | @menu | ||
6993 | * Sets:: | ||
6994 | * Listeners:: | ||
6995 | * Operations:: | ||
6996 | * Supplying a Set:: | ||
6997 | * The Result Callback:: | ||
6998 | @end menu | ||
6999 | |||
7000 | @node Sets | ||
7001 | @subsubsection Sets | ||
7002 | |||
7003 | New sets are created with @code{GNUNET_SETI_create}. Only the local peer's | ||
7004 | configuration (as each set has its own client connection) must be provided. | ||
7005 | The set exists until either the client calls @code{GNUNET_SET_destroy} or | ||
7006 | the client's connection to the service is disrupted. | ||
7007 | In the latter case, the client is notified by the return value of | ||
7008 | functions dealing with sets. This return value must always be checked. | ||
7009 | |||
7010 | Elements are added with @code{GNUNET_SET_add_element}. | ||
7011 | |||
7012 | @node Listeners | ||
7013 | @subsubsection Listeners | ||
7014 | |||
7015 | Listeners are created with @code{GNUNET_SET_listen}. Each time time a | ||
7016 | remote peer suggests a set operation with an application id and operation | ||
7017 | type matching a listener, the listener's callback is invoked. | ||
7018 | The client then must synchronously call either @code{GNUNET_SET_accept} | ||
7019 | or @code{GNUNET_SET_reject}. Note that the operation will not be started | ||
7020 | until the client calls @code{GNUNET_SET_commit} | ||
7021 | (see Section "Supplying a Set"). | ||
7022 | |||
7023 | @node Operations | ||
7024 | @subsubsection Operations | ||
7025 | |||
7026 | Operations to be initiated by the local peer are created with | ||
7027 | @code{GNUNET_SET_prepare}. Note that the operation will not be started | ||
7028 | until the client calls @code{GNUNET_SET_commit} | ||
7029 | (see Section "Supplying a Set"). | ||
7030 | |||
7031 | @node Supplying a Set | ||
7032 | @subsubsection Supplying a Set | ||
7033 | |||
7034 | To create symmetry between the two ways of starting a set operation | ||
7035 | (accepting and initiating it), the operation handles returned by | ||
7036 | @code{GNUNET_SET_accept} and @code{GNUNET_SET_prepare} do not yet have a | ||
7037 | set to operate on, thus they can not do any work yet. | ||
7038 | |||
7039 | The client must call @code{GNUNET_SET_commit} to specify a set to use for | ||
7040 | an operation. @code{GNUNET_SET_commit} may only be called once per set | ||
7041 | operation. | ||
7042 | |||
7043 | @node The Result Callback | ||
7044 | @subsubsection The Result Callback | ||
7045 | |||
7046 | Clients must specify both a result mode and a result callback with | ||
7047 | @code{GNUNET_SET_accept} and @code{GNUNET_SET_prepare}. The result | ||
7048 | callback with a status indicating either that an element was received, or | ||
7049 | the operation failed or succeeded. | ||
7050 | The interpretation of the received element depends on the result mode. | ||
7051 | The callback needs to know which result mode it is used in, as the | ||
7052 | arguments do not indicate if an element is part of the full result set, | ||
7053 | or if it is in the difference between the original set and the final set. | ||
7054 | |||
7055 | @node The SETI Client-Service Protocol | ||
7056 | @subsection The SETI Client-Service Protocol | ||
7057 | |||
7058 | @menu | ||
7059 | * Creating Sets:: | ||
7060 | * Listeners2:: | ||
7061 | * Initiating Operations:: | ||
7062 | * Modifying Sets:: | ||
7063 | * Results and Operation Status:: | ||
7064 | @end menu | ||
7065 | |||
7066 | @node Creating Sets | ||
7067 | @subsubsection Creating Sets | ||
7068 | |||
7069 | For each set of a client, there exists a client connection to the service. | ||
7070 | Sets are created by sending the @code{GNUNET_SERVICE_SETI_CREATE} message | ||
7071 | over a new client connection. Multiple operations for one set are | ||
7072 | multiplexed over one client connection, using a request id supplied by | ||
7073 | the client. | ||
7074 | |||
7075 | @node Listeners2 | ||
7076 | @subsubsection Listeners2 | ||
7077 | |||
7078 | |||
7079 | |||
7080 | Each listener also requires a seperate client connection. By sending the | ||
7081 | @code{GNUNET_SERVICE_SETI_LISTEN} message, the client notifies the service | ||
7082 | of the application id and operation type it is interested in. A client | ||
7083 | rejects an incoming request by sending @code{GNUNET_SERVICE_SETI_REJECT} | ||
7084 | on the listener's client connection. | ||
7085 | In contrast, when accepting an incoming request, a | ||
7086 | @code{GNUNET_SERVICE_SETI_ACCEPT} message must be sent over the@ set that | ||
7087 | is supplied for the set operation. | ||
7088 | |||
7089 | @node Initiating Operations | ||
7090 | @subsubsection Initiating Operations | ||
7091 | |||
7092 | Operations with remote peers are initiated by sending a | ||
7093 | @code{GNUNET_SERVICE_SETI_EVALUATE} message to the service. The@ client | ||
7094 | connection that this message is sent by determines the set to use. | ||
7095 | |||
7096 | @node Modifying Sets | ||
7097 | @subsubsection Modifying Sets | ||
7098 | |||
7099 | Sets are modified with the @code{GNUNET_SERVICE_SETI_ADD} message. | ||
7100 | |||
7101 | |||
7102 | @c %@menu | ||
7103 | @c %* Results and Operation Status:: | ||
7104 | @c %* Iterating Sets:: | ||
7105 | @c %@end menu | ||
7106 | |||
7107 | @node Results and Operation Status | ||
7108 | @subsubsection Results and Operation Status | ||
7109 | |||
7110 | The service notifies the client of result elements and success/failure of | ||
7111 | a set operation with the @code{GNUNET_SERVICE_SETI_RESULT} message. | ||
7112 | |||
7113 | @node The SET Intersection Peer-to-Peer Protocol | ||
7114 | @subsection The SET Intersection Peer-to-Peer Protocol | ||
7115 | |||
7116 | The intersection protocol operates over CADET and starts with a | ||
7117 | GNUNET_MESSAGE_TYPE_SETI_P2P_OPERATION_REQUEST being sent by the peer | ||
7118 | initiating the operation to the peer listening for inbound requests. | ||
7119 | It includes the number of elements of the initiating peer, which is used | ||
7120 | to decide which side will send a Bloom filter first. | ||
7121 | |||
7122 | The listening peer checks if the operation type and application | ||
7123 | identifier are acceptable for its current state. | ||
7124 | If not, it responds with a GNUNET_MESSAGE_TYPE_SETI_RESULT and a status of | ||
7125 | GNUNET_SETI_STATUS_FAILURE (and terminates the CADET channel). | ||
7126 | |||
7127 | If the application accepts the request, the listener sends back a | ||
7128 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} if it has | ||
7129 | more elements in the set than the client. | ||
7130 | Otherwise, it immediately starts with the Bloom filter exchange. | ||
7131 | If the initiator receives a | ||
7132 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} response, | ||
7133 | it beings the Bloom filter exchange, unless the set size is indicated to | ||
7134 | be zero, in which case the intersection is considered finished after | ||
7135 | just the initial handshake. | ||
7136 | |||
7137 | |||
7138 | @menu | ||
7139 | * The Bloom filter exchange:: | ||
7140 | * Salt:: | ||
7141 | @end menu | ||
7142 | |||
7143 | @node The Bloom filter exchange | ||
7144 | @subsubsection The Bloom filter exchange | ||
7145 | |||
7146 | In this phase, each peer transmits a Bloom filter over the remaining | ||
7147 | keys of the local set to the other peer using a | ||
7148 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_BF} message. This | ||
7149 | message additionally includes the number of elements left in the sender's | ||
7150 | set, as well as the XOR over all of the keys in that set. | ||
7151 | |||
7152 | The number of bits 'k' set per element in the Bloom filter is calculated | ||
7153 | based on the relative size of the two sets. | ||
7154 | Furthermore, the size of the Bloom filter is calculated based on 'k' and | ||
7155 | the number of elements in the set to maximize the amount of data filtered | ||
7156 | per byte transmitted on the wire (while avoiding an excessively high | ||
7157 | number of iterations). | ||
7158 | |||
7159 | The receiver of the message removes all elements from its local set that | ||
7160 | do not pass the Bloom filter test. | ||
7161 | It then checks if the set size of the sender and the XOR over the keys | ||
7162 | match what is left of its own set. If they do, it sends a | ||
7163 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_DONE} back to indicate | ||
7164 | that the latest set is the final result. | ||
7165 | Otherwise, the receiver starts another Bloom filter exchange, except | ||
7166 | this time as the sender. | ||
7167 | |||
7168 | @node Salt | ||
7169 | @subsubsection Salt | ||
7170 | |||
7171 | Bloomfilter operations are probabilistic: With some non-zero probability | ||
7172 | the test may incorrectly say an element is in the set, even though it is | ||
7173 | not. | ||
7174 | |||
7175 | To mitigate this problem, the intersection protocol iterates exchanging | ||
7176 | Bloom filters using a different random 32-bit salt in each iteration (the | ||
7177 | salt is also included in the message). | ||
7178 | With different salts, set operations may fail for different elements. | ||
7179 | Merging the results from the executions, the probability of failure drops | ||
7180 | to zero. | ||
7181 | |||
7182 | The iterations terminate once both peers have established that they have | ||
7183 | sets of the same size, and where the XOR over all keys computes the same | ||
7184 | 512-bit value (leaving a failure probability of 2-511). | ||
7185 | |||
7186 | |||
7187 | @cindex SETU Subsystem | ||
7188 | @node SETU Subsystem | ||
7189 | @section SETU Subsystem | ||
7190 | |||
7191 | The SETU service implements efficient set union operations between two peers | ||
7192 | over a CADET tunnel. Elements of a set consist of an @emph{element type} and | ||
7193 | arbitrary binary @emph{data}. The size of an element's data is limited to | ||
7194 | around 62 KB. | ||
7195 | |||
7196 | @menu | ||
7197 | * Local Sets:: | ||
7198 | * Set Modifications:: | ||
7199 | * Set Operations:: | ||
7200 | * Result Elements:: | ||
7201 | * libgnunetset:: | ||
7202 | * The SET Client-Service Protocol:: | ||
7203 | * The SET Intersection Peer-to-Peer Protocol:: | ||
7204 | * The SET Union Peer-to-Peer Protocol:: | ||
7205 | @end menu | ||
7206 | |||
7207 | @node Local Sets | ||
7208 | @subsection Local Sets | ||
7209 | |||
7210 | Sets created by a local client can be modified (by adding additional elements) | ||
7211 | and reused for multiple operations. If elements are to be removed, a fresh | ||
7212 | set must be created by the client. | ||
7213 | |||
7214 | @node Set Modifications | ||
7215 | @subsection Set Modifications | ||
7216 | |||
7217 | Even when set operations are active, one can add elements | ||
7218 | to a set. | ||
7219 | However, these changes will only be visible to operations that have been | ||
7220 | created after the changes have taken place. That is, every set operation | ||
7221 | only sees a snapshot of the set from the time the operation was started. | ||
7222 | This mechanism is @emph{not} implemented by copying the whole set, but by | ||
7223 | attaching @emph{generation information} to each element and operation. | ||
7224 | |||
7225 | @node Set Operations | ||
7226 | @subsection Set Operations | ||
7227 | |||
7228 | Set operations can be started in two ways: Either by accepting an | ||
7229 | operation request from a remote peer, or by requesting a set operation | ||
7230 | from a remote peer. | ||
7231 | Set operations are uniquely identified by the involved @emph{peers}, an | ||
7232 | @emph{application id} and the @emph{operation type}. | ||
7233 | |||
7234 | The client is notified of incoming set operations by @emph{set listeners}. | ||
7235 | A set listener listens for incoming operations of a specific operation | ||
7236 | type and application id. | ||
7237 | Once notified of an incoming set request, the client can accept the set | ||
7238 | request (providing a local set for the operation) or reject it. | ||
7239 | |||
7240 | @node Result Elements | ||
7241 | @subsection Result Elements | ||
7242 | |||
7243 | The SET service has three @emph{result modes} that determine how an | ||
7244 | operation's result set is delivered to the client: | ||
7245 | |||
7246 | @itemize @bullet | ||
7247 | @item @strong{Locally added Elements.} Elements that are in the union | ||
7248 | but not already in the local peer's set are returned. | ||
7249 | @item @strong{Remote added Elements.} Additionally, notify the client | ||
7250 | if the remote peer lacked some elements and thus also return to the | ||
7251 | local client those elements that we are sending to the remote peer to | ||
7252 | be added to its union. Obtaining these elements requires setting | ||
7253 | the @code{GNUNET_SETU_OPTION_SYMMETRIC} option. | ||
7254 | @end itemize | ||
7255 | |||
7256 | @cindex libgnunetsetu | ||
7257 | @node libgnunetsetu | ||
7258 | @subsection libgnunetsetu | ||
7259 | |||
7260 | @menu | ||
7261 | * Sets:: | ||
7262 | * Listeners:: | ||
7263 | * Operations:: | ||
7264 | * Supplying a Set:: | ||
7265 | * The Result Callback:: | ||
7266 | @end menu | ||
7267 | |||
7268 | @node Sets | ||
7269 | @subsubsection Sets | ||
7270 | |||
7271 | New sets are created with @code{GNUNET_SETU_create}. Only the local peer's | ||
7272 | configuration (as each set has its own client connection) must be provided. | ||
7273 | The set exists until either the client calls @code{GNUNET_SETU_destroy} or | ||
7274 | the client's connection to the service is disrupted. | ||
7275 | In the latter case, the client is notified by the return value of | ||
7276 | functions dealing with sets. This return value must always be checked. | ||
7277 | |||
7278 | Elements are added with @code{GNUNET_SETU_add_element}. | ||
7279 | |||
7280 | @node Listeners | ||
7281 | @subsubsection Listeners | ||
7282 | |||
7283 | Listeners are created with @code{GNUNET_SETU_listen}. Each time time a | ||
7284 | remote peer suggests a set operation with an application id and operation | ||
7285 | type matching a listener, the listener's callback is invoked. | ||
7286 | The client then must synchronously call either @code{GNUNET_SETU_accept} | ||
7287 | or @code{GNUNET_SETU_reject}. Note that the operation will not be started | ||
7288 | until the client calls @code{GNUNET_SETU_commit} | ||
7289 | (see Section "Supplying a Set"). | ||
7290 | |||
7291 | @node Operations | ||
7292 | @subsubsection Operations | ||
7293 | |||
7294 | Operations to be initiated by the local peer are created with | ||
7295 | @code{GNUNET_SETU_prepare}. Note that the operation will not be started | ||
7296 | until the client calls @code{GNUNET_SETU_commit} | ||
7297 | (see Section "Supplying a Set"). | ||
7298 | |||
7299 | @node Supplying a Set | ||
7300 | @subsubsection Supplying a Set | ||
7301 | |||
7302 | To create symmetry between the two ways of starting a set operation | ||
7303 | (accepting and initiating it), the operation handles returned by | ||
7304 | @code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare} do not yet have a | ||
7305 | set to operate on, thus they can not do any work yet. | ||
7306 | |||
7307 | The client must call @code{GNUNET_SETU_commit} to specify a set to use for | ||
7308 | an operation. @code{GNUNET_SETU_commit} may only be called once per set | ||
7309 | operation. | ||
7310 | |||
7311 | @node The Result Callback | ||
7312 | @subsubsection The Result Callback | ||
7313 | |||
7314 | Clients must specify both a result mode and a result callback with | ||
7315 | @code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare}. The result | ||
7316 | callback with a status indicating either that an element was received, | ||
7317 | transmitted to the other peer (if this information was requested), or | ||
7318 | if the operation failed or ultimately succeeded. | ||
7319 | |||
7320 | @node The SETU Client-Service Protocol | ||
7321 | @subsection The SETU Client-Service Protocol | ||
7322 | |||
7323 | @menu | ||
7324 | * Creating Sets:: | ||
7325 | * Listeners2:: | ||
7326 | * Initiating Operations:: | ||
7327 | * Modifying Sets:: | ||
7328 | * Results and Operation Status:: | ||
7329 | * Iterating Sets:: | ||
7330 | @end menu | ||
7331 | |||
7332 | @node Creating Sets | ||
7333 | @subsubsection Creating Sets | ||
7334 | |||
7335 | For each set of a client, there exists a client connection to the service. | ||
7336 | Sets are created by sending the @code{GNUNET_SERVICE_SETU_CREATE} message | ||
7337 | over a new client connection. Multiple operations for one set are | ||
7338 | multiplexed over one client connection, using a request id supplied by | ||
7339 | the client. | ||
7340 | |||
7341 | @node Listeners2 | ||
7342 | @subsubsection Listeners2 | ||
7343 | |||
7344 | Each listener also requires a seperate client connection. By sending the | ||
7345 | @code{GNUNET_SERVICE_SETU_LISTEN} message, the client notifies the service | ||
7346 | of the application id and operation type it is interested in. A client | ||
7347 | rejects an incoming request by sending @code{GNUNET_SERVICE_SETU_REJECT} | ||
7348 | on the listener's client connection. | ||
7349 | In contrast, when accepting an incoming request, a | ||
7350 | @code{GNUNET_SERVICE_SETU_ACCEPT} message must be sent over the@ set that | ||
7351 | is supplied for the set operation. | ||
7352 | |||
7353 | @node Initiating Operations | ||
7354 | @subsubsection Initiating Operations | ||
7355 | |||
7356 | |||
7357 | |||
7358 | Operations with remote peers are initiated by sending a | ||
7359 | @code{GNUNET_SERVICE_SETU_EVALUATE} message to the service. The@ client | ||
7360 | connection that this message is sent by determines the set to use. | ||
7361 | |||
7362 | @node Modifying Sets | ||
7363 | @subsubsection Modifying Sets | ||
7364 | |||
7365 | |||
7366 | |||
7367 | Sets are modified with the @code{GNUNET_SERVICE_SETU_ADD} message. | ||
7368 | |||
7369 | |||
7370 | @c %@menu | ||
7371 | @c %* Results and Operation Status:: | ||
7372 | @c %* Iterating Sets:: | ||
7373 | @c %@end menu | ||
7374 | |||
7375 | @node Results and Operation Status | ||
7376 | @subsubsection Results and Operation Status | ||
7377 | |||
7378 | The service notifies the client of result elements and success/failure of | ||
7379 | a set operation with the @code{GNUNET_SERVICE_SETU_RESULT} message. | ||
7380 | |||
7381 | |||
7382 | @node The SET Union Peer-to-Peer Protocol | ||
7383 | @subsection The SET Union Peer-to-Peer Protocol | ||
7384 | |||
7385 | |||
7386 | The SET union protocol is based on Eppstein's efficient set reconciliation | ||
7387 | without prior context. You should read this paper first if you want to | ||
7388 | understand the protocol. | ||
7389 | |||
7390 | The union protocol operates over CADET and starts with a | ||
7391 | GNUNET_MESSAGE_TYPE_SETU_P2P_OPERATION_REQUEST being sent by the peer | ||
7392 | initiating the operation to the peer listening for inbound requests. | ||
7393 | It includes the number of elements of the initiating peer, which is | ||
7394 | currently not used. | ||
7395 | |||
7396 | The listening peer checks if the operation type and application | ||
7397 | identifier are acceptable for its current state. If not, it responds with | ||
7398 | a @code{GNUNET_MESSAGE_TYPE_SETU_RESULT} and a status of | ||
7399 | @code{GNUNET_SETU_STATUS_FAILURE} (and terminates the CADET channel). | ||
7400 | |||
7401 | If the application accepts the request, it sends back a strata estimator | ||
7402 | using a message of type GNUNET_MESSAGE_TYPE_SETU_P2P_SE. The | ||
7403 | initiator evaluates the strata estimator and initiates the exchange of | ||
7404 | invertible Bloom filters, sending a GNUNET_MESSAGE_TYPE_SETU_P2P_IBF. | ||
7405 | |||
7406 | During the IBF exchange, if the receiver cannot invert the Bloom filter or | ||
7407 | detects a cycle, it sends a larger IBF in response (up to a defined | ||
7408 | maximum limit; if that limit is reached, the operation fails). | ||
7409 | Elements decoded while processing the IBF are transmitted to the other | ||
7410 | peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS, or requested from the | ||
7411 | other peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS messages, | ||
7412 | depending on the sign observed during decoding of the IBF. | ||
7413 | Peers respond to a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS message | ||
7414 | with the respective element in a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS | ||
7415 | message. If the IBF fully decodes, the peer responds with a | ||
7416 | GNUNET_MESSAGE_TYPE_SETU_P2P_DONE message instead of another | ||
7417 | GNUNET_MESSAGE_TYPE_SETU_P2P_IBF. | ||
7418 | |||
7419 | All Bloom filter operations use a salt to mingle keys before hashing them | ||
7420 | into buckets, such that future iterations have a fresh chance of | ||
7421 | succeeding if they failed due to collisions before. | ||
7422 | |||
7423 | |||
7424 | |||
7425 | |||
7426 | |||
7427 | |||
6910 | @cindex STATISTICS Subsystem | 7428 | @cindex STATISTICS Subsystem |
6911 | @node STATISTICS Subsystem | 7429 | @node STATISTICS Subsystem |
6912 | @section STATISTICS Subsystem | 7430 | @section STATISTICS Subsystem |