diff options
Diffstat (limited to 'doc/handbook/chapters/developer.texi')
-rw-r--r-- | doc/handbook/chapters/developer.texi | 516 |
1 files changed, 514 insertions, 2 deletions
diff --git a/doc/handbook/chapters/developer.texi b/doc/handbook/chapters/developer.texi index 6d8ddd3c2..369e5327c 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,513 @@ 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 | * Intersection Sets:: | ||
6934 | * Set Intersection Modifications:: | ||
6935 | * Set Intersection Operations:: | ||
6936 | * Intersection Result Elements:: | ||
6937 | * libgnunetseti:: | ||
6938 | * The SETI Client-Service Protocol:: | ||
6939 | * The SETI Intersection Peer-to-Peer Protocol:: | ||
6940 | @end menu | ||
6941 | |||
6942 | @node Intersection Sets | ||
6943 | @subsection Intersection 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 Intersection Modifications | ||
6950 | @subsection Set Intersection 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 Intersection Operations | ||
6961 | @subsection Set Intersection 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 Intersection Result Elements | ||
6976 | @subsection Intersection 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 | * Intersection Set API:: | ||
6994 | * Intersection Listeners:: | ||
6995 | * Intersection Operations:: | ||
6996 | * Supplying a Set for Intersection:: | ||
6997 | * The Intersection Result Callback:: | ||
6998 | @end menu | ||
6999 | |||
7000 | @node Intersection Set API | ||
7001 | @subsubsection Intersection Set API | ||
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 Intersection Listeners | ||
7013 | @subsubsection Intersection 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 Intersection Operations | ||
7024 | @subsubsection Intersection 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 for Intersection | ||
7032 | @subsubsection Supplying a Set for Intersection | ||
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 Intersection Result Callback | ||
7044 | @subsubsection The Intersection 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 Intersection Sets:: | ||
7060 | * Listeners for Intersection:: | ||
7061 | * Initiating Intersection Operations:: | ||
7062 | * Modifying Intersection Sets:: | ||
7063 | * Intersection Results and Operation Status:: | ||
7064 | @end menu | ||
7065 | |||
7066 | @node Creating Intersection Sets | ||
7067 | @subsubsection Creating Intersection 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 Listeners for Intersection | ||
7076 | @subsubsection Listeners for Intersection | ||
7077 | |||
7078 | Each listener also requires a seperate client connection. By sending the | ||
7079 | @code{GNUNET_SERVICE_SETI_LISTEN} message, the client notifies the service | ||
7080 | of the application id and operation type it is interested in. A client | ||
7081 | rejects an incoming request by sending @code{GNUNET_SERVICE_SETI_REJECT} | ||
7082 | on the listener's client connection. | ||
7083 | In contrast, when accepting an incoming request, a | ||
7084 | @code{GNUNET_SERVICE_SETI_ACCEPT} message must be sent over the@ set that | ||
7085 | is supplied for the set operation. | ||
7086 | |||
7087 | @node Initiating Intersection Operations | ||
7088 | @subsubsection Initiating Intersection Operations | ||
7089 | |||
7090 | Operations with remote peers are initiated by sending a | ||
7091 | @code{GNUNET_SERVICE_SETI_EVALUATE} message to the service. The@ client | ||
7092 | connection that this message is sent by determines the set to use. | ||
7093 | |||
7094 | @node Modifying Intersection Sets | ||
7095 | @subsubsection Modifying Intersection Sets | ||
7096 | |||
7097 | Sets are modified with the @code{GNUNET_SERVICE_SETI_ADD} message. | ||
7098 | |||
7099 | |||
7100 | @c %@menu | ||
7101 | @c %* Results and Operation Status:: | ||
7102 | @c %* Iterating Sets:: | ||
7103 | @c %@end menu | ||
7104 | |||
7105 | @node Intersection Results and Operation Status | ||
7106 | @subsubsection Intersection Results and Operation Status | ||
7107 | |||
7108 | The service notifies the client of result elements and success/failure of | ||
7109 | a set operation with the @code{GNUNET_SERVICE_SETI_RESULT} message. | ||
7110 | |||
7111 | @node The SETI Intersection Peer-to-Peer Protocol | ||
7112 | @subsection The SETI Intersection Peer-to-Peer Protocol | ||
7113 | |||
7114 | The intersection protocol operates over CADET and starts with a | ||
7115 | GNUNET_MESSAGE_TYPE_SETI_P2P_OPERATION_REQUEST being sent by the peer | ||
7116 | initiating the operation to the peer listening for inbound requests. | ||
7117 | It includes the number of elements of the initiating peer, which is used | ||
7118 | to decide which side will send a Bloom filter first. | ||
7119 | |||
7120 | The listening peer checks if the operation type and application | ||
7121 | identifier are acceptable for its current state. | ||
7122 | If not, it responds with a GNUNET_MESSAGE_TYPE_SETI_RESULT and a status of | ||
7123 | GNUNET_SETI_STATUS_FAILURE (and terminates the CADET channel). | ||
7124 | |||
7125 | If the application accepts the request, the listener sends back a | ||
7126 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} if it has | ||
7127 | more elements in the set than the client. | ||
7128 | Otherwise, it immediately starts with the Bloom filter exchange. | ||
7129 | If the initiator receives a | ||
7130 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} response, | ||
7131 | it beings the Bloom filter exchange, unless the set size is indicated to | ||
7132 | be zero, in which case the intersection is considered finished after | ||
7133 | just the initial handshake. | ||
7134 | |||
7135 | |||
7136 | @menu | ||
7137 | * The Bloom filter exchange in SETI:: | ||
7138 | * Intersection Salt:: | ||
7139 | @end menu | ||
7140 | |||
7141 | @node The Bloom filter exchange in SETI | ||
7142 | @subsubsection The Bloom filter exchange in SETI | ||
7143 | |||
7144 | In this phase, each peer transmits a Bloom filter over the remaining | ||
7145 | keys of the local set to the other peer using a | ||
7146 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_BF} message. This | ||
7147 | message additionally includes the number of elements left in the sender's | ||
7148 | set, as well as the XOR over all of the keys in that set. | ||
7149 | |||
7150 | The number of bits 'k' set per element in the Bloom filter is calculated | ||
7151 | based on the relative size of the two sets. | ||
7152 | Furthermore, the size of the Bloom filter is calculated based on 'k' and | ||
7153 | the number of elements in the set to maximize the amount of data filtered | ||
7154 | per byte transmitted on the wire (while avoiding an excessively high | ||
7155 | number of iterations). | ||
7156 | |||
7157 | The receiver of the message removes all elements from its local set that | ||
7158 | do not pass the Bloom filter test. | ||
7159 | It then checks if the set size of the sender and the XOR over the keys | ||
7160 | match what is left of its own set. If they do, it sends a | ||
7161 | @code{GNUNET_MESSAGE_TYPE_SETI_P2P_DONE} back to indicate | ||
7162 | that the latest set is the final result. | ||
7163 | Otherwise, the receiver starts another Bloom filter exchange, except | ||
7164 | this time as the sender. | ||
7165 | |||
7166 | @node Intersection Salt | ||
7167 | @subsubsection Intersection Salt | ||
7168 | |||
7169 | Bloom filter operations are probabilistic: With some non-zero probability | ||
7170 | the test may incorrectly say an element is in the set, even though it is | ||
7171 | not. | ||
7172 | |||
7173 | To mitigate this problem, the intersection protocol iterates exchanging | ||
7174 | Bloom filters using a different random 32-bit salt in each iteration (the | ||
7175 | salt is also included in the message). | ||
7176 | With different salts, set operations may fail for different elements. | ||
7177 | Merging the results from the executions, the probability of failure drops | ||
7178 | to zero. | ||
7179 | |||
7180 | The iterations terminate once both peers have established that they have | ||
7181 | sets of the same size, and where the XOR over all keys computes the same | ||
7182 | 512-bit value (leaving a failure probability of 2-511). | ||
7183 | |||
7184 | |||
7185 | @cindex SETU Subsystem | ||
7186 | @node SETU Subsystem | ||
7187 | @section SETU Subsystem | ||
7188 | |||
7189 | The SETU service implements efficient set union operations between two peers | ||
7190 | over a CADET tunnel. Elements of a set consist of an @emph{element type} and | ||
7191 | arbitrary binary @emph{data}. The size of an element's data is limited to | ||
7192 | around 62 KB. | ||
7193 | |||
7194 | @menu | ||
7195 | * Union Sets:: | ||
7196 | * Set Union Modifications:: | ||
7197 | * Set Union Operations:: | ||
7198 | * Union Result Elements:: | ||
7199 | * libgnunetsetu:: | ||
7200 | * The SETU Client-Service Protocol:: | ||
7201 | * The SETU Union Peer-to-Peer Protocol:: | ||
7202 | @end menu | ||
7203 | |||
7204 | @node Union Sets | ||
7205 | @subsection Union Sets | ||
7206 | |||
7207 | Sets created by a local client can be modified (by adding additional elements) | ||
7208 | and reused for multiple operations. If elements are to be removed, a fresh | ||
7209 | set must be created by the client. | ||
7210 | |||
7211 | @node Set Union Modifications | ||
7212 | @subsection Set Union Modifications | ||
7213 | |||
7214 | Even when set operations are active, one can add elements | ||
7215 | to a set. | ||
7216 | However, these changes will only be visible to operations that have been | ||
7217 | created after the changes have taken place. That is, every set operation | ||
7218 | only sees a snapshot of the set from the time the operation was started. | ||
7219 | This mechanism is @emph{not} implemented by copying the whole set, but by | ||
7220 | attaching @emph{generation information} to each element and operation. | ||
7221 | |||
7222 | @node Set Union Operations | ||
7223 | @subsection Set Union Operations | ||
7224 | |||
7225 | Set operations can be started in two ways: Either by accepting an | ||
7226 | operation request from a remote peer, or by requesting a set operation | ||
7227 | from a remote peer. | ||
7228 | Set operations are uniquely identified by the involved @emph{peers}, an | ||
7229 | @emph{application id} and the @emph{operation type}. | ||
7230 | |||
7231 | The client is notified of incoming set operations by @emph{set listeners}. | ||
7232 | A set listener listens for incoming operations of a specific operation | ||
7233 | type and application id. | ||
7234 | Once notified of an incoming set request, the client can accept the set | ||
7235 | request (providing a local set for the operation) or reject it. | ||
7236 | |||
7237 | @node Union Result Elements | ||
7238 | @subsection Union Result Elements | ||
7239 | |||
7240 | The SET service has three @emph{result modes} that determine how an | ||
7241 | operation's result set is delivered to the client: | ||
7242 | |||
7243 | @itemize @bullet | ||
7244 | @item @strong{Locally added Elements.} Elements that are in the union | ||
7245 | but not already in the local peer's set are returned. | ||
7246 | @item @strong{Remote added Elements.} Additionally, notify the client | ||
7247 | if the remote peer lacked some elements and thus also return to the | ||
7248 | local client those elements that we are sending to the remote peer to | ||
7249 | be added to its union. Obtaining these elements requires setting | ||
7250 | the @code{GNUNET_SETU_OPTION_SYMMETRIC} option. | ||
7251 | @end itemize | ||
7252 | |||
7253 | @cindex libgnunetsetu | ||
7254 | @node libgnunetsetu | ||
7255 | @subsection libgnunetsetu | ||
7256 | |||
7257 | @menu | ||
7258 | * Union Set API:: | ||
7259 | * Union Listeners:: | ||
7260 | * Union Operations:: | ||
7261 | * Supplying a Set for Union:: | ||
7262 | * The Union Result Callback:: | ||
7263 | @end menu | ||
7264 | |||
7265 | @node Union Set API | ||
7266 | @subsubsection Union Set API | ||
7267 | |||
7268 | New sets are created with @code{GNUNET_SETU_create}. Only the local peer's | ||
7269 | configuration (as each set has its own client connection) must be provided. | ||
7270 | The set exists until either the client calls @code{GNUNET_SETU_destroy} or | ||
7271 | the client's connection to the service is disrupted. | ||
7272 | In the latter case, the client is notified by the return value of | ||
7273 | functions dealing with sets. This return value must always be checked. | ||
7274 | |||
7275 | Elements are added with @code{GNUNET_SETU_add_element}. | ||
7276 | |||
7277 | @node Union Listeners | ||
7278 | @subsubsection Union Listeners | ||
7279 | |||
7280 | Listeners are created with @code{GNUNET_SETU_listen}. Each time time a | ||
7281 | remote peer suggests a set operation with an application id and operation | ||
7282 | type matching a listener, the listener's callback is invoked. | ||
7283 | The client then must synchronously call either @code{GNUNET_SETU_accept} | ||
7284 | or @code{GNUNET_SETU_reject}. Note that the operation will not be started | ||
7285 | until the client calls @code{GNUNET_SETU_commit} | ||
7286 | (see Section "Supplying a Set"). | ||
7287 | |||
7288 | @node Union Operations | ||
7289 | @subsubsection Union Operations | ||
7290 | |||
7291 | Operations to be initiated by the local peer are created with | ||
7292 | @code{GNUNET_SETU_prepare}. Note that the operation will not be started | ||
7293 | until the client calls @code{GNUNET_SETU_commit} | ||
7294 | (see Section "Supplying a Set"). | ||
7295 | |||
7296 | @node Supplying a Set for Union | ||
7297 | @subsubsection Supplying a Set for Union | ||
7298 | |||
7299 | To create symmetry between the two ways of starting a set operation | ||
7300 | (accepting and initiating it), the operation handles returned by | ||
7301 | @code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare} do not yet have a | ||
7302 | set to operate on, thus they can not do any work yet. | ||
7303 | |||
7304 | The client must call @code{GNUNET_SETU_commit} to specify a set to use for | ||
7305 | an operation. @code{GNUNET_SETU_commit} may only be called once per set | ||
7306 | operation. | ||
7307 | |||
7308 | @node The Union Result Callback | ||
7309 | @subsubsection The Union Result Callback | ||
7310 | |||
7311 | Clients must specify both a result mode and a result callback with | ||
7312 | @code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare}. The result | ||
7313 | callback with a status indicating either that an element was received, | ||
7314 | transmitted to the other peer (if this information was requested), or | ||
7315 | if the operation failed or ultimately succeeded. | ||
7316 | |||
7317 | @node The SETU Client-Service Protocol | ||
7318 | @subsection The SETU Client-Service Protocol | ||
7319 | |||
7320 | @menu | ||
7321 | * Creating Union Sets:: | ||
7322 | * Listeners for Union:: | ||
7323 | * Initiating Union Operations:: | ||
7324 | * Modifying Union Sets:: | ||
7325 | * Union Results and Operation Status:: | ||
7326 | @end menu | ||
7327 | |||
7328 | @node Creating Union Sets | ||
7329 | @subsubsection Creating Union Sets | ||
7330 | |||
7331 | For each set of a client, there exists a client connection to the service. | ||
7332 | Sets are created by sending the @code{GNUNET_SERVICE_SETU_CREATE} message | ||
7333 | over a new client connection. Multiple operations for one set are | ||
7334 | multiplexed over one client connection, using a request id supplied by | ||
7335 | the client. | ||
7336 | |||
7337 | @node Listeners for Union | ||
7338 | @subsubsection Listeners for Union | ||
7339 | |||
7340 | Each listener also requires a seperate client connection. By sending the | ||
7341 | @code{GNUNET_SERVICE_SETU_LISTEN} message, the client notifies the service | ||
7342 | of the application id and operation type it is interested in. A client | ||
7343 | rejects an incoming request by sending @code{GNUNET_SERVICE_SETU_REJECT} | ||
7344 | on the listener's client connection. | ||
7345 | In contrast, when accepting an incoming request, a | ||
7346 | @code{GNUNET_SERVICE_SETU_ACCEPT} message must be sent over the@ set that | ||
7347 | is supplied for the set operation. | ||
7348 | |||
7349 | @node Initiating Union Operations | ||
7350 | @subsubsection Initiating Union Operations | ||
7351 | |||
7352 | |||
7353 | |||
7354 | Operations with remote peers are initiated by sending a | ||
7355 | @code{GNUNET_SERVICE_SETU_EVALUATE} message to the service. The@ client | ||
7356 | connection that this message is sent by determines the set to use. | ||
7357 | |||
7358 | @node Modifying Union Sets | ||
7359 | @subsubsection Modifying Union Sets | ||
7360 | |||
7361 | Sets are modified with the @code{GNUNET_SERVICE_SETU_ADD} message. | ||
7362 | |||
7363 | |||
7364 | @c %@menu | ||
7365 | @c %* Results and Operation Status:: | ||
7366 | @c %* Iterating Sets:: | ||
7367 | @c %@end menu | ||
7368 | |||
7369 | @node Union Results and Operation Status | ||
7370 | @subsubsection Union Results and Operation Status | ||
7371 | |||
7372 | The service notifies the client of result elements and success/failure of | ||
7373 | a set operation with the @code{GNUNET_SERVICE_SETU_RESULT} message. | ||
7374 | |||
7375 | |||
7376 | @node The SETU Union Peer-to-Peer Protocol | ||
7377 | @subsection The SETU Union Peer-to-Peer Protocol | ||
7378 | |||
7379 | |||
7380 | The SET union protocol is based on Eppstein's efficient set reconciliation | ||
7381 | without prior context. You should read this paper first if you want to | ||
7382 | understand the protocol. | ||
7383 | |||
7384 | The union protocol operates over CADET and starts with a | ||
7385 | GNUNET_MESSAGE_TYPE_SETU_P2P_OPERATION_REQUEST being sent by the peer | ||
7386 | initiating the operation to the peer listening for inbound requests. | ||
7387 | It includes the number of elements of the initiating peer, which is | ||
7388 | currently not used. | ||
7389 | |||
7390 | The listening peer checks if the operation type and application | ||
7391 | identifier are acceptable for its current state. If not, it responds with | ||
7392 | a @code{GNUNET_MESSAGE_TYPE_SETU_RESULT} and a status of | ||
7393 | @code{GNUNET_SETU_STATUS_FAILURE} (and terminates the CADET channel). | ||
7394 | |||
7395 | If the application accepts the request, it sends back a strata estimator | ||
7396 | using a message of type GNUNET_MESSAGE_TYPE_SETU_P2P_SE. The | ||
7397 | initiator evaluates the strata estimator and initiates the exchange of | ||
7398 | invertible Bloom filters, sending a GNUNET_MESSAGE_TYPE_SETU_P2P_IBF. | ||
7399 | |||
7400 | During the IBF exchange, if the receiver cannot invert the Bloom filter or | ||
7401 | detects a cycle, it sends a larger IBF in response (up to a defined | ||
7402 | maximum limit; if that limit is reached, the operation fails). | ||
7403 | Elements decoded while processing the IBF are transmitted to the other | ||
7404 | peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS, or requested from the | ||
7405 | other peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS messages, | ||
7406 | depending on the sign observed during decoding of the IBF. | ||
7407 | Peers respond to a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS message | ||
7408 | with the respective element in a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS | ||
7409 | message. If the IBF fully decodes, the peer responds with a | ||
7410 | GNUNET_MESSAGE_TYPE_SETU_P2P_DONE message instead of another | ||
7411 | GNUNET_MESSAGE_TYPE_SETU_P2P_IBF. | ||
7412 | |||
7413 | All Bloom filter operations use a salt to mingle keys before hashing them | ||
7414 | into buckets, such that future iterations have a fresh chance of | ||
7415 | succeeding if they failed due to collisions before. | ||
7416 | |||
7417 | |||
7418 | |||
7419 | |||
7420 | |||
7421 | |||
6910 | @cindex STATISTICS Subsystem | 7422 | @cindex STATISTICS Subsystem |
6911 | @node STATISTICS Subsystem | 7423 | @node STATISTICS Subsystem |
6912 | @section STATISTICS Subsystem | 7424 | @section STATISTICS Subsystem |