Last active
February 13, 2018 02:38
-
-
Save spikeekips/ebf41bc1270ab6c8d7c354df267f73b4 to your computer and use it in GitHub Desktop.
Revisions
-
spikeekips revised this gist
Feb 13, 2018 . 1 changed file with 5 additions and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -44,6 +44,8 @@ Simply to say, `commons` is the shared nodes between quorums. > > Definition (safety). A set of nodes in an FBAS enjoy safety if no two of them ever externalize different values for the same slot. - From [The Stellar Consensus Protocol](https://www.stellar.org/papers/stellar-consensus-protocol.pdf) So we can simply get the number of nodes for satisfying `safety`. ``` @@ -57,6 +59,8 @@ So we can simply get the number of nodes for satisfying `safety`. > > Definition (liveness). A node in an FBAS enjoys liveness if it can externalize new values without the participation of any failed (including ill-behaved) nodes. - From [The Stellar Consensus Protocol](https://www.stellar.org/papers/stellar-consensus-protocol.pdf) `liveness` also can be calculated, ``` @@ -155,4 +159,4 @@ $ python check-quorums-are-stable.py 5 4 2 ............................................................................................................................................................................................................................................ liveness(a): {"FAULT": 3, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 3, "QUORUM": "b", "commons": 2, "has_liveness": false, "is_safety": false, "max_safety": 1, "size_of_nodes": 4} ``` -
Feb 13, 2018 . 1 changed file with 89 additions and 18 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,3 +1,72 @@ # Checking The Stability Of Two Quorums This script will simply do these, * set up and compose the 2 quorums automatically with given numbers, and the `commons`(shared nodes between 2 quorums) is also considered. * by the possible number of faulty nodes, checking and calculating these factors, * `safety` * `liveness` * minimum `threshold` I want to get the possible cases and by increasing the number of faulty nodes, how each factors are changed. ## Terminology ### `node` In this script, node will be limited to 'validator', which can participate to consensus process of network. ### `quorum` The paper, [The Stellar Consensus Protocol](https://www.stellar.org/papers/stellar-consensus-protocol.pdf) by David Mazie`res, explains like this, > Definition (quorum). A set of nodes `𝑈 ⊆ 𝐕` in FBAS `⟨𝐕,𝐐⟩` is a quorum iff `𝑈 ≠ ∅` and `𝑈` contains a slice for each member — i.e., `∀𝑣 ∈ 𝑈`, `∃𝑞 ∈ 𝐐(𝑣)` such that `𝑞 ⊆ 𝑈`. > A quorum is a set of nodes sufficient to reach agreement. `quorum slice` is the sufficient set of nodes for each node, but `quorum` is for the network-level. ### `commons` According to the [official documentation](https://www.stellar.org/developers/stellar-core/software/admin.html#quorum-intersection) of stellar.org, > For example, consider two nodes that respectively reference the sets Set1 and Set2 composed of some common nodes and some other nodes. > > Set1 = Common + extra1, Set2 = Common + extra2 Simply to say, `commons` is the shared nodes between quorums. ### `safety` > 3.3. Safety and liveness > > Definition (safety). A set of nodes in an FBAS enjoy safety if no two of them ever externalize different values for the same slot. So we can simply get the number of nodes for satisfying `safety`. ``` <commons> - 1 >= f ``` `f` is the number of faulty nodes, that is, safety nodes will be greater than faulty nodes. ### `liveness` > 3.3. Safety and liveness > > Definition (liveness). A node in an FBAS enjoys liveness if it can externalize new values without the participation of any failed (including ill-behaved) nodes. `liveness` also can be calculated, ``` <nodes in one quorum> - <commons> >= f ``` ### `threshold` `threshold` is the lowest number to reach agreement in one quorum. ## Installation ``` @@ -8,36 +77,38 @@ $ pip install pygments termcolor ``` $ python check-quorums-are-stable.py -h usage: check-quorums-are-stable.py [-h] qa qb commons Checking the stability of 2 quorums positional arguments: qa number of nodes in quorum, `a` qb number of nodes in quorum, `b` commons number of commons(shared nodes) between quorums, `a` and `b` optional arguments: -h, --help show this help message and exit ``` ## Check Stability Of Quorums ``` $ python check-quorums-are-stable.py 5 4 2 - quorums ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- a: {"count": 5, "quorum": ["v00", "v01", "v02", "v03", "v04"]} b: {"count": 4, "quorum": ["v03", "v04", "v05", "v06"]} commons: {"commons": ["v03", "v04"], "count": 2} - functions -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- fault tolerance: {"f": "<number of nodes> >= 3f + 1"} max safety: {"f": "<commons> - 1 >= f"} liveness: {"f": "<size of nodes> - <commons> >= f"} threshold: {"f": "<size of not commons> + <safety> / <size of nodes>: https://www.stellar.org/developers/stellar-core/software/admin.html#quorum-intersection"} or threshold: {"f": "1 - <commons p> + (<safety p> * <common p>)"} - etc -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- max fault: {"fault": 1} max safety: {"safety": 1} ============================================================================================================================================================================================================================================ - FAULT: 0 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 0, "commons": 2, "max_safety": 1} * safe_nodes: 2 @@ -49,11 +120,11 @@ $ python check-quorums-are-stable.py 5 4 2 safety(all): {"FAULT": 0, "is_safety": true, "max_safety": 1, "safe_nodes": 1, "safety": 0} min threshold(a): {"FAULT": 0, "QUORUM": "a", "commons": 2, "commons_p": 0.4, "max_safety": 1, "min_threshold": 0.8, "safe_nodes": 1, "safety_p": 0.5} min threshold(b): {"FAULT": 0, "QUORUM": "b", "commons": 2, "commons_p": 0.5, "max_safety": 1, "min_threshold": 0.75, "safe_nodes": 1, "safety_p": 0.5} ............................................................................................................................................................................................................................................ liveness(a): {"FAULT": 0, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": true, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 0, "QUORUM": "b", "commons": 2, "has_liveness": true, "is_safety": true, "max_safety": 1, "size_of_nodes": 4} - FAULT: 1 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 1, "commons": 2, "max_safety": 1} * safe_nodes: 2 @@ -63,25 +134,25 @@ $ python check-quorums-are-stable.py 5 4 2 * safe_nodes: 1 safety(all): {"FAULT": 1, "is_safety": false, "max_safety": 1, "safe_nodes": 1, "safety": 0} ............................................................................................................................................................................................................................................ liveness(a): {"FAULT": 1, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 1, "QUORUM": "b", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 4} - FAULT: 2 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 2, "commons": 2, "max_safety": 1} * safe_nodes: 2 safety(all): {"FAULT": 2, "is_safety": false, "max_safety": 1, "safe_nodes": 2, "safety": 1} ............................................................................................................................................................................................................................................ liveness(a): {"FAULT": 2, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 2, "QUORUM": "b", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 4} - FAULT: 3 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 3, "commons": 2, "max_safety": 1} * safe_nodes: 2 safety(all): {"FAULT": 3, "is_safety": false, "max_safety": 1, "safe_nodes": 2, "safety": 1} ............................................................................................................................................................................................................................................ liveness(a): {"FAULT": 3, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 3, "QUORUM": "b", "commons": 2, "has_liveness": false, "is_safety": false, "max_safety": 1, "size_of_nodes": 4} ``` -
Feb 12, 2018 . 1 changed file with 87 additions and 0 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,87 @@ ## Installation ``` $ pip install pygments termcolor ``` ## Usage ``` $ python check-quorums-are-stable.py -h usage: check-quorums-are-stable.py [-h] na nb commons positional arguments: na number of nodes in quorum `a` nb number of nodes in quorum `b` commons number of common nodes optional arguments: -h, --help show this help message and exit ``` ## Check Quorums ``` $ python check-quorums-are-stable.py 5 4 2 - quorums --------------------------------------------------------------------------------------------- a: {"count": 5, "quorum": ["v00", "v01", "v02", "v03", "v04"]} b: {"count": 4, "quorum": ["v03", "v04", "v05", "v06"]} commons: {"commons": ["v03", "v04"], "count": 2} - functions ------------------------------------------------------------------------------------------- fault tolerance: {"f": "<number of nodes> >= 3f + 1"} max safety: {"f": "<commons> - 1 >= f"} liveness: {"f": "<size of nodes> - <commons> >= f"} threshold: {"f": "<size of not commons> + <safety> / <size of nodes>: https://www.stellar.org/developers/stellar-core/software/admin.html#quorum-intersection"} or threshold: {"f": "1 - <commons p> + (<safety p> * <common p>)"} - etc ------------------------------------------------------------------------------------------------- max fault: {"fault": 1} max safety: {"safety": 1} ======================================================================================================= - FAULT: 0 -------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 0, "commons": 2, "max_safety": 1} * safe_nodes: 2 safety(all): {"FAULT": 0, "is_safety": true, "max_safety": 1, "safe_nodes": 2, "safety": 1} min threshold(a): {"FAULT": 0, "QUORUM": "a", "commons": 2, "commons_p": 0.4, "max_safety": 1, "min_threshold": 1.0, "safe_nodes": 2, "safety_p": 1.0} min threshold(b): {"FAULT": 0, "QUORUM": "b", "commons": 2, "commons_p": 0.5, "max_safety": 1, "min_threshold": 1.0, "safe_nodes": 2, "safety_p": 1.0} * safe_nodes: 1 safety(all): {"FAULT": 0, "is_safety": true, "max_safety": 1, "safe_nodes": 1, "safety": 0} min threshold(a): {"FAULT": 0, "QUORUM": "a", "commons": 2, "commons_p": 0.4, "max_safety": 1, "min_threshold": 0.8, "safe_nodes": 1, "safety_p": 0.5} min threshold(b): {"FAULT": 0, "QUORUM": "b", "commons": 2, "commons_p": 0.5, "max_safety": 1, "min_threshold": 0.75, "safe_nodes": 1, "safety_p": 0.5} ....................................................................................................... liveness(a): {"FAULT": 0, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": true, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 0, "QUORUM": "b", "commons": 2, "has_liveness": true, "is_safety": true, "max_safety": 1, "size_of_nodes": 4} - FAULT: 1 -------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 1, "commons": 2, "max_safety": 1} * safe_nodes: 2 safety(all): {"FAULT": 1, "is_safety": true, "max_safety": 1, "safe_nodes": 2, "safety": 1} min threshold(a): {"FAULT": 1, "QUORUM": "a", "commons": 2, "commons_p": 0.4, "max_safety": 1, "min_threshold": 0.8, "safe_nodes": 1, "safety_p": 0.5} min threshold(b): {"FAULT": 1, "QUORUM": "b", "commons": 2, "commons_p": 0.5, "max_safety": 1, "min_threshold": 0.75, "safe_nodes": 1, "safety_p": 0.5} * safe_nodes: 1 safety(all): {"FAULT": 1, "is_safety": false, "max_safety": 1, "safe_nodes": 1, "safety": 0} ....................................................................................................... liveness(a): {"FAULT": 1, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 1, "QUORUM": "b", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 4} - FAULT: 2 -------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 2, "commons": 2, "max_safety": 1} * safe_nodes: 2 safety(all): {"FAULT": 2, "is_safety": false, "max_safety": 1, "safe_nodes": 2, "safety": 1} ....................................................................................................... liveness(a): {"FAULT": 2, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 2, "QUORUM": "b", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 4} - FAULT: 3 -------------------------------------------------------------------------------------------- max_safety(all): {"FAULT": 3, "commons": 2, "max_safety": 1} * safe_nodes: 2 safety(all): {"FAULT": 3, "is_safety": false, "max_safety": 1, "safe_nodes": 2, "safety": 1} ....................................................................................................... liveness(a): {"FAULT": 3, "QUORUM": "a", "commons": 2, "has_liveness": true, "is_safety": false, "max_safety": 1, "size_of_nodes": 5} liveness(b): {"FAULT": 3, "QUORUM": "b", "commons": 2, "has_liveness": false, "is_safety": false, "max_safety": 1, "size_of_nodes": 4} ``` -
Feb 12, 2018 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,193 @@ import argparse import collections import json import os import pygments import pygments.lexers import pygments.formatters from termcolor import colored, cprint import math import sys # noqa _, _TERMINAL_COLUMNS = os.popen('stty size', 'r').read().split() TERMINAL_COLUMNS = int(_TERMINAL_COLUMNS) def print_line(h, c='-', color=None): if h is None: print(c * TERMINAL_COLUMNS) return s = h if color is not None: s = colored(h, color=color) print(c, s, c * (TERMINAL_COLUMNS - len(h) - 3)) return def print_metric(h, **kw): color = None for k, v in kw.copy().items(): if type(v) in (float,): kw[k] = float('%.2f' % v) continue if k.startswith('_is_') or k.startswith('_has_'): kw[k[1:]] = v del kw[k] elif not k.startswith('is_') and not k.startswith('has_'): continue if not v: color = 'red' formatted_json = json.dumps(kw, sort_keys=True) if h is not None and len(h) > 0: print('%20s:' % h, end=' ') if color is None: colorful_json = pygments.highlight( formatted_json, pygments.lexers.JsonLexer(), pygments.formatters.TerminalFormatter(), ) print(colorful_json, end='') return cprint(formatted_json, color) return def check_quorums(a, b): qs = collections.namedtuple('QuorumSet', ('a', 'b'))(set(a), set(b)) commons = qs.a & qs.b print_line('quorums') print_metric('a', count=len(qs.a), quorum=sorted(qs.a)) print_metric('b', count=len(qs.b), quorum=sorted(qs.b)) print_metric('commons', count=len(commons), commons=sorted(commons)) print_line('functions') print_metric('fault tolerance', f='<number of nodes> >= 3f + 1') print_metric('max safety', f='<commons> - 1 >= f') print_metric('liveness', f='<size of nodes> - <commons> >= f') print_metric( 'threshold', f='<size of not commons> + <safety> / <size of nodes>: https://www.stellar.org/developers/stellar-core/software/admin.html#quorum-intersection', # noqa ) print_metric('or threshold', f='1 - <commons p> + (<safety p> * <common p>)') print_line('etc') max_f = min(math.ceil((len(q0) - 1) / 3), math.ceil((len(q1) - 1) / 3)) print_metric('max fault', fault=max_f) print_metric('max safety', safety=len(commons) - max_f) print_line(None, c='=') f = 0 while True: print_line('FAULT: %d' % f, color='green') # check safety max_safety = len(commons) - 1 print_metric( 'max_safety(all)', max_safety=max_safety, FAULT=f, commons=len(commons), ) safe_nodes = max_safety + 1 while safe_nodes >= 1: print() cprint('%3s* safe_nodes: %d' % ('', safe_nodes), 'magenta') is_safety = safe_nodes - 1 >= f print_metric( 'safety(all)', safe_nodes=safe_nodes, safety=safe_nodes - 1, FAULT=f, is_safety=is_safety, max_safety=max_safety, ) if not is_safety: break if safe_nodes - f >= 0: for name in ('a', 'b'): q = getattr(qs, name) safetyP = (safe_nodes - f) / len(commons) commonP = len(commons) / len(q) min_threshold = 1 - (1 - safetyP) * commonP print_metric( 'min threshold(%s)' % name, min_threshold=min_threshold, safe_nodes=safe_nodes - f, commons=len(commons), safety_p=safetyP, commons_p=commonP, QUORUM=name, max_safety=max_safety, FAULT=f, ) safe_nodes -= 1 print_line(None, c='.') for name in ('a', 'b'): q = getattr(qs, name) liveness_fault = len(q) - len(commons) has_liveness = liveness_fault >= f print_metric( 'liveness(%s)' % name, has_liveness=has_liveness, _is_safety=is_safety, size_of_nodes=len(q), commons=len(commons), FAULT=f, QUORUM=name, max_safety=max_safety, ) if not is_safety and not has_liveness: break f += 1 print() return parser = argparse.ArgumentParser(formatter_class=argparse.ArgumentDefaultsHelpFormatter) parser.add_argument('na', type=int, help='number of nodes in quorum `a`') parser.add_argument('nb', type=int, help='number of nodes in quorum `b`') parser.add_argument('commons', type=int, help='number of common nodes') if __name__ == '__main__': options = parser.parse_args() q0 = tuple(map(lambda x: 'v%02d' % x, range(options.na))) q1 = tuple(map( lambda x: 'v%02d' % x, range(options.na - options.commons, options.na - options.commons + options.nb), )) check_quorums(q0, q1)