added consensus log-round simulation, work on consensus service, still problems with dv test case

1 files changed, 103 insertions, 0 deletions

diff --git a/src/consensus/consensus-simulation.py b/src/consensus/consensus-simulation.py
new file mode 100644
index 000000000..930dfee62
--- /dev/null
+++ b/src/consensus/consensus-simulation.py
@@ -0,0 +1,103 @@
+#!/usr/bin/python

+# This file is part of GNUnet

+# (C) 2013 Christian Grothoff (and other contributing authors)

+#

+# 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 2, 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.

+

+import argparse

+import random

+from math import ceil,log,floor

+

+def bsc(n):

+  """ count the bits set in n"""

+  l = n.bit_length()

+  c = 0

+  x = 1

+  for _ in range(0, l):

+    if n & x:

+      c = c + 1

+    x = x << 1

+  return c

+

+def simulate(k, n, verbose):

+  assert k < n

+  largest_arc = int(2**ceil(log(n, 2))) / 2

+  num_ghosts = (2 * largest_arc) - n

+  if verbose:

+    print "we have", num_ghosts, "ghost peers"

+  # n.b. all peers with idx<k are evil

+  peers = range(n)

+  info = [1 << x for x in xrange(n)]

+  def done_p():

+    for x in xrange(k, n):

+      if bsc(info[x]) < n-k:

+        return False

+    return True

+  rounds = 0

+  while not done_p():

+    if verbose:

+      print "-- round --"

+    arc = 1

+    while arc <= largest_arc:

+      if verbose:

+        print "-- subround --"

+      new_info = [x for x in info]

+      for peer_physical in xrange(n):

+        peer_logical = peers[peer_physical]

+        peer_type = None

+        partner_logical = (peer_logical + arc) % n

+        partner_physical = peers.index(partner_logical)

+        if peer_physical < k or partner_physical < k:

+          if verbose:

+            print "bad peer in connection", peer_physical, "--", partner_physical

+          continue

+        if peer_logical & arc == 0:

+          # we are outgoing

+          if verbose:

+            print peer_physical, "connects to", partner_physical

+          peer_type = "outgoing"

+          if peer_logical < num_ghosts:

+            # we have a ghost, check if the peer who connects

+            # to our ghost is actually outgoing

+            ghost_partner_logical = (peer_logical - arc) % n

+            if ghost_partner_logical & arc == 0:

+              peer_type = peer_type + ", ghost incoming"

+          new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical]

+          new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical]

+        else:

+          peer_type = "incoming"

+        if verbose > 1:

+          print "type of", str(peer_physical) + ":", peer_type

+      info = new_info

+      arc = arc << 1;

+    rounds = rounds + 1

+    random.shuffle(peers)

+  return rounds

+

+if __name__ == "__main__":

+  parser = argparse.ArgumentParser()

+  parser.add_argument("k", metavar="k", type=int, help="#(bad peers)")

+  parser.add_argument("n", metavar="n", type=int, help="#(all peers)")

+  parser.add_argument("r", metavar="r", type=int, help="#(rounds)")

+  parser.add_argument('--verbose', '-v', action='count')

+

+  args = parser.parse_args()

+  sum = 0.0;

+  for n in xrange (0, args.r):

+    sum += simulate(args.k, args.n, args.verbose)

+  print sum / args.r;

+

+