[Paper] Implementability of Global Distributed Protocols modulo Network Architectures

Source: arXiv - 2602.10320v1

Overview

The paper tackles a fundamental question for anyone building distributed systems: Can a high‑level “global” protocol be turned into a set of local programs that actually work on a given network? Li and Wies introduce a systematic way to answer this question for a variety of common asynchronous network architectures, offering both a theoretical framework and a practical tool that developers can use to verify and synthesize correct distributed implementations.

Key Contributions

• Network‑parametric Coherence Conditions – a unified set of criteria that capture exactly when a global protocol is implementable on a given network topology.
• Minimal operational axioms – the authors distill the conditions down to five simple rules describing how individual message buffers can insert and remove messages.
• Broad coverage of real‑world networks – they prove that five widely studied asynchronous architectures (peer‑to‑peer FIFO, mailbox, sender‑box, mono‑box, and bag) satisfy the axioms, making the theory immediately applicable.
• Complexity analysis – tight upper and lower bounds for the decision problem of implementability under different network models.
• Symbolic decision algorithms – efficient, network‑agnostic procedures for checking implementability, enabling automated analysis.
• Sprout(A) tool – the first implementation that supports network‑parametric verification without sacrificing speed or modularity, demonstrating the approach on realistic case studies.

Methodology

1. Formalizing Global Protocols – The authors model a global protocol as a choreography describing the intended message flow among participants, independent of any network details.
2. Defining Network Architectures – Each architecture is abstracted as a collection of message buffers (e.g., FIFO queues, unordered bags) together with operations for inserting and removing messages.
3. Coherence Conditions – They introduce a set of network‑parametric constraints that guarantee that local projections of the global protocol can be executed without deadlock or message loss.
4. Axiom Reduction – By analyzing the buffer operations, they prove that only five simple axioms (e.g., “insertion preserves order when required”) are sufficient to enforce the coherence conditions.
5. Complexity & Algorithms – Using symbolic representations (BDDs/SMT), they devise algorithms that decide implementability in polynomial time for many architectures and in PSPACE for the most general case.
6. Tool Implementation – Sprout(A) encodes the axioms and algorithms, taking a global protocol description and a network specification as input and outputting a yes/no answer plus, optionally, a synthesized local implementation.

Results & Findings

• Exact Characterization – For the five target architectures, the coherence conditions are both necessary and sufficient: a global protocol is implementable iff it satisfies the conditions.
• Optimal Complexity – Implementability checking is NL‑complete for FIFO‑peer‑to‑peer networks, P‑complete for mailbox‑style networks, and PSPACE‑complete for the most permissive bag model.
• Algorithmic Efficiency – Sprout(A) decides implementability on benchmark protocols (e.g., leader election, reliable broadcast) within seconds, matching or beating existing architecture‑specific tools.
• Modularity – Because the axioms are network‑parametric, adding a new architecture only requires specifying its buffer insertion/removal behavior; the same decision engine can be reused.

Practical Implications

• Design‑time Assurance – Engineers can write a global choreography (e.g., in a DSL like Scribble) and automatically verify whether it will work on their chosen transport layer (e.g., message queues, actor mailboxes).
• Protocol Synthesis – When the check succeeds, Sprout(A) can generate skeleton local code that respects the underlying network semantics, reducing boilerplate and human error.
• Network‑agnostic Development – Teams can switch between, say, a FIFO message broker and an unordered bag‑based pub/sub system without rewriting correctness proofs; they only need to supply the new buffer axioms.
• Performance‑aware Choices – The complexity results help architects pick the “right” network model for a given protocol: if a protocol fails under a bag model but succeeds under FIFO, the trade‑off between ordering guarantees and implementability becomes explicit.
• Tool Integration – Sprout(A)’s API can be embedded into CI pipelines, ensuring that any change to a choreography remains implementable across all supported network back‑ends before code is merged.

Limitations & Future Work

• Scope of Architectures – The study focuses on five classic asynchronous models; more exotic or hybrid networks (e.g., partially ordered multicast, priority queues) are not yet covered.
• Dynamic Topologies – The current framework assumes a static set of participants and buffers; handling dynamic join/leave or runtime reconfiguration remains an open challenge.
• Scalability of Synthesis – While verification is fast, generating full‑fledged production code (including error handling, retries, etc.) from the abstract local implementations needs further engineering.
• Empirical Evaluation – The paper’s experiments are limited to synthetic benchmarks; applying Sprout(A) to large‑scale microservice deployments would validate its real‑world impact.

Overall, Li and Wies provide a solid theoretical foundation and a usable tool that bring global protocol verification into the everyday toolbox of distributed system developers.

Authors

• Elaine Li
• Thomas Wies

Paper Information

• arXiv ID: 2602.10320v1
• Categories: cs.FL, cs.DC, cs.PL
• Published: February 10, 2026
• PDF: Download PDF