Quoracle

A Rust library for constructing and analyzing read-write quorum systems used in distributed systems research.

Features

• Expression algebra for defining quorum systems using operators (OR, AND, Choose)
• Linear programming-based optimization for finding optimal read/write strategies
• Multi-metric analysis including load, capacity, network overhead, and latency
• Resilience calculation for fault tolerance analysis
• Heuristic search for discovering optimal quorum configurations

Installation

Add this to your Cargo.toml:

[dependencies]
quoracle = "1.4"

The default uses the Microlp solver (pure Rust, silent output). For alternatives, see SOLVERS.md.

Quick Start

use quoracle::*;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Define node expressions.
    let a = Expr::Node(Node::new("a"));
    let b = Expr::Node(Node::new("b"));
    let c = Expr::Node(Node::new("c"));

    // Build a quorum system where reads need any single node
    // and writes (the dual) need all nodes.
    let qs = QuorumSystem::from_reads(a + b + c);

    // Find the load-optimal strategy for a 50% read workload.
    let fr = Distribution::fixed(0.5)?;
    let limits = StrategyLimits::default();
    let strategy = qs.strategy(
        Objective::Load, // Minimize load
        Some(&fr),       // Read fraction
        None,            // Write fraction (inferred from reads)
        &limits,         // Optional load/network/latency limits
        0,               // f-resilience
    )?;

    // Calculate load.
    let load = strategy.load(Some(&fr), None)?;
    println!("Load: {load:.4}");
    Ok(())
}

Development

Building

# Build the library
cargo build --lib

# Check code without building
cargo check

# Run clippy linter
cargo clippy --all-targets --all-features

# Generate documentation
cargo doc --no-deps --open

Testing

# Run all tests (155 total)
cargo test

# Results:
# - 118 unit tests: ✅ all pass
# - 36 integration tests: ✅ all pass
# - 1 doc test: ✅ pass

Examples

Simple Example - Basic quorum system usage

cargo run --example simple

Output shows grid quorum system with resilience calculation and load optimization.

Tutorial Example - Comprehensive walkthrough

cargo run --example tutorial

Covers all major features including heterogeneous nodes and latency optimization.

Search Example - Heuristic search for optimal systems

cargo run --example search

Demonstrates automated search for optimal 4-node configurations.

Benchmarking

# Run benchmarks
cargo bench --bench benchmarks

# Compare with Python implementation
cd _
pip install -r requirements.txt
python benchmarks.py

See BENCHMARKS.md for benchmarking methodology and COMPARISON.md for detailed Rust vs Python performance analysis.

Performance

The Rust implementation provides significant performance improvements over the Python version:

• 3-10× faster for quorum enumeration and iteration
• 2-10× faster for load calculations
• 3-10× faster for heuristic search
• ~1.5× faster for LP optimization (measured with the CBC backend)

See PERFORMANCE.md for measured results and COMPARISON.md for detailed Rust vs Python analysis.

Documentation

Full API documentation is available:

cargo doc --no-deps --open

Or view online at docs.rs/quoracle (when published).

Project Structure

quoracle/
├── src/
│   ├── lib.rs              # Public API exports
│   ├── expr.rs             # Expression algebra (Node, Or, And, Choose)
│   ├── quorum_system.rs    # QuorumSystem and Strategy
│   ├── distribution.rs     # Workload distribution types
│   ├── geometry.rs         # Point/Segment for piecewise functions
│   ├── search.rs           # Heuristic search
│   ├── lp.rs              # LP solver abstraction
│   └── error.rs           # Error types
├── tests/                  # Integration tests
├── benches/               # Performance benchmarks
├── examples/              # Usage examples
└── _/                     # Python reference implementation

Implementation Notes

• ~2,800 lines of library code across 7 modules (plus tests)
• 155 tests (118 unit + 36 integration + 1 doc, all passing)
• Zero clippy warnings with strict lints (unsafe_code forbidden)
• Uses the Microlp LP solver by default (pure Rust); CBC available via the cbc feature
• Type-safe generics with Element trait
• BTreeMap-based quorum storage for hashability

Comparison with Python Version

Both implementations:

• Use identical algorithms
• Are production-ready
• Have comprehensive tests

The Rust implementation defaults to the pure-Rust Microlp solver, with CBC available via the cbc feature; the Python implementation uses CBC.

Future Work

While Quoracle focuses on read-write quorum systems, related research areas exist:

Chain Replication (Out of Scope)

Chain replication (e.g., Machi, Hibari) provides linearizable distributed storage through ordered replica chains. While powerful, chain replication is fundamentally incompatible with quorum-based approaches:

• Chains: Ordered replicas (head/tail roles), sequential updates, single-node reads
• Quorums: Unordered replicas, parallel operations, set-based reads/writes

Modeling chains as degenerate quorums would lose essential chain semantics (ordering, linearizability guarantees). Each approach is optimal for different use cases and should be analyzed with purpose-built tools.

Potential Extensions

Potential future work within the quorum system domain:

• Custom optimization metrics beyond load/capacity/latency
• Network topology awareness (per-link costs)
• Dynamic reconfiguration support
• Extended heterogeneous node modeling

Contributing

Contributions welcome! Please ensure:

• All tests pass: cargo test
• No clippy warnings: cargo clippy --all-targets --all-features
• Code is formatted: cargo fmt

License

MIT OR Apache-2.0