Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Checking the stability fo two quorums in SCP(FBA)

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 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 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

$ pip install pygments termcolor

Usage

$ 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
         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}
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment