Crate antichain 

A coordinator-free primitive for tracking distributed progress using lattice algebra.

Overview

This crate provides three core primitives:

• Lattice — a trait for types with a greatest lower bound (meet) and least upper bound (join), consistent with PartialOrd.
• Antichain<T> — a set of mutually incomparable elements maintaining the antichain invariant: no element is <= any other.
• Frontier<T> — a progress claim: all timestamps strictly less than some antichain element are considered complete.

Two composition types are also provided:

• ProductTimestamp<T1, T2> — product order: (a1, b1) ≤ (a2, b2) iff a1 ≤ a2 and b1 ≤ b2. Used for independent multi-dimensional clocks.
• Lexicographic<A, B> — lexicographic order: outer dimension dominates; inner breaks ties. Used for epoch × offset patterns.

Three order-modifier wrappers complete the Phase 6 composition toolkit:

• Max<T> — inverts T’s partial order so that Frontier::meet computes max instead of min. Tracks “at least X” lower bounds.
• Min<T> — preserves T’s natural order (transparent newtype). Used alongside Max in composite types for semantic clarity.
• Bounded<T> — clamps values to a [min, max] interval, giving a provable upper bound on antichain width for finite ranges.

Phase 7 adds structural and dynamic lattice types:

• WithTop<T> — adds a structural Top sentinel above all Value(t). Top absorbs Lattice::join and is the identity for Lattice::meet. Signals a permanently-closed data path.
• WithBottom<T> — adds a structural Bottom sentinel below all Value(t). Bottom absorbs Lattice::meet and is the identity for Lattice::join. Compose with WithTop to produce Bottom < Value(t) < Top.
• MapLattice<K, V> — point-wise lattice over a BTreeMap. Models progress in runtime-topology systems where the set of dimensions (shards, partitions) changes dynamically. Meet = key-intersection + value-meet; join = key-union + value-join.
• SetLattice<T> — powerset lattice over a BTreeSet. The partial order is set inclusion. Meet is intersection; join is union. Models universal acknowledgement across a cluster.

Quick start

use antichain::Frontier;

// Two workers report their progress independently.
let worker_a = Frontier::from_elem(5u64);
let worker_b = Frontier::from_elem(3u64);

// Merge without coordination — meet is commutative, associative, and idempotent.
let merged = worker_a.meet(&worker_b);
assert_eq!(merged, worker_b.meet(&worker_a));  // commutative
assert!(merged.less_equal(&3));                // timestamp 3 is still in-flight
assert!(!merged.less_equal(&7));               // timestamp 7 is past the frontier

Convergence guarantee

Two nodes that have each seen any subset of the same update set, in any order, will hold identical Frontier values after merging.

use antichain::Frontier;

let updates = [
    Frontier::from_elem(3u64),
    Frontier::from_elem(7u64),
    Frontier::from_elem(5u64),
];

// Node A applies updates in order [0, 1, 2].
let node_a = updates[0].meet(&updates[1]).meet(&updates[2]);

// Node B applies updates in a different order [2, 0, 1].
let node_b = updates[2].meet(&updates[0]).meet(&updates[1]);

// Node C applies updates in yet another order [1, 2, 0].
let node_c = updates[1].meet(&updates[2]).meet(&updates[0]);

// All three converge to the same value regardless of order.
assert_eq!(node_a, node_b);
assert_eq!(node_b, node_c);

no_std support

Disable the default std feature to use this crate in no_std environments. A global allocator must be present (extern crate alloc is used internally):

[dependencies]
antichain = { version = "0.1", default-features = false }

Feature flags

Feature	Default	Description
std	yes	Link against std; disable for no_std + alloc environments.
serde	no	Derive Serialize / Deserialize for all public types.

Performance

Empirical width bounds (measured 2026-06-18, Apple M-series, release build):

Operation	Width 10	Width 100	Width 500	Width 1 000
Antichain::<ProductTimestamp>::insert (build width-n antichain)	123 ns	6.4 µs	146 µs	584 µs
Frontier::<ProductTimestamp>::meet (two width-n antichains)	147 ns	9.2 µs	204 µs	825 µs
Frontier::<u64>::meet (totally-ordered; collapses to width 1)	18 ns	18 ns	18 ns	18 ns
Antichain::<ProductTimestamp>::less_equal (dominates query)	5 ns	52 ns	246 ns	499 ns

Interpretation:

• Frontier::<u64>::meet is O(1) at any input count: the totally-ordered antichain collapses to width 1 (the minimum element), so inserting 1 000 u64 values costs the same as inserting 10.
• Frontier::<ProductTimestamp>::meet is empirically O(n²) in antichain width n. At widths seen in practice (typically ≤ 50 independent stream partitions), the cost is in the low-microsecond range.
• Compaction verdict (Phase 8.1): no compaction step is required. At width ≤ 100 the meet cost is < 10 µs. Width 1 000 (825 µs) exceeds practical system widths; if antichains grow beyond ≈ 100 elements, model each independent dimension as a MapLattice key rather than widening the antichain.

Structs

Antichain

A set of mutually incomparable elements under PartialOrd.

Bounded

A timestamp wrapper that restricts values to the interval [min, max].

Frontier

A progress claim: all timestamps strictly less than some element are complete.

Lexicographic

A pair timestamp with lexicographic order: the outer dimension totally orders; the inner dimension breaks ties.

MapLattice

A point-wise lattice over a BTreeMap<K, V>.

Max

Wraps T and inverts its partial order.

Min

Wraps T preserving its natural partial order.

ProductTimestamp

A pair timestamp with the product order: (a1, b1) ≤ (a2, b2) iff a1 ≤ a2 and b1 ≤ b2.

SetLattice

A powerset lattice over a BTreeSet<T>.

Enums

WithBottom

Lifts any type T by adding a single Bottom element below all Value(t).

WithTop

Lifts any type T by adding a single Top element above all Value(t).

Traits

Lattice

Greatest lower bound (meet) and least upper bound (join).