diff options
Diffstat (limited to 'src/consensus')
-rw-r--r-- | src/consensus/.gitignore | 1 | ||||
-rw-r--r-- | src/consensus/Makefile.am | 20 | ||||
-rw-r--r-- | src/consensus/consensus-simulation.py | 108 | ||||
-rw-r--r-- | src/consensus/consensus-simulation.py.in | 110 |
4 files changed, 130 insertions, 109 deletions
diff --git a/src/consensus/.gitignore b/src/consensus/.gitignore index d49147d17..8050d760e 100644 --- a/src/consensus/.gitignore +++ b/src/consensus/.gitignore | |||
@@ -3,3 +3,4 @@ gnunet-consensus-profiler | |||
3 | gnunet-service-consensus | 3 | gnunet-service-consensus |
4 | test_consensus_api | 4 | test_consensus_api |
5 | resource.log.master | 5 | resource.log.master |
6 | consensus-simulation.py | ||
diff --git a/src/consensus/Makefile.am b/src/consensus/Makefile.am index c0205ee5d..991e36a95 100644 --- a/src/consensus/Makefile.am +++ b/src/consensus/Makefile.am | |||
@@ -27,6 +27,17 @@ libexec_PROGRAMS += \ | |||
27 | gnunet-service-evil-consensus | 27 | gnunet-service-evil-consensus |
28 | endif | 28 | endif |
29 | 29 | ||
30 | do_subst = $(SED) -e 's,[@]PYTHON[@],$(PYTHON),g' | ||
31 | |||
32 | SUFFIXES = .py.in .py | ||
33 | |||
34 | .py.in.py: | ||
35 | $(do_subst) < $< > $@ | ||
36 | chmod +x $@ | ||
37 | |||
38 | check-python-style: | ||
39 | flake8 consensus-simulation.py.in | ||
40 | |||
30 | lib_LTLIBRARIES = \ | 41 | lib_LTLIBRARIES = \ |
31 | libgnunetconsensus.la | 42 | libgnunetconsensus.la |
32 | 43 | ||
@@ -103,5 +114,12 @@ test_consensus_api_LDADD = \ | |||
103 | $(top_builddir)/src/testing/libgnunettesting.la \ | 114 | $(top_builddir)/src/testing/libgnunettesting.la \ |
104 | libgnunetconsensus.la | 115 | libgnunetconsensus.la |
105 | 116 | ||
117 | noinst_SCRIPTS = \ | ||
118 | consensus-simulation.py | ||
119 | |||
120 | CLEANFILES = \ | ||
121 | $(noinst_SCRIPTS) | ||
122 | |||
106 | EXTRA_DIST = \ | 123 | EXTRA_DIST = \ |
107 | test_consensus.conf | 124 | test_consensus.conf \ |
125 | consensus-simulation.py.in | ||
diff --git a/src/consensus/consensus-simulation.py b/src/consensus/consensus-simulation.py deleted file mode 100644 index 542fe0dac..000000000 --- a/src/consensus/consensus-simulation.py +++ /dev/null | |||
@@ -1,108 +0,0 @@ | |||
1 | #!/usr/bin/python | ||
2 | # This file is part of GNUnet | ||
3 | # (C) 2013 Christian Grothoff (and other contributing authors) | ||
4 | # | ||
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 | ||
7 | # by the Free Software Foundation; either version 2, or (at your | ||
8 | # option) any later version. | ||
9 | # | ||
10 | # GNUnet is distributed in the hope that it will be useful, but | ||
11 | # WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | # General Public License for more details. | ||
14 | # | ||
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 | ||
17 | # Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | ||
18 | # Boston, MA 02110-1301, USA. | ||
19 | |||
20 | from __future__ import absolute_import | ||
21 | from __future__ import print_function | ||
22 | import argparse | ||
23 | import random | ||
24 | from math import ceil,log,floor | ||
25 | |||
26 | |||
27 | def bsc(n): | ||
28 | """ count the bits set in n""" | ||
29 | l = n.bit_length() | ||
30 | c = 0 | ||
31 | x = 1 | ||
32 | for _ in range(0, l): | ||
33 | if n & x: | ||
34 | c = c + 1 | ||
35 | x = x << 1 | ||
36 | return c | ||
37 | |||
38 | |||
39 | def simulate(k, n, verbose): | ||
40 | assert k < n | ||
41 | largest_arc = int(2**ceil(log(n, 2))) / 2 | ||
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: | ||
56 | print "-- round --" | ||
57 | arc = 1 | ||
58 | while arc <= largest_arc: | ||
59 | if verbose: | ||
60 | print "-- subround --" | ||
61 | new_info = [x for x in info] | ||
62 | for peer_physical in xrange(n): | ||
63 | peer_logical = peers[peer_physical] | ||
64 | peer_type = None | ||
65 | partner_logical = (peer_logical + arc) % n | ||
66 | partner_physical = peers.index(partner_logical) | ||
67 | if peer_physical < k or partner_physical < k: | ||
68 | if verbose: | ||
69 | print "bad peer in connection", peer_physical, "--", partner_physical | ||
70 | continue | ||
71 | if peer_logical & arc == 0: | ||
72 | # we are outgoing | ||
73 | if verbose: | ||
74 | print peer_physical, "connects to", partner_physical | ||
75 | peer_type = "outgoing" | ||
76 | if peer_logical < num_ghosts: | ||
77 | # we have a ghost, check if the peer who connects | ||
78 | # to our ghost is actually outgoing | ||
79 | ghost_partner_logical = (peer_logical - arc) % n | ||
80 | if ghost_partner_logical & arc == 0: | ||
81 | peer_type = peer_type + ", ghost incoming" | ||
82 | new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical] | ||
83 | new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical] | ||
84 | else: | ||
85 | peer_type = "incoming" | ||
86 | if verbose > 1: | ||
87 | print "type of", str(peer_physical) + ":", peer_type | ||
88 | info = new_info | ||
89 | arc = arc << 1; | ||
90 | rounds = rounds + 1 | ||
91 | random.shuffle(peers) | ||
92 | return rounds | ||
93 | |||
94 | |||
95 | if __name__ == "__main__": | ||
96 | parser = argparse.ArgumentParser() | ||
97 | 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("r", metavar="r", type=int, help="#(rounds)") | ||
100 | parser.add_argument('--verbose', '-v', action='count') | ||
101 | |||
102 | args = parser.parse_args() | ||
103 | sum = 0.0; | ||
104 | for n in xrange (0, args.r): | ||
105 | sum += simulate(args.k, args.n, args.verbose) | ||
106 | printsum / args.r; | ||
107 | |||
108 | |||
diff --git a/src/consensus/consensus-simulation.py.in b/src/consensus/consensus-simulation.py.in new file mode 100644 index 000000000..6629ffaa8 --- /dev/null +++ b/src/consensus/consensus-simulation.py.in | |||
@@ -0,0 +1,110 @@ | |||
1 | #!@PYTHON@ | ||
2 | # This file is part of GNUnet | ||
3 | # (C) 2013, 2018 Christian Grothoff (and other contributing authors) | ||
4 | # | ||
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 | ||
7 | # by the Free Software Foundation; either version 2, or (at your | ||
8 | # option) any later version. | ||
9 | # | ||
10 | # GNUnet is distributed in the hope that it will be useful, but | ||
11 | # WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | # General Public License for more details. | ||
14 | # | ||
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 | ||
17 | # Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | ||
18 | # Boston, MA 02110-1301, USA. | ||
19 | |||
20 | from __future__ import absolute_import | ||
21 | from __future__ import print_function | ||
22 | import argparse | ||
23 | import random | ||
24 | from math import ceil, log, floor | ||
25 | from past.builtins import xrange | ||
26 | |||
27 | |||
28 | def bsc(n): | ||
29 | """ count the bits set in n""" | ||
30 | l = n.bit_length() | ||
31 | c = 0 | ||
32 | x = 1 | ||
33 | for _ in range(0, l): | ||
34 | if n & x: | ||
35 | c = c + 1 | ||
36 | x = x << 1 | ||
37 | return c | ||
38 | |||
39 | |||
40 | def simulate(k, n, verbose): | ||
41 | assert k < n | ||
42 | largest_arc = int(2**ceil(log(n, 2))) / 2 | ||
43 | num_ghosts = (2 * largest_arc) - n | ||
44 | if verbose: | ||
45 | print("we have", num_ghosts, "ghost peers") | ||
46 | # n.b. all peers with idx<k are evil | ||
47 | peers = range(n) | ||
48 | # py2-3 compatible, backwards. | ||
49 | # refer to http://python-future.org/compatible_idioms.html#xrange | ||
50 | info = [1 << x for x in xrange(n)] | ||
51 | |||
52 | def done_p(): | ||
53 | for x in xrange(k, n): | ||
54 | if bsc(info[x]) < n-k: | ||
55 | return False | ||
56 | return True | ||
57 | rounds = 0 | ||
58 | while not done_p(): | ||
59 | if verbose: | ||
60 | print("-- round --") | ||
61 | arc = 1 | ||
62 | while arc <= largest_arc: | ||
63 | if verbose: | ||
64 | print("-- subround --") | ||
65 | new_info = [x for x in info] | ||
66 | for peer_physical in xrange(n): | ||
67 | peer_logical = peers[peer_physical] | ||
68 | peer_type = None | ||
69 | partner_logical = (peer_logical + arc) % n | ||
70 | partner_physical = peers.index(partner_logical) | ||
71 | if peer_physical < k or partner_physical < k: | ||
72 | if verbose: | ||
73 | print("bad peer in connection", peer_physical, "--", partner_physical) | ||
74 | continue | ||
75 | if peer_logical & arc == 0: | ||
76 | # we are outgoing | ||
77 | if verbose: | ||
78 | print(peer_physical, "connects to", partner_physical) | ||
79 | peer_type = "outgoing" | ||
80 | if peer_logical < num_ghosts: | ||
81 | # we have a ghost, check if the peer who connects | ||
82 | # to our ghost is actually outgoing | ||
83 | ghost_partner_logical = (peer_logical - arc) % n | ||
84 | if ghost_partner_logical & arc == 0: | ||
85 | peer_type = peer_type + ", ghost incoming" | ||
86 | new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical] | ||
87 | new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical] | ||
88 | else: | ||
89 | peer_type = "incoming" | ||
90 | if verbose > 1: | ||
91 | print("type of", str(peer_physical) + ":", peer_type) | ||
92 | info = new_info | ||
93 | arc = arc << 1 | ||
94 | rounds = rounds + 1 | ||
95 | random.shuffle(peers) | ||
96 | return rounds | ||
97 | |||
98 | |||
99 | if __name__ == "__main__": | ||
100 | parser = argparse.ArgumentParser() | ||
101 | parser.add_argument("k", metavar="k", type=int, help="#(bad peers)") | ||
102 | parser.add_argument("n", metavar="n", type=int, help="#(all peers)") | ||
103 | parser.add_argument("r", metavar="r", type=int, help="#(rounds)") | ||
104 | parser.add_argument('--verbose', '-v', action='count') | ||
105 | |||
106 | args = parser.parse_args() | ||
107 | sum = 0.0 | ||
108 | for n in xrange(0, args.r): | ||
109 | sum += simulate(args.k, args.n, args.verbose) | ||
110 | print(sum / args.r) | ||