aboutsummaryrefslogtreecommitdiff
path: root/src/rps/rps-sampler_client.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/rps/rps-sampler_client.c')
-rw-r--r--src/rps/rps-sampler_client.c54
1 files changed, 54 insertions, 0 deletions
diff --git a/src/rps/rps-sampler_client.c b/src/rps/rps-sampler_client.c
index 1ba60e1a8..0de25df07 100644
--- a/src/rps/rps-sampler_client.c
+++ b/src/rps/rps-sampler_client.c
@@ -219,6 +219,41 @@ RPS_sampler_mod_init (size_t init_size,
219 219
220 220
221/** 221/**
222 * @brief Compute the probability that we already observed all peers from a
223 * biased stream of peer ids.
224 *
225 * Deficiency factor:
226 * As introduced by Brahms: Factor between the number of unique ids in a
227 * truly random stream and number of unique ids in the gossip stream.
228 *
229 * @param num_peers_estim The estimated number of peers in the network
230 * @param num_peers_observed The number of peers the given element has observed
231 * @param deficiency_factor A factor that catches the 'bias' of a random stream
232 * of peer ids
233 *
234 * @return The estimated probability
235 */
236static double
237prob_observed_n_peers (uint32_t num_peers_estim,
238 uint32_t num_peers_observed,
239 double deficiency_factor)
240{
241 uint32_t num_peers = num_peers_estim * (1/deficiency_factor);
242 uint64_t sum = 0;
243
244 for (uint32_t i = 0; i < num_peers; i++)
245 {
246 uint64_t a = pow (-1, num_peers-i);
247 uint64_t b = binom (num_peers, i);
248 uint64_t c = pow (i, num_peers_observed);
249 sum += a * b * c;
250 }
251
252 return sum / (double) pow (num_peers, num_peers_observed);
253}
254
255
256/**
222 * Get one random peer out of the sampled peers. 257 * Get one random peer out of the sampled peers.
223 * 258 *
224 * This reinitialises the queried sampler element. 259 * This reinitialises the queried sampler element.
@@ -230,6 +265,7 @@ sampler_mod_get_rand_peer (void *cls)
230 struct RPS_SamplerElement *s_elem; 265 struct RPS_SamplerElement *s_elem;
231 struct GNUNET_TIME_Relative last_request_diff; 266 struct GNUNET_TIME_Relative last_request_diff;
232 struct RPS_Sampler *sampler; 267 struct RPS_Sampler *sampler;
268 double prob_observed_n;
233 269
234 gpc->get_peer_task = NULL; 270 gpc->get_peer_task = NULL;
235 gpc->notify_ctx = NULL; 271 gpc->notify_ctx = NULL;
@@ -294,6 +330,24 @@ sampler_mod_get_rand_peer (void *cls)
294 gpc); 330 gpc);
295 return; 331 return;
296 } 332 }
333 /* compute probability */
334 prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim,
335 s_elem->num_peers,
336 sampler->deficiency_factor);
337 /* check if probability is above desired */
338 if (prob_observed_n >= sampler->desired_probability)
339 {
340 LOG (GNUNET_ERROR_TYPE_DEBUG,
341 "Probability of having observed all peers (%d) too small ( < %d).\n",
342 prob_observed_n,
343 sampler->desired_probability);
344 GNUNET_assert (NULL == gpc->notify_ctx);
345 gpc->notify_ctx =
346 sampler_notify_on_update (sampler,
347 &sampler_mod_get_rand_peer,
348 gpc);
349 return;
350 }
297 /* More reasons to wait could be added here */ 351 /* More reasons to wait could be added here */
298 352
299// GNUNET_STATISTICS_set (stats, 353// GNUNET_STATISTICS_set (stats,