Crate fbas_analyzer

A library and tool for analyzing the quorum structure of federated byzantine agreement systems (FBASs) like Stellar. Related research paper here.

We recommend using the Analysis struct for doing analyses.

Example analysis

We will load a simple FBAS from the test_data folder. We will not use an organizations file; analyses will be based on raw nodes.

use fbas_analyzer::{Fbas, Analysis, bitset, bitsetvec};

let fbas = Fbas::from_json_file(std::path::Path::new("test_data/correct.json"));
let analysis = Analysis::new(&fbas, None);

assert!(analysis.has_quorum_intersection());

// "Unwrapping" analysis results gives us their internal representation, with node IDs
// corresponding to node indices in the input JSON.
assert_eq!(bitsetvec![{0,1},{0,10},{1,10}], analysis.minimal_blocking_sets().unwrap());
assert_eq!(bitsetvec![{0},{1},{10}], analysis.minimal_splitting_sets().unwrap());
assert_eq!(bitset!{0,1,10}, analysis.top_tier().unwrap());

// You can also serialize results using serde.
assert_eq!(
    "[[0,1],[0,10],[1,10]]",
    serde_json::to_string(&analysis.minimal_blocking_sets()).unwrap()
);

Modules

simulation

Macros

bitset	Create a BitSet from a list of elements.
bitsetvec	Create a Vec<BitSet> from a list of sets.
timed	Measure the time it takes for an operation to complete (as Duration).
timed_secs	Measure the time it takes for an operation to complete (in seconds, as f64).

Structs

Analysis	Front end for the most interesting FBAS analyses. Among other things, it does ID space shrinking (which improves memory and performance when using bit sets) and caches the results of long-running computations.
Duration	A Duration type to represent a span of time, typically used for system timeouts.
Fbas
Instant	A measurement of a monotonically nondecreasing clock. Opaque and useful only with Duration.
NodeIdSetResult	Wraps a node ID set.
NodeIdSetVecResult	Wraps a vector of node ID sets. Node ID sets are stored in shrunken form to preserve memory.
Organizations
QuorumSet

Traits

AnalysisResult

Functions

all_intersect
contains_only_minimal_node_sets
find_minimal_blocking_sets
find_minimal_quorums	Find all minimal quorums in the FBAS...
find_minimal_splitting_sets
find_nonintersecting_quorums	Find at least two non-intersecting quorums. Use this function if it is very likely that the FBAS lacks quorum intersection and you want to stop early in such cases.
find_symmetric_clusters	Finds groups of nodes (represented as quorum sets) such that all members of the same group have the exact identical quorum set, and the nodes contained in this quorum set are exactly the group of nodes (a symmetric cluster). Once no more such clusters are found, returns the maximum quorum of the remaining nodes. (So, getting a result with more than 1 entry implies that we don't have quorum intersection.)
involved_nodes
remove_non_minimal_node_sets	Reduce to minimal node sets, i.e. to a set of node sets so that no member set is a superset of another.

Type Definitions

NodeId
NodeIdSet