diff options
Diffstat (limited to 'src/consensus/consensus-simulation.py.in')
-rw-r--r-- | src/consensus/consensus-simulation.py.in | 143 |
1 files changed, 72 insertions, 71 deletions
diff --git a/src/consensus/consensus-simulation.py.in b/src/consensus/consensus-simulation.py.in index fbad9f678..12bef871d 100644 --- a/src/consensus/consensus-simulation.py.in +++ b/src/consensus/consensus-simulation.py.in | |||
@@ -25,82 +25,83 @@ from math import ceil, log, floor | |||
25 | 25 | ||
26 | 26 | ||
27 | def bsc(n): | 27 | def bsc(n): |
28 | """ count the bits set in n""" | 28 | """ count the bits set in n""" |
29 | l = n.bit_length() | 29 | l = n.bit_length() |
30 | c = 0 | 30 | c = 0 |
31 | x = 1 | 31 | x = 1 |
32 | for _ in range(0, l): | 32 | for _ in range(0, l): |
33 | if n & x: | 33 | if n & x: |
34 | c = c + 1 | 34 | c = c + 1 |
35 | x = x << 1 | 35 | x = x << 1 |
36 | return c | 36 | return c |
37 | 37 | ||
38 | 38 | ||
39 | def simulate(k, n, verbose): | 39 | def simulate(k, n, verbose): |
40 | assert k < n | 40 | assert k < n |
41 | largest_arc = int(2**ceil(log(n, 2))) / 2 | 41 | largest_arc = int(2**ceil(log(n, 2))) / 2 |
42 | num_ghosts = (2 * largest_arc) - n | 42 | num_ghosts = (2 * largest_arc) - n |
43 | if verbose: | ||
44 | print("we have", num_ghosts, "ghost peers") | ||
45 | # n.b. all peers with idx<k are evil | ||
46 | peers = range(n) | ||
47 | info = [1 << x for x in xrange(n)] | ||
48 | def done_p(): | ||
49 | for x in xrange(k, n): | ||
50 | if bsc(info[x]) < n-k: | ||
51 | return False | ||
52 | return True | ||
53 | rounds = 0 | ||
54 | while not done_p(): | ||
55 | if verbose: | 43 | if verbose: |
56 | print("-- round --") | 44 | print("we have", num_ghosts, "ghost peers") |
57 | arc = 1 | 45 | # n.b. all peers with idx<k are evil |
58 | while arc <= largest_arc: | 46 | peers = range(n) |
59 | if verbose: | 47 | info = [1 << x for x in xrange(n)] |
60 | print("-- subround --") | 48 | |
61 | new_info = [x for x in info] | 49 | def done_p(): |
62 | for peer_physical in xrange(n): | 50 | for x in xrange(k, n): |
63 | peer_logical = peers[peer_physical] | 51 | if bsc(info[x]) < n-k: |
64 | peer_type = None | 52 | return False |
65 | partner_logical = (peer_logical + arc) % n | 53 | return True |
66 | partner_physical = peers.index(partner_logical) | 54 | rounds = 0 |
67 | if peer_physical < k or partner_physical < k: | 55 | while not done_p(): |
68 | if verbose: | 56 | if verbose: |
69 | print("bad peer in connection", peer_physical, "--", partner_physical) | 57 | print("-- round --") |
70 | continue | 58 | arc = 1 |
71 | if peer_logical & arc == 0: | 59 | while arc <= largest_arc: |
72 | # we are outgoing | 60 | if verbose: |
73 | if verbose: | 61 | print("-- subround --") |
74 | print(peer_physical, "connects to", partner_physical) | 62 | new_info = [x for x in info] |
75 | peer_type = "outgoing" | 63 | for peer_physical in xrange(n): |
76 | if peer_logical < num_ghosts: | 64 | peer_logical = peers[peer_physical] |
77 | # we have a ghost, check if the peer who connects | 65 | peer_type = None |
78 | # to our ghost is actually outgoing | 66 | partner_logical = (peer_logical + arc) % n |
79 | ghost_partner_logical = (peer_logical - arc) % n | 67 | partner_physical = peers.index(partner_logical) |
80 | if ghost_partner_logical & arc == 0: | 68 | if peer_physical < k or partner_physical < k: |
81 | peer_type = peer_type + ", ghost incoming" | 69 | if verbose: |
82 | new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical] | 70 | print("bad peer in connection", peer_physical, "--", partner_physical) |
83 | new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical] | 71 | continue |
84 | else: | 72 | if peer_logical & arc == 0: |
85 | peer_type = "incoming" | 73 | # we are outgoing |
86 | if verbose > 1: | 74 | if verbose: |
87 | print("type of", str(peer_physical) + ":", peer_type) | 75 | print(peer_physical, "connects to", partner_physical) |
88 | info = new_info | 76 | peer_type = "outgoing" |
89 | arc = arc << 1 | 77 | if peer_logical < num_ghosts: |
90 | rounds = rounds + 1 | 78 | # we have a ghost, check if the peer who connects |
91 | random.shuffle(peers) | 79 | # to our ghost is actually outgoing |
92 | return rounds | 80 | ghost_partner_logical = (peer_logical - arc) % n |
81 | if ghost_partner_logical & arc == 0: | ||
82 | peer_type = peer_type + ", ghost incoming" | ||
83 | new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical] | ||
84 | new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical] | ||
85 | else: | ||
86 | peer_type = "incoming" | ||
87 | if verbose > 1: | ||
88 | print("type of", str(peer_physical) + ":", peer_type) | ||
89 | info = new_info | ||
90 | arc = arc << 1 | ||
91 | rounds = rounds + 1 | ||
92 | random.shuffle(peers) | ||
93 | return rounds | ||
93 | 94 | ||
94 | 95 | ||
95 | if __name__ == "__main__": | 96 | if __name__ == "__main__": |
96 | parser = argparse.ArgumentParser() | 97 | parser = argparse.ArgumentParser() |
97 | parser.add_argument("k", metavar="k", type=int, help="#(bad peers)") | 98 | parser.add_argument("k", metavar="k", type=int, help="#(bad peers)") |
98 | parser.add_argument("n", metavar="n", type=int, help="#(all peers)") | 99 | parser.add_argument("n", metavar="n", type=int, help="#(all peers)") |
99 | parser.add_argument("r", metavar="r", type=int, help="#(rounds)") | 100 | parser.add_argument("r", metavar="r", type=int, help="#(rounds)") |
100 | parser.add_argument('--verbose', '-v', action='count') | 101 | parser.add_argument('--verbose', '-v', action='count') |
101 | 102 | ||
102 | args = parser.parse_args() | 103 | args = parser.parse_args() |
103 | sum = 0.0 | 104 | sum = 0.0 |
104 | for n in xrange(0, args.r): | 105 | for n in xrange(0, args.r): |
105 | sum += simulate(args.k, args.n, args.verbose) | 106 | sum += simulate(args.k, args.n, args.verbose) |
106 | print(sum / args.r) | 107 | print(sum / args.r) |