Checking the stability fo two quorums in SCP(FBA)

README.md

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.

• From The Stellar Consensus Protocol

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.

• From The Stellar Consensus Protocol

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}

check-quorums-are-stable.py

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)