diff options
Diffstat (limited to 'src/consensus/consensus-simulation.py')
-rw-r--r-- | src/consensus/consensus-simulation.py | 206 |
1 files changed, 103 insertions, 103 deletions
diff --git a/src/consensus/consensus-simulation.py b/src/consensus/consensus-simulation.py index 930dfee62..3bc4ab652 100644 --- a/src/consensus/consensus-simulation.py +++ b/src/consensus/consensus-simulation.py | |||
@@ -1,103 +1,103 @@ | |||
1 | #!/usr/bin/python | 1 | #!/usr/bin/python |
2 | # This file is part of GNUnet | 2 | # This file is part of GNUnet |
3 | # (C) 2013 Christian Grothoff (and other contributing authors) | 3 | # (C) 2013 Christian Grothoff (and other contributing authors) |
4 | # | 4 | # |
5 | # GNUnet is free software; you can redistribute it and/or modify | 5 | # GNUnet is free software; you can redistribute it and/or modify |
6 | # it under the terms of the GNU General Public License as published | 6 | # it under the terms of the GNU General Public License as published |
7 | # by the Free Software Foundation; either version 2, or (at your | 7 | # by the Free Software Foundation; either version 2, or (at your |
8 | # option) any later version. | 8 | # option) any later version. |
9 | # | 9 | # |
10 | # GNUnet is distributed in the hope that it will be useful, but | 10 | # GNUnet is distributed in the hope that it will be useful, but |
11 | # WITHOUT ANY WARRANTY; without even the implied warranty of | 11 | # WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | # General Public License for more details. | 13 | # General Public License for more details. |
14 | # | 14 | # |
15 | # You should have received a copy of the GNU General Public License | 15 | # You should have received a copy of the GNU General Public License |
16 | # along with GNUnet; see the file COPYING. If not, write to the | 16 | # along with GNUnet; see the file COPYING. If not, write to the |
17 | # Free Software Foundation, Inc., 59 Temple Place - Suite 330, | 17 | # Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
18 | # Boston, MA 02111-1307, USA. | 18 | # Boston, MA 02111-1307, USA. |
19 | 19 | ||
20 | import argparse | 20 | import argparse |
21 | import random | 21 | import random |
22 | from math import ceil,log,floor | 22 | from math import ceil,log,floor |
23 | 23 | ||
24 | def bsc(n): | 24 | def bsc(n): |
25 | """ count the bits set in n""" | 25 | """ count the bits set in n""" |
26 | l = n.bit_length() | 26 | l = n.bit_length() |
27 | c = 0 | 27 | c = 0 |
28 | x = 1 | 28 | x = 1 |
29 | for _ in range(0, l): | 29 | for _ in range(0, l): |
30 | if n & x: | 30 | if n & x: |
31 | c = c + 1 | 31 | c = c + 1 |
32 | x = x << 1 | 32 | x = x << 1 |
33 | return c | 33 | return c |
34 | 34 | ||
35 | def simulate(k, n, verbose): | 35 | def simulate(k, n, verbose): |
36 | assert k < n | 36 | assert k < n |
37 | largest_arc = int(2**ceil(log(n, 2))) / 2 | 37 | largest_arc = int(2**ceil(log(n, 2))) / 2 |
38 | num_ghosts = (2 * largest_arc) - n | 38 | num_ghosts = (2 * largest_arc) - n |
39 | if verbose: | 39 | if verbose: |
40 | print "we have", num_ghosts, "ghost peers" | 40 | print "we have", num_ghosts, "ghost peers" |
41 | # n.b. all peers with idx<k are evil | 41 | # n.b. all peers with idx<k are evil |
42 | peers = range(n) | 42 | peers = range(n) |
43 | info = [1 << x for x in xrange(n)] | 43 | info = [1 << x for x in xrange(n)] |
44 | def done_p(): | 44 | def done_p(): |
45 | for x in xrange(k, n): | 45 | for x in xrange(k, n): |
46 | if bsc(info[x]) < n-k: | 46 | if bsc(info[x]) < n-k: |
47 | return False | 47 | return False |
48 | return True | 48 | return True |
49 | rounds = 0 | 49 | rounds = 0 |
50 | while not done_p(): | 50 | while not done_p(): |
51 | if verbose: | 51 | if verbose: |
52 | print "-- round --" | 52 | print "-- round --" |
53 | arc = 1 | 53 | arc = 1 |
54 | while arc <= largest_arc: | 54 | while arc <= largest_arc: |
55 | if verbose: | 55 | if verbose: |
56 | print "-- subround --" | 56 | print "-- subround --" |
57 | new_info = [x for x in info] | 57 | new_info = [x for x in info] |
58 | for peer_physical in xrange(n): | 58 | for peer_physical in xrange(n): |
59 | peer_logical = peers[peer_physical] | 59 | peer_logical = peers[peer_physical] |
60 | peer_type = None | 60 | peer_type = None |
61 | partner_logical = (peer_logical + arc) % n | 61 | partner_logical = (peer_logical + arc) % n |
62 | partner_physical = peers.index(partner_logical) | 62 | partner_physical = peers.index(partner_logical) |
63 | if peer_physical < k or partner_physical < k: | 63 | if peer_physical < k or partner_physical < k: |
64 | if verbose: | 64 | if verbose: |
65 | print "bad peer in connection", peer_physical, "--", partner_physical | 65 | print "bad peer in connection", peer_physical, "--", partner_physical |
66 | continue | 66 | continue |
67 | if peer_logical & arc == 0: | 67 | if peer_logical & arc == 0: |
68 | # we are outgoing | 68 | # we are outgoing |
69 | if verbose: | 69 | if verbose: |
70 | print peer_physical, "connects to", partner_physical | 70 | print peer_physical, "connects to", partner_physical |
71 | peer_type = "outgoing" | 71 | peer_type = "outgoing" |
72 | if peer_logical < num_ghosts: | 72 | if peer_logical < num_ghosts: |
73 | # we have a ghost, check if the peer who connects | 73 | # we have a ghost, check if the peer who connects |
74 | # to our ghost is actually outgoing | 74 | # to our ghost is actually outgoing |
75 | ghost_partner_logical = (peer_logical - arc) % n | 75 | ghost_partner_logical = (peer_logical - arc) % n |
76 | if ghost_partner_logical & arc == 0: | 76 | if ghost_partner_logical & arc == 0: |
77 | peer_type = peer_type + ", ghost incoming" | 77 | peer_type = peer_type + ", ghost incoming" |
78 | new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical] | 78 | new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical] |
79 | new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical] | 79 | new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical] |
80 | else: | 80 | else: |
81 | peer_type = "incoming" | 81 | peer_type = "incoming" |
82 | if verbose > 1: | 82 | if verbose > 1: |
83 | print "type of", str(peer_physical) + ":", peer_type | 83 | print "type of", str(peer_physical) + ":", peer_type |
84 | info = new_info | 84 | info = new_info |
85 | arc = arc << 1; | 85 | arc = arc << 1; |
86 | rounds = rounds + 1 | 86 | rounds = rounds + 1 |
87 | random.shuffle(peers) | 87 | random.shuffle(peers) |
88 | return rounds | 88 | return rounds |
89 | 89 | ||
90 | if __name__ == "__main__": | 90 | if __name__ == "__main__": |
91 | parser = argparse.ArgumentParser() | 91 | parser = argparse.ArgumentParser() |
92 | parser.add_argument("k", metavar="k", type=int, help="#(bad peers)") | 92 | parser.add_argument("k", metavar="k", type=int, help="#(bad peers)") |
93 | parser.add_argument("n", metavar="n", type=int, help="#(all peers)") | 93 | parser.add_argument("n", metavar="n", type=int, help="#(all peers)") |
94 | parser.add_argument("r", metavar="r", type=int, help="#(rounds)") | 94 | parser.add_argument("r", metavar="r", type=int, help="#(rounds)") |
95 | parser.add_argument('--verbose', '-v', action='count') | 95 | parser.add_argument('--verbose', '-v', action='count') |
96 | 96 | ||
97 | args = parser.parse_args() | 97 | args = parser.parse_args() |
98 | sum = 0.0; | 98 | sum = 0.0; |
99 | for n in xrange (0, args.r): | 99 | for n in xrange (0, args.r): |
100 | sum += simulate(args.k, args.n, args.verbose) | 100 | sum += simulate(args.k, args.n, args.verbose) |
101 | print sum / args.r; | 101 | print sum / args.r; |
102 | 102 | ||
103 | 103 | ||