Import RPS

git-svn-id: https://gnunet.org/svn/gnunet@34478 140774ce-b5e7-0310-ab8b-a85725594a96

16 files changed, 2472 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index 1cef035c40..e80a996630 100644
--- a/.gitignore
+++ b/.gitignore
@@ -132,6 +132,7 @@
 /pkgconfig/gnunetats.pc
 /pkgconfig/gnunetregex.pc
 /pkgconfig/gnunetnse.pc
+/pkgconfig/gnunetrps.pc
 /pkgconfig/gnunetnat.pc
 /pkgconfig/Makefile.in
 /pkgconfig/Makefile
@@ -1000,6 +1001,17 @@
 /src/revocation/Makefile
 /src/revocation/.deps
 
+# /src/rps/
+/src/rps/rps.conf
+/src/rps/test_rps_multipeer
+/src/rps/Makefile.in
+/src/rps/Makefile
+/src/rps/.deps
+/src/rps/gnunet-service-rps
+/src/rps/gnunet-rps
+/src/rps/*log
+/src/rps/*.trs
+
 # /src/scalarproduct/
 /src/scalarproduct/gnunet-service-scalarproduct
 /src/scalarproduct/scalarproduct.conf
diff --git a/configure.ac b/configure.ac
index ae7e04394d..9c0bdc1b1c 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1483,6 +1483,8 @@ src/regex/Makefile
 src/regex/regex.conf
 src/revocation/Makefile
 src/revocation/revocation.conf
+src/rps/Makefile
+src/rps/rps.conf
 src/secretsharing/Makefile
 src/secretsharing/secretsharing.conf
 src/sensor/Makefile
@@ -1542,6 +1544,7 @@ pkgconfig/gnunetpsyc.pc
 pkgconfig/gnunetpsycstore.pc
 pkgconfig/gnunetregex.pc
 pkgconfig/gnunetrevocation.pc
+pkgconfig/gnunetrps.pc
 pkgconfig/gnunetscalarproduct.pc
 pkgconfig/gnunetset.pc
 pkgconfig/gnunetsocial.pc
diff --git a/pkgconfig/Makefile.am b/pkgconfig/Makefile.am
index ac40906cd6..547755c127 100644
--- a/pkgconfig/Makefile.am
+++ b/pkgconfig/Makefile.am
@@ -31,6 +31,7 @@ pcfiles = \
        gnunetpsycstore.pc \
        gnunetregex.pc \
        gnunetrevocation.pc \
+       gnunetrps.pc \
        gnunetscalarproduct.pc \
        gnunetset.pc \
        gnunetspeaker.pc \
@@ -87,6 +88,7 @@ EXTRA_DIST = \
        gnunetpsycstore.pc.in \
        gnunetregex.pc.in \
        gnunetrevocation.pc.in \
+       gnunetrps.pc.in \
        gnunetscalarproduct.pc.in \
        gnunetset.pc.in \
        gnunetspeaker.pc.in \
diff --git a/pkgconfig/gnunetrps.pc.in b/pkgconfig/gnunetrps.pc.in
new file mode 100644
index 0000000000..94042e8eb2
--- /dev/null
+++ b/pkgconfig/gnunetrps.pc.in
@@ -0,0 +1,12 @@
+prefix=@prefix@
+exec_prefix=@exec_prefix@
+libdir=@libdir@
+includedir=@includedir@
+
+Name: GNUnet RPS
+Description: random peer sampling based on the BRAHMS protocol
+URL: https://gnunet.org
+Version: @VERSION@
+Requires:
+Libs: -L${libdir} -lgnunetrps
+Cflags: -I${includedir}
diff --git a/src/Makefile.am b/src/Makefile.am
index 18f8aeef2d..8efb7afe65 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -20,6 +20,7 @@ if HAVE_EXPERIMENTAL
   env \
   psycstore \
   psyc \
+  rps \
   social \
   $(CONSENSUS) \
   $(SECRETSHARING) \
diff --git a/src/include/gnunet_protocols.h b/src/include/gnunet_protocols.h
index 5a2b644be6..747a252ffc 100644
--- a/src/include/gnunet_protocols.h
+++ b/src/include/gnunet_protocols.h
@@ -2630,10 +2630,47 @@ extern "C"
 #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_ACT_MALICIOUS_OK  894
 
 #endif
+
+/*******************************************************************************
+ * RPS messages
+ ******************************************************************************/
+
+/* P2P Messages */
+
+/**
+ * RPS PUSH message to push own ID to another peer
+ */
+#define GNUNET_MESSAGE_TYPE_RPS_PP_PUSH         950
+
+/**
+ * RPS PULL REQUEST message to request the local view of another peer
+ */
+#define GNUNET_MESSAGE_TYPE_RPS_PP_PULL_REQUEST 951
+
+/**
+ * RPS PULL REPLY message which contains the view of the other peer
+ */
+#define GNUNET_MESSAGE_TYPE_RPS_PP_PULL_REPLY   952
+
+
+
+/* Client-Service Messages */
+
+/**
+ * RPS CS REQUEST Message for the Client to request (a) random peer(s)
+ */
+#define GNUNET_MESSAGE_TYPE_RPS_CS_REQUEST      953
+
+/**
+ * RPS CS REPLY Message for the Server to send (a) random peer(s)
+ */
+#define GNUNET_MESSAGE_TYPE_RPS_CS_REPLY        954
+
+
 /*******************************************************************************/
 
 /**
- * Next available: 904
+ * Next available: 960
  */
 
 /**
diff --git a/src/include/gnunet_rps_service.h b/src/include/gnunet_rps_service.h
new file mode 100644
index 0000000000..dc822b8f17
--- /dev/null
+++ b/src/include/gnunet_rps_service.h
@@ -0,0 +1,83 @@
+/*
+      This file is part of GNUnet
+      (C) 
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 3, or (at your
+      option) any later version.
+
+      GNUnet is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @file include/gnunet_rps_service.h
+ * @brief API to the rps service
+ * @author Julius Bünger
+ */
+#ifndef GNUNET_RPS_SERVICE_H
+#define GNUNET_RPS_SERVICE_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#if 0                           /* keep Emacsens' auto-indent happy */
+}
+#endif
+#endif
+
+/**
+ * Version of the rps API.
+ */
+#define GNUNET_RPS_VERSION 0x00000000
+
+typedef void (* GNUNET_RPS_NotifyReadyCB) (void *cls, uint64_t num_peers, struct GNUNET_PeerIdentity *peers);
+
+  struct GNUNET_RPS_Request_Handle *
+GNUNET_RPS_request_peers_single_call (const struct GNUNET_CONFIGURATION_Handle *cfg,
+                          uint64_t n,
+                          GNUNET_RPS_NotifyReadyCB ready_cb,
+                          void *cls);
+
+/**
+ * Connect to the rps service
+ */
+  struct GNUNET_RPS_Handle *
+GNUNET_RPS_connect( const struct GNUNET_CONFIGURATION_Handle *cfg );
+
+/**
+ * Request n random peers.
+ */
+  struct GNUNET_RPS_Request_Handle *
+GNUNET_RPS_request_peers (struct GNUNET_RPS_Handle *h, uint64_t n,
+                          GNUNET_RPS_NotifyReadyCB ready_cb,
+                          void *cls);
+
+/**
+ * Cancle an issued request.
+ */
+  void
+GNUNET_RPS_request_cancel ( struct GNUNET_RPS_Request_Handle *rh );
+
+/**
+ * Disconnect from the rps service
+ */
+  void
+GNUNET_RPS_disconnect ( struct GNUNET_RPS_Handle *h );
+
+#if 0                           /* keep Emacsens' auto-indent happy */
+{
+#endif
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/src/rps/Makefile.am b/src/rps/Makefile.am
new file mode 100644
index 0000000000..f6c31b1073
--- /dev/null
+++ b/src/rps/Makefile.am
@@ -0,0 +1,76 @@
+AM_CPPFLAGS = -I$(top_srcdir)/src/include
+
+if MINGW
+ WINFLAGS = -Wl,--no-undefined -Wl,--export-all-symbols
+endif
+
+if USE_COVERAGE
+  AM_CFLAGS = --coverage -O0
+  XLIB = -lgcov
+endif
+
+pkgcfgdir= $(pkgdatadir)/config.d/
+
+libexecdir= $(pkglibdir)/libexec/
+
+pkgcfg_DATA = \
+  rps.conf
+
+bin_PROGRAMS = gnunet-rps
+
+gnunet_rps_SOURCES = gnunet-rps.c
+gnunet_rps_LDADD = \
+  libgnunetrps.la \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(XLIB) $(GN_LIBINTL)
+
+lib_LTLIBRARIES = libgnunetrps.la
+
+libgnunetrps_la_SOURCES = \
+  rps_api.c rps.h
+libgnunetrps_la_LIBADD = \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(GN_LIBINTL) $(XLIB)
+libgnunetrps_la_LDFLAGS = \
+  $(GN_LIB_LDFLAGS)  $(WINFLAGS) \
+  -version-info 0:0:0
+
+
+libexec_PROGRAMS = \
+ gnunet-service-rps
+
+
+gnunet_service_rps_SOURCES = \
+ gnunet-service-rps.c
+gnunet_service_rps_LDADD = \
+  libgnunetrps.la \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(top_builddir)/src/cadet/libgnunetcadet.la \
+  $(top_builddir)/src/nse/libgnunetnse.la \
+  $(top_builddir)/src/statistics/libgnunetstatistics.la \
+  $(LIBGCRYPT_LIBS) \
+  -lm -lgcrypt \
+  $(GN_LIBINTL)
+
+if HAVE_TESTING
+check_PROGRAMS = \
+ test_rps_multipeer
+endif
+
+if ENABLE_TEST_RUN
+AM_TESTS_ENVIRONMENT=export GNUNET_PREFIX=$${GNUNET_PREFIX:-@libdir@};export PATH=$${GNUNET_PREFIX:-@prefix@}/bin:$$PATH;
+TESTS = $(check_PROGRAMS)
+endif
+
+test_rps_multipeer_SOURCES = \
+ test_rps_multipeer.c
+test_rps_multipeer_LDADD = \
+  libgnunetrps.la \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(top_builddir)/src/testbed/libgnunettestbed.la \
+  -lm
+
+
+EXTRA_DIST = \
+  test_rps.conf
+
diff --git a/src/rps/gnunet-rps.c b/src/rps/gnunet-rps.c
new file mode 100644
index 0000000000..7a4f75d6f8
--- /dev/null
+++ b/src/rps/gnunet-rps.c
@@ -0,0 +1,71 @@
+/*
+     This file is part of GNUnet.
+     (C)
+
+     GNUnet is free software; you can redistribute it and/or modify
+     it under the terms of the GNU General Public License as published
+     by the Free Software Foundation; either version 3, or (at your
+     option) any later version.
+
+     GNUnet is distributed in the hope that it will be useful, but
+     WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+     Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file rps/gnunet-rps.c
+ * @brief rps tool
+ * @author Julius Bünger
+ */
+#include <gnunet/platform.h>
+#include <gnunet/gnunet_util_lib.h>
+#include "gnunet_rps_service.h"
+
+static int ret;
+
+/**
+ * Main function that will be run by the scheduler.
+ *
+ * @param cls closure
+ * @param args remaining command-line arguments
+ * @param cfgfile name of the configuration file used (for saving, can be NULL!)
+ * @param cfg configuration
+ */
+static void
+run (void *cls,
+     char *const *args,
+     const char *cfgfile,
+     const struct GNUNET_CONFIGURATION_Handle *cfg)
+{
+  ret = 0;
+}
+
+/**
+ * The main function to rps.
+ *
+ * @param argc number of arguments from the command line
+ * @param argv command line arguments
+ * @return 0 ok, 1 on error
+ */
+int
+main (int argc, char *const *argv)
+{
+  static const struct GNUNET_GETOPT_CommandLineOption options[] = {
+    GNUNET_GETOPT_OPTION_END
+  };
+  return (GNUNET_OK ==
+          GNUNET_PROGRAM_run (argc,
+                              argv,
+                              "gnunet-rps [options [value]]",
+                              gettext_noop
+                              ("rps"),
+                              options, &run, NULL)) ? ret : 1;
+}
+
+/* end of gnunet-rps.c */
diff --git a/src/rps/gnunet-service-rps.c b/src/rps/gnunet-service-rps.c
new file mode 100644
index 0000000000..6d96f54869
--- /dev/null
+++ b/src/rps/gnunet-service-rps.c
@@ -0,0 +1,1382 @@
+/*
+     This file is part of GNUnet.
+     (C)
+
+     GNUnet is free software; you can redistribute it and/or modify
+     it under the terms of the GNU General Public License as published
+     by the Free Software Foundation; either version 3, or (at your
+     option) any later version.
+
+     GNUnet is distributed in the hope that it will be useful, but
+     WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+     Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file rps/gnunet-service-rps.c
+ * @brief rps service implementation
+ * @author Julius Bünger
+ */
+#include "platform.h"
+#include "gnunet_util_lib.h"
+#include "gnunet_cadet_service.h"
+#include "gnunet_nse_service.h"
+#include "rps.h"
+
+#include <math.h>
+#include <inttypes.h>
+
+#define LOG(kind, ...) GNUNET_log(kind, __VA_ARGS__)
+
+// TODO modify @brief in every file
+
+// TODO take care that messages are not longer than 64k
+
+// TODO check for overflows
+
+// TODO align message structs
+
+// TODO multipeerlist indep of gossiped list
+
+// TODO maybe wait during initialisation some time to get some peers
+//      - initialise peers before proceeding
+//      - Use the magic 0000 peer GNUNET_CADET_get_peers() returns
+
+// (TODO api -- possibility of getting weak random peer immideately)
+
+// TODO malicious peer
+
+// TODO switch Slist -> DLL
+
+/**
+ * Our configuration.
+ */
+static const struct GNUNET_CONFIGURATION_Handle *cfg;
+
+/**
+ * Our own identity.
+ */
+struct GNUNET_PeerIdentity *own_identity;
+
+/**
+ * Compare two peer identities. Taken from secretsharing.
+ *
+ * @param p1 Some peer identity.
+ * @param p2 Some peer identity.
+ * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
+ */
+static int
+peer_id_cmp (const void *p1, const void *p2)
+{
+  return memcmp (p1, p2, sizeof (struct GNUNET_PeerIdentity));
+}
+
+/***********************************************************************
+ * Sampler
+ *
+ * WARNING: This section needs to be reviewed regarding the use of
+ * functions providing (pseudo)randomness!
+***********************************************************************/
+
+// TODO init list
+// TODO grow/shrink list
+
+/**
+ * A sampler sampling PeerIDs.
+ */
+struct Sampler
+{
+  /**
+   * Min-wise linear permutation used by this sampler.
+   *
+   * This is an key later used by a hmac.
+   */
+  struct GNUNET_CRYPTO_AuthKey auth_key;
+
+  /**
+   * The PeerID this sampler currently samples.
+   */
+  struct GNUNET_PeerIdentity *peer_id;
+
+  /**
+   * The according hash value of this PeerID.
+   */
+  struct GNUNET_HashCode peer_id_hash;
+
+};
+
+typedef void (* SAMPLER_deleteCB) (void *cls, struct GNUNET_PeerIdentity *id, struct GNUNET_HashCode hash);
+
+/**
+ * (Re)Initialise given Sampler with random min-wise independent function.
+ *
+ * In this implementation this means choosing an auth_key for later use in
+ * a hmac at random.
+ */
+  struct Sampler *
+SAMPLER_init()
+{
+  struct Sampler *s;
+  
+  s = GNUNET_new(struct Sampler);
+
+  // I guess I don't need to call GNUNET_CRYPTO_hmac_derive_key()...
+  GNUNET_CRYPTO_random_block(GNUNET_CRYPTO_QUALITY_STRONG,
+                             &(s->auth_key.key),
+                             GNUNET_CRYPTO_HASH_LENGTH);
+
+  s->peer_id = own_identity; // Maybe set to own PeerID. So we always have
+                     // a valid PeerID in the sampler.
+                     // Maybe take a PeerID as second argument.
+
+  GNUNET_CRYPTO_hmac(&s->auth_key, s->peer_id,
+                     sizeof(struct GNUNET_PeerIdentity),
+                     &s->peer_id_hash);
+
+  return s;
+}
+
+/**
+ * Compare two hashes.
+ *
+ * Returns if the first one is smaller then the second.
+ * Used by SAMPLER_next() to compare hashes.
+ */
+  int
+hash_cmp(struct GNUNET_HashCode hash1, struct GNUNET_HashCode hash2)
+{
+  return memcmp( (const void *) &hash1, (const void *) & hash2, sizeof(struct GNUNET_HashCode)) < 0;
+}
+
+/**
+ * Input an PeerID into the given sampler.
+ */
+  static void
+SAMPLER_next(struct Sampler *s, const struct GNUNET_PeerIdentity *id, SAMPLER_deleteCB del_cb, void *cb_cls)
+{
+  struct GNUNET_HashCode other_hash;
+
+  GNUNET_CRYPTO_hmac(&s->auth_key,
+                     id,
+                     sizeof(struct GNUNET_PeerIdentity),
+                     &other_hash);
+
+  if ( NULL == s->peer_id ) { // Or whatever is a valid way to say
+                              // "we have no PeerID at the moment"
+    *s->peer_id = *id;
+    s->peer_id_hash = other_hash;
+
+  } else {
+
+    if ( hash_cmp(other_hash, s->peer_id_hash) ) {
+      LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Got PeerID %s; Discarding old PeerID %s\n",
+          GNUNET_i2s(id), GNUNET_i2s(s->peer_id));
+
+      if ( NULL != del_cb ) {
+        del_cb(cb_cls, s->peer_id, s->peer_id_hash);
+      }
+      *s->peer_id = *id;
+      s->peer_id_hash = other_hash;
+
+    } else {
+      LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Got PeerID %s; Keeping old PeerID %s\n",
+          GNUNET_i2s(id), GNUNET_i2s(s->peer_id));
+    }
+
+  }
+}
+
+
+
+/**
+ * A fuction to update every sampler in the given list
+ */
+  static void
+SAMPLER_update_list(struct GNUNET_CONTAINER_SList *lst, const struct GNUNET_PeerIdentity *id,
+                    SAMPLER_deleteCB del_cb, void *cb_cls)
+{
+  struct GNUNET_CONTAINER_SList_Iterator *iter;
+  struct Sampler *sampler;
+  size_t s;
+
+  iter = GNUNET_malloc(sizeof(struct GNUNET_CONTAINER_SList_Iterator));
+  *iter = GNUNET_CONTAINER_slist_begin(lst);
+  s = sizeof(struct Sampler);
+  do {
+    sampler = (struct Sampler *) GNUNET_CONTAINER_slist_get(iter, &s);
+    SAMPLER_next(sampler, id, del_cb, cb_cls);
+  } while ( GNUNET_NO != GNUNET_CONTAINER_slist_next(iter) );
+  
+  GNUNET_CONTAINER_slist_iter_destroy(iter);
+}
+
+/**
+ * Get one random peer out of the sampled peers.
+ *
+ * We might want to reinitialise this sampler after giving the
+ * corrsponding peer to the client.
+ */
+  struct GNUNET_PeerIdentity* 
+SAMPLER_get_rand_peer (struct GNUNET_CONTAINER_SList *lst)
+{
+  uint64_t list_size;
+
+  LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER_get_rand_peer:\n");
+
+  list_size = (uint64_t) GNUNET_CONTAINER_slist_count(lst);
+
+  if ( 0 == list_size ) {
+    LOG(GNUNET_ERROR_TYPE_DEBUG, "Sgrp: List empty - Returning own PeerID %s\n", GNUNET_i2s(own_identity));
+    return own_identity;
+  } else {
+    uint64_t index;
+    struct GNUNET_CONTAINER_SList_Iterator *iter;
+    uint64_t i;
+    size_t s;
+    struct GNUNET_PeerIdentity *peer;
+
+    /**
+     * Choose the index of the peer we want to give back
+     * at random from the interval of the sampler list
+     */
+    index = GNUNET_CRYPTO_random_u64(GNUNET_CRYPTO_QUALITY_STRONG,
+                                     list_size);
+                                     // TODO check that it does not overflow
+    LOG(GNUNET_ERROR_TYPE_DEBUG, "Sgrp: Length of Slist: %" PRIu64 ", index: %" PRIu64 "\n", list_size, index);
+
+    s = sizeof( struct Sampler );
+    iter = GNUNET_malloc(sizeof(struct GNUNET_CONTAINER_SList_Iterator));
+    *iter = GNUNET_CONTAINER_slist_begin(lst);
+    for ( i = 0 ; i < index ; i++ ) {
+      if (GNUNET_NO == GNUNET_CONTAINER_slist_next(iter) ) { // Maybe unneeded
+        *iter = GNUNET_CONTAINER_slist_begin(lst);
+      }
+    }
+    
+    // TODO something missing?
+
+    // FIXME this looks wrong:
+    peer = ((struct Sampler *) GNUNET_CONTAINER_slist_get(iter, &s))->peer_id;
+    GNUNET_CONTAINER_slist_iter_destroy(iter);
+    LOG(GNUNET_ERROR_TYPE_DEBUG, "Sgrp: Returning PeerID %s (own ID: %s)\n", GNUNET_i2s(peer), GNUNET_i2s(own_identity));
+
+    return peer;
+  }
+}
+
+/**
+ * Get n random peers out of the sampled peers.
+ *
+ * We might want to reinitialise this sampler after giving the
+ * corrsponding peer to the client.
+ * Random with or without consumption?
+ */
+  struct GNUNET_PeerIdentity**  // TODO give back simple array
+SAMPLER_get_n_rand_peers (struct GNUNET_CONTAINER_SList *lst, uint64_t n)
+{
+  // TODO check if we have too much (distinct) sampled peers
+  // If we are not ready yet maybe schedule for later
+  struct GNUNET_PeerIdentity **peers;
+  uint64_t i;
+  
+  peers = GNUNET_malloc(n * sizeof(struct GNUNET_PeerIdentity *));
+
+  for ( i = 0 ; i < n ; i++ ) {
+    peers[i] = SAMPLER_get_rand_peer(lst);
+  }
+
+  // TODO something else missing?
+  return peers;
+}
+
+/**
+ * Counts how many Samplers currently hold a given PeerID.
+ */
+  uint64_t
+SAMPLER_count_id ( struct GNUNET_CONTAINER_SList *lst, struct GNUNET_PeerIdentity *id ) {
+  size_t s;
+  struct GNUNET_CONTAINER_SList_Iterator *iter;
+  uint64_t count;
+
+  s = sizeof( struct Sampler );
+  iter = GNUNET_new(struct GNUNET_CONTAINER_SList_Iterator);
+  *iter = GNUNET_CONTAINER_slist_begin(lst);
+  count = 0;
+  while ( GNUNET_YES == GNUNET_CONTAINER_slist_next(iter) ) {
+    if ( peer_id_cmp( ((struct Sampler *) GNUNET_CONTAINER_slist_get(iter, &s))->peer_id, id) ) {
+      count++;
+    }
+  }
+  GNUNET_CONTAINER_slist_iter_destroy(iter);
+  return count;
+}
+
+
+/***********************************************************************
+ * /Sampler
+***********************************************************************/
+
+
+
+/***********************************************************************
+ * Gossip list
+***********************************************************************/
+
+///**
+// * Get one random peer out of the gossiped peer list.
+// */
+//  struct GNUNET_PeerIdentity *
+//get_random_peer(struct GNUNET_CONTAINER_MultiPeerMap * lst)
+//{
+//  size_t n;
+//  struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
+//  uint64_t index;
+//  uint64_t i;
+//  struct GNUNET_PeerIdentity *peer;
+//
+//  n = (size_t) GNUNET_CONTAINER_multipeermap_size(lst);
+//  index = GNUNET_CRYPTO_random_u64(GNUNET_CRYPTO_QUALITY_STRONG,
+//                                   (uint64_t) n);
+//  iter = GNUNET_CONTAINER_multipeermap_iterator_create(lst);
+//
+//  for ( i = 0 ; i < index ; i++ ) {
+//    GNUNET_CONTAINER_multipeermap_iterator_next(iter, NULL, NULL);
+//  }
+//  
+//  peer = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
+//  GNUNET_CONTAINER_multipeermap_iterator_next(iter, peer, NULL);
+//
+//  return peer;
+//}
+
+
+/***********************************************************************
+ * /Gossip list
+***********************************************************************/
+
+
+
+/***********************************************************************
+ * Housekeeping with peers
+***********************************************************************/
+
+/**
+ * Struct used to store the context of a connected client.
+ */
+struct client_ctx
+{
+  /**
+   * The message queue to communicate with the client.
+   */
+  struct GNUNET_MQ_Handle *mq;
+};
+
+/**
+ * Used to keep track in what lists single peerIDs are.
+ */
+enum in_list_flag // probably unneeded
+{
+  in_other_sampler_list = 0x1,
+  in_other_gossip_list  = 0x2, // unneeded?
+  in_own_sampler_list   = 0x4,
+  in_own_gossip_list    = 0x8 // unneeded?
+};
+
+/**
+ * Struct used to keep track of other peer's status
+ *
+ * This is stored in a multipeermap.
+ */
+struct peer_context
+{
+  /**
+   * In own gossip/sampler list, in other's gossip/sampler list
+   */
+  uint32_t in_flags; // unneeded?
+
+  /**
+   * Message queue open to client
+   */
+  struct GNUNET_MQ_Handle *mq;
+
+  /**
+   * Channel open to client.
+   */
+  struct GNUNET_CADET_Channel *to_channel;
+
+  /**
+   * Channel open from client.
+   */
+  struct GNUNET_CADET_Channel *from_channel; // unneeded
+
+  /**
+   * This is pobably followed by 'statistical' data (when we first saw
+   * him, how did we get his ID, how many pushes (in a timeinterval),
+   * ...)
+   */
+};
+
+/***********************************************************************
+ * /Housekeeping with peers
+***********************************************************************/
+
+/**
+ * Set of all peers to keep track of them.
+ */
+static struct GNUNET_CONTAINER_MultiPeerMap *peer_map;
+
+
+// -- gossip list length --
+// Depends on the (estimated) size of the
+// network. - Initial size might be the
+// number of peers cadet provides.
+// TODO other events to grow/shrink size?
+
+/**
+ * List of samplers
+ */
+struct GNUNET_CONTAINER_SList *sampler_list;
+
+/**
+ * Sampler list size
+ *
+ * Adapts to the nse. Size should be in BigTheta(network_size)^(1/3).
+ */
+size_t sampler_list_size;
+
+
+/**
+ * The gossiped list of peers.
+ */
+struct GNUNET_PeerIdentity *gossip_list;
+
+/**
+ * Size of the gossiped list
+ */
+unsigned int gossip_list_size;
+
+/**
+ * Min size of the gossip list
+ */
+uint64_t gossip_list_min_size;
+
+///**
+// * Max size of the gossip list
+// * 
+// * This will probably be left to be set by the client.
+// */
+//uint64_t gossip_list_max_size;
+
+
+/**
+ * The estimated size of the network.
+ *
+ * Influenced by the stdev.
+ */
+size_t est_size;
+
+
+
+/**
+ * Percentage of total peer number in the gossip list
+ * to send random PUSHes to
+ */
+float alpha;
+
+/**
+ * Percentage of total peer number in the gossip list
+ * to send random PULLs to
+ */
+float beta;
+
+/**
+ * The percentage gamma of history updates.
+ * Simply 1 - alpha - beta
+ */
+
+
+
+
+/**
+ * Identifier for the main task that runs periodically.
+ */
+GNUNET_SCHEDULER_TaskIdentifier do_round_task;
+
+/**
+ * Time inverval the do_round task runs in.
+ */
+struct GNUNET_TIME_Relative round_interval;
+
+
+
+/**
+ * List to store peers received through pushes temporary.
+ */
+struct GNUNET_CONTAINER_SList *push_list;
+
+/**
+ * List to store peers received through pulls temporary.
+ */
+struct GNUNET_CONTAINER_SList *pull_list;
+
+
+/**
+ * Handler to NSE.
+ */
+struct GNUNET_NSE_Handle *nse;
+
+/**
+ * Handler to CADET.
+ */
+struct GNUNET_CADET_Handle *cadet_handle;
+
+
+/***********************************************************************
+ * Util functions
+***********************************************************************/
+
+/**
+ * Get random peer from the gossip list.
+ */
+  struct GNUNET_PeerIdentity *
+get_rand_gossip_peer()
+{
+  uint64_t index;
+  struct GNUNET_PeerIdentity *peer;
+
+  // TODO find a better solution.
+  // FIXME if we have only own ID in gossip list this will block
+  // but then we might have a problem nevertheless ?
+
+  do {
+
+    /**;
+     * Choose the index of the peer we want to return
+     * at random from the interval of the gossip list
+     */
+    index = GNUNET_CRYPTO_random_u64(GNUNET_CRYPTO_QUALITY_STRONG,
+                                     gossip_list_size);
+
+    peer = &(gossip_list[index]);
+  } while ( own_identity == peer || NULL == peer );
+
+  return peer;
+}
+
+/**
+ * Get the message queue of a specific peer.
+ *
+ * If we already have a message queue open to this client,
+ * simply return it, otherways create one.
+ */
+  struct GNUNET_MQ_Handle *
+get_mq (struct GNUNET_CONTAINER_MultiPeerMap *peer_map, struct GNUNET_PeerIdentity *peer_id)
+{
+  struct peer_context *ctx;
+  struct GNUNET_MQ_Handle * mq;
+  struct GNUNET_CADET_Channel *channel;
+
+  if ( GNUNET_OK != GNUNET_CONTAINER_multipeermap_contains( peer_map, peer_id ) ) {
+
+    channel = GNUNET_CADET_channel_create(cadet_handle, NULL, peer_id,
+                                  GNUNET_RPS_CADET_PORT,
+                                  GNUNET_CADET_OPTION_RELIABLE);
+    mq = GNUNET_CADET_mq_create(channel);
+
+    ctx = GNUNET_malloc(sizeof(struct peer_context));
+    ctx->in_flags = 0;
+    ctx->to_channel = channel;
+    ctx->mq = mq;
+
+    GNUNET_CONTAINER_multipeermap_put(peer_map, peer_id, ctx,
+                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
+  } else {
+    ctx = GNUNET_CONTAINER_multipeermap_get(peer_map, peer_id);
+    if ( NULL == ctx->mq ) {
+      if ( NULL == ctx->to_channel ) {
+        channel = GNUNET_CADET_channel_create(cadet_handle, NULL, peer_id,
+                                      GNUNET_RPS_CADET_PORT,
+                                      GNUNET_CADET_OPTION_RELIABLE);
+        ctx->to_channel = channel;
+      }
+
+      mq = GNUNET_CADET_mq_create(ctx->to_channel);
+      ctx->mq = mq;
+    }
+  }
+
+  return ctx->mq;
+}
+
+
+/***********************************************************************
+ * /Util functions
+***********************************************************************/
+
+/**
+ * Function called by NSE.
+ *
+ * Updates sizes of sampler list and gossip list and adapt those lists
+ * accordingly.
+ */
+  void
+nse_callback(void *cls, struct GNUNET_TIME_Absolute timestamp, double logestimate, double std_dev)
+{
+  double estimate;
+  //double scale; // TODO this might go gloabal/config
+
+  LOG(GNUNET_ERROR_TYPE_DEBUG, "Received a ns estimate - logest: %f, std_dev: %f\n", logestimate, std_dev);
+  //scale = .01;
+  estimate = 1 << (uint64_t) round(logestimate);
+  // GNUNET_NSE_log_estimate_to_n (logestimate);
+  estimate = pow(estimate, 1./3);// * (std_dev * scale); // TODO add
+  if ( 0 < estimate ) {
+    LOG(GNUNET_ERROR_TYPE_DEBUG, "Changing estimate to %f\n", estimate);
+    est_size = estimate;
+  } else {
+    LOG(GNUNET_ERROR_TYPE_DEBUG, "Not using estimate %f\n", estimate);
+  }
+}
+
+/**
+ * Handle RPS request from the client.
+ *
+ * @param cls closure
+ * @param client identification of the client
+ * @param message the actual message
+ */
+static void
+// TODO rename
+handle_cs_request (void *cls,
+            struct GNUNET_SERVER_Client *client,
+            const struct GNUNET_MessageHeader *message)
+{
+  LOG(GNUNET_ERROR_TYPE_DEBUG, "Client requested (a) random peer(s).\n");
+
+  struct GNUNET_RPS_CS_RequestMessage *