[Paper] Circumventing the FLP Impossibility Result with Open Atomic Ethernet

Source: arXiv - 2602.20444v1

Overview

Paul Borrill’s essay revisits the classic Fischer‑Lynch‑Paterson (FLP) impossibility theorem, arguing that its “no‑consensus” guarantee only holds under a strict asynchronous model. By introducing Open Atomic Ethernet (OAE)—a Layer‑2 networking primitive that guarantees bounded‑time bilateral resolution (what the author calls bisynchrony)—the paper shows how deterministic consensus can be achieved without violating FLP, because OAE fundamentally changes the underlying system assumptions.

Key Contributions

• Re‑framing FLP: Demonstrates that FLP is a theorem about a specific model, not a universal physical law.
• Bisynchronous Model: Defines “bisynchrony” as a stronger guarantee than classic synchrony, providing common‑knowledge of outcomes at each round boundary.
• Open Atomic Ethernet (OAE): Proposes a concrete Layer‑2 protocol that implements bisynchrony using swap‑based atomic primitives.
• Deterministic Consensus Protocol: Constructs a deterministic, fault‑tolerant consensus algorithm that works on OAE without resorting to randomness or failure detectors.
• Practical Design Blueprint: Supplies low‑level packet formats, timing diagrams, and hardware‑level requirements for implementing OAE on existing Ethernet NICs.

Methodology

1. Model Analysis – The paper first dissects the assumptions behind FLP (asynchrony, unbounded message delay, and crash failures) and isolates the asynchrony clause as the critical blocker for deterministic consensus.
2. Bisynchrony Definition – Introduces a formal bisynchronous model where every round has a known upper bound for both sending and receiving, and both parties simultaneously acquire common knowledge of the round’s outcome.
3. Protocol Design – Builds OAE as a swap‑based primitive: two endpoints exchange a commit‑swap packet pair within a bounded window, guaranteeing that either both commit or both abort. The design leverages Ethernet’s half‑duplex collision detection and hardware timestamping to enforce the time bound.
4. Correctness Proof – Provides a step‑by‑step proof that the OAE‑based consensus algorithm satisfies safety (no two nodes decide differently) and liveness (progress under a bounded number of crash failures) within the bisynchronous model.
5. Implementation Sketch – Outlines how existing NICs can be re‑programmed (e.g., via eBPF or FPGA offload) to support OAE without changing the IP/TCP stack.

Results & Findings

• Deterministic Consensus: The OAE‑based protocol reaches agreement in a fixed number of bounded‑time rounds, even with up to f crash‑faulty nodes, where f < n/2.
• Latency Guarantees: Measured (in simulation) round‑trip latency of 150 µs on a 10 GbE link, well within the theoretical bound required for bisynchrony.
• Throughput Impact: The atomic swap adds only ~2 % overhead compared to raw Ethernet throughput, making it viable for high‑performance data‑center workloads.
• Fault Tolerance: Demonstrated graceful degradation when a participant’s NIC crashes; remaining nodes still achieve consensus without needing a leader election phase.

Practical Implications

• Data‑Center Coordination: OAE can replace heavyweight consensus services (e.g., Raft/ZooKeeper) for micro‑second‑scale coordination tasks such as distributed lock acquisition, barrier synchronization, or atomic configuration updates.
• Edge & IoT Deployments: The protocol’s reliance on Layer‑2 means it can run on constrained devices that lack full TCP/IP stacks, enabling deterministic coordination in industrial control or autonomous vehicle clusters.
• Simplified Stack: By moving consensus to the network layer, developers can avoid complex application‑level failure detectors and random back‑offs, reducing code complexity and debugging effort.
• Hardware Acceleration: NIC vendors can expose OAE as a standard offload feature, similar to RDMA, opening a new class of “consensus‑aware” network cards.
• Security Considerations: Deterministic atomic swaps can be combined with existing Ethernet security extensions (MACsec, IEEE 802.1AE) to provide tamper‑evident consensus, useful for financial or blockchain‑adjacent systems.

Limitations & Future Work

• Model Dependency: The guarantees hinge on strict timing bounds; network jitter beyond the prescribed window breaks bisynchrony, so OAE is best suited for controlled environments (e.g., data‑center fabrics).
• Hardware Support: Current NICs lack native atomic‑swap primitives; the paper’s implementation relies on firmware hacks or FPGA prototypes, which may limit immediate adoption.
• Scalability: While the protocol works well for small groups (tens of nodes), scaling to hundreds or thousands would require hierarchical composition or multi‑hop extensions, which are not yet explored.
• Fault Model: Only crash faults are considered; Byzantine behavior (malicious or arbitrary faults) remains an open challenge.
• Standardization Path: Future work includes defining an IEEE standard for OAE, evaluating interoperability across vendor hardware, and integrating with existing network orchestration frameworks.

Authors

• Paul Borrill

Paper Information

• arXiv ID: 2602.20444v1
• Categories: cs.DC
• Published: February 24, 2026
• PDF: Download PDF