[Paper] Space-Optimal, Computation-Optimal, Topology-Agnostic, Throughput-Scalable Causal Delivery through Hybrid Buffering

Source: arXiv - 2601.11487v1

Overview

Causal delivery guarantees that messages are received in the order dictated by their cause‑and‑effect relationships—a cornerstone for building correct distributed applications. This paper presents a new algorithm that delivers causal ordering while keeping per‑message metadata essentially constant, works on any network topology, and incurs only O(1) processing cost per message. In short, it makes causal delivery practical for large‑scale systems where previous solutions either blew up metadata size or suffered from poor throughput.

Key Contributions

• Sender Permission to Send (SPS) + FIFO proof: Formal demonstration that enforcing “permission to send” at the sender together with FIFO reception guarantees causal delivery.
• Critical analysis of Cykas: Shows that the recent sender‑buffering algorithm Cykas is overly conservative, leading to throughput bottlenecks and liveness problems.
• Hybrid buffering algorithm: Introduces a novel scheme that combines sender‑side buffering (to enforce SPS) with receiver‑side buffering (to enforce FIFO), achieving:
  • Topology‑agnostic operation (no reliance on specific communication graphs).
  • Space‑optimal metadata: effectively constant size per message regardless of the number of processes.
  • Computation‑optimal processing: amortized O(1) work per message using carefully chosen data structures.
• Theoretical guarantees: Proves correctness (causal delivery), safety (no deadlocks), and scalability (throughput grows with the number of processes).

Methodology

1. Model & Definitions – The authors formalize causal relationships using the classic “happens‑before” relation and define the Sender Permission to Send (SPS) condition: a sender may transmit a message only after it knows that all its causal predecessors have already been sent.
2. Algorithm Design –
   • Sender side: Maintains a lightweight vector of send‑permissions that indicates which remote processes are allowed to receive the next message.
   • Receiver side: Buffers incoming messages only until FIFO order is restored; once FIFO is satisfied, the message is delivered, implicitly satisfying SPS for downstream sends.
   • Hybrid data structures: A combination of per‑process circular buffers and a global “ready‑set” hash map ensures constant‑time insertion, lookup, and removal.
3. Proof Sketch – By showing that SPS guarantees that no causal predecessor is omitted and FIFO guarantees local ordering, the authors prove that the hybrid algorithm satisfies the causal delivery property.
4. Evaluation – Analytical complexity analysis (space and time) and a comparative discussion with existing sender‑only (e.g., Cykas) and receiver‑only schemes.

Results & Findings

In essence, the hybrid approach eliminates the metadata explosion and the processing bottleneck that have historically prevented causal delivery from being used in large‑scale microservice or peer‑to‑peer environments.

Practical Implications

• Microservices & Event‑Driven Architectures: Developers can now embed causal ordering directly into message brokers (e.g., Kafka, NATS) without inflating payloads, enabling stronger consistency guarantees for state‑synchronization and audit trails.
• Collaborative Applications: Real‑time editors, multiplayer games, and CRDT‑based systems can enforce causality without sacrificing latency, improving convergence and reducing conflict resolution complexity.
• Edge & IoT Networks: Devices with limited memory and bandwidth benefit from the constant‑size metadata, making causal messaging feasible on constrained hardware.
• Framework Integration: The algorithm’s topology‑agnostic nature means it can be dropped into existing RPC or pub/sub libraries as a plug‑in layer, requiring only modest changes to the send/receive pipelines.

Limitations & Future Work

• Assumes reliable FIFO channels: The proofs rely on underlying FIFO delivery; extending the approach to lossy or unordered networks would need additional mechanisms (e.g., retransmission, sequencing).
• Prototype not benchmarked: The paper provides analytical guarantees but lacks empirical performance numbers on real clusters; future work could include a production‑grade implementation and comparison with state‑of‑the‑art causal broadcast libraries.
• Dynamic membership: Handling nodes joining/leaving the system dynamically is not addressed; integrating membership protocols while preserving O(1) metadata is an open challenge.

Authors

• Paulo Sérgio Almeida

Paper Information

• arXiv ID: 2601.11487v1
• Categories: cs.DC
• Published: January 16, 2026
• PDF: Download PDF