Byzantine-Tolerant Causal Unicast with Constant Message Space Overhead

• Causal message ordering preserves the happens-before relationship, supporting strong consistency without the overhead of total synchronization.Source: §1 · p. 1
• Unicast causal delivery must manage dependencies without global message visibility, while receiver buffering has O(n^2) metadata overhead and sender buffering can constrain throughput.Source: §1 · p. 1
• In asynchronous Byzantine systems, deterministic causal ordering cannot guarantee both strong safety and liveness without cryptography, while existing unicast solutions face overhead or model limitations.Source: §1 · p. 1

• The paper presents a Byzantine-tolerant causal ordering algorithm with O(1) message overhead.Source: Contributions · p. 1
• The algorithm uses the Sender Permission to Send invariant with isolated per-peer queues and event-driven Cascading Space Evictions to counter state-pinning and head-of-line blocking.It uses point-to-point unicast for application payloads, acknowledgments, and permissions.Source: Contributions · p. 2
• The protocol guarantees deterministic system-wide liveness for honest-to-honest communication in a purely asynchronous environment while satisfying Congestion-Relaxed Causal Delivery.Weak causal safety is preserved unless extreme latency or Byzantine withholding exceeds local buffer capacities and forces optimistic queue evictions.Source: Contributions · p. 2
• O(1) network message space overhead avoids attaching O(n) or O(n^2) dependency histories to application packets.Dependency vectors and outbound history snapshots remain in process-local state.Source: Contributions · p. 2
• O(n^2) local space complexity bounds process-segregated unacknowledged and missing-permit buffers, while event-driven vector checks have amortized O(n) computational cost.The stated worst-case computational pass is O(n^2).Source: Contributions · p. 2

System Model.

• The system has n processes, permits any t < n Byzantine failures, and assumes reliable FIFO channels for application messages between each process pair.Source: System Model · p. 2

Causal Ordering and Safety Definitions.

• In asynchronous Byzantine systems, deterministic cryptography-free causal ordering cannot guarantee both strong safety and liveness, so algorithms must accept safety violations or risk halting honest processes.Source: Causal Ordering and Safety Definitions · pp. 2–3

Adapting Causal Ordering to Byzantine Systems.

• SPS delays network-sending until relevant causal dependencies are cleared; with point-to-point FIFO channels, SPS at all correct nodes is sufficient for system-wide causal delivery.The protocol adapts SPS using isolated outbound queues and missing-permit buffers.Source: Adapting Causal Ordering to Byzantine… · p. 3

Liveness.

• Liveness requires every message sent by a correct process to another correct process to be eventually delivered.Source: Liveness · p. 3

The Congestion-Relaxed Causal Delivery Abstraction.

• Congestion-Relaxed Causal Delivery preserves FIFO and bounded causal integrity when correct-process queues avoid eviction and required permissions arrive before network sends.Weak safety violations are limited to extreme congestion or adversarial stalling that forces queue eviction; without those conditions, the abstraction reduces to weak safety.Source: The Congestion-Relaxed Causal Delivery… · pp. 3–4

Crash-Tolerant Causal Delivery.

• Crash-tolerant receiver-buffering algorithms retain O(n^2) worst-case metadata, while Cykas reduces metadata to O(1) but has throughput scalability and liveness limitations.Source: Crash-Tolerant Causal Delivery · p. 4
• Almeida’s hybrid buffering uses SPS to provide liveness and throughput scalability, but its unified buffers and trust in ACKs and PERMITs leave it vulnerable to Byzantine resource-exhaustion and state-pinning attacks.Source: Crash-Tolerant Causal Delivery · p. 4

Byzantine-Tolerant Causal Ordering.

• Secure causal atomic broadcast uses threshold encryption but incurs expected O(n^3) consensus communication over full payloads and has a nonzero probability of causal-ordering violation.Source: Byzantine-Tolerant Causal Ordering · p. 4
• Other Byzantine-tolerant approaches rely on synchrony or incur O(n) message overhead; some lack strong safety or assume unbounded memory.The Minicast Algorithm uses Byzantine Reliable Broadcast with O(n^2) messages and assumes unbounded local space.Source: Byzantine-Tolerant Causal Ordering · p. 4

4 Proposed Algorithm

• O(1) network message-size overhead and O(n²) local space support deterministic liveness, with occasional safety violations permitted under extreme latency or resource-exhaustion attacks.The protocol guarantees Congestion-Relaxed Causal Delivery despite those exceptions.Source: §4 · pp. 4–5, §4.3 · p. 5

4.1 Core Logic

• The algorithm extends Almeida’s Sender Permission to Send invariant [1] to Byzantine tolerance while addressing withheld controls, causal forgery, memory exhaustion, and replay attacks.These attacks can otherwise cause blocking, release messages prematurely, consume memory, or trigger duplicate deliveries.Source: §4.1 · p. 5

4.2 Important Data Structures

• Isolated buffers and dependency vectors keep messages at constant network size, while the local structures require O(n²) space and all application and control traffic uses point-to-point unicast.The architecture replaces unified data structures with process-isolated queues and localized tracking arrays; its computational time is amortized O(n).Source: §4.1 · p. 5, §4.2 · p. 5

4.3 Byzantine Tolerant Algorithm

• Event-driven optimistic cascading evictions in isolated buffers preserve liveness in an asynchronous network, permitting localized, transient causal-safety violations when physical buffer limits are reached.The protocol allocates O(n²) local memory for isolated queues while retaining O(1) message-size overhead.Source: §4.3 · p. 5

5.1 Liveness Guarantee

• An honest process is not permanently blocked from sending or delivering, and messages between honest processes are eventually delivered under continuous application traffic or a timeout-driven synchronous variant.If traffic is reactive and queues never fill, evictions may not trigger and a system-wide deadlock can result.Source: §5.1 · p. 6

5.2 Congestion-Relaxed Causal Delivery Guarantee

• The algorithm guarantees Congestion-Relaxed Causal Delivery for communications between honest processes, preserving FIFO order and bounded causal integrity.FIFO follows from reliable FIFO channels and in-sequence receiver delivery.Source: §5.2 · p. 8

5.3 Safety Trade-offs

• Strict safety is relaxed under physical capacity pressure because deterministic strong safety and liveness cannot both be guaranteed without cryptography in an asynchronous Byzantine system.The analysis distinguishes self-contained violations within Byzantine processes, adversarial sequence shifting, and true safety breaches involving a broken dependency chain over the wire.Source: §5.3 · pp. 8–9

5.3.1 Weak Safety Violation under Severe Asynchronous Network

• Physical buffer limits can force true weak-safety violations even between completely honest processes under extreme asynchronous network conditions.The Congestion-Relaxed Causal Delivery guarantee still holds.Source: §5.3.1 · pp. 9–10
• Extreme delay can postpone an ACK until honest-process queues saturate, prompting eviction and a premature PERMIT that may let a causally dependent message arrive first.The resulting honest-to-honest weak-safety violation is described as very low probability; avoiding it with bounded memory is not guaranteed, while unbounded queues would restore memory-exhaustion vulnerabilities.Source: §5.3.1 · pp. 9–10

6 Complexity Analysis

• The complexity profile covers network message metadata overhead, communication message complexity, local memory space complexity, and computational execution time.The analysis is summarized in Table 1, with further detail in Appendix C.Source: §6 · p. 10

7 Discussion and Conclusions

• The protocol is presented as the first purely asynchronous Byzantine-tolerant point-to-point unicast causal-delivery protocol with strict O(1) network message-space overhead.It introduces Congestion-Relaxed Causal Delivery to bridge absolute liveness and relaxed causal-safety bounds.Source: §7 · p. 10
• Unlike approaches that append O(n) or O(n^2) dependency vectors and incur O(n^2) or O(n^3) message complexity, the protocol keeps wire overhead at O(1).Its point-to-point isolated queues also prevent a Byzantine node from exhausting resources or freezing unrelated correct processes' channels.Source: §7 · p. 10
• The localized signaling plane has amortized computational execution cost O(n) per message and avoids heavy global-consensus overhead during normal execution.Source: §7 · p. 10
• Queue capacities Mmax and Qmax are application-controlled; increasing them can reduce weak-safety violations at a predictable local memory cost of O(n^2).Causal ordering is guaranteed for honest-to-honest paths unless specified bounds are exceeded.Source: §7 · p. 10
• The paper characterizes the trade-off between buffer capacities and transient ordering relaxations as viable for secure, high-performance distributed systems.Source: §7 · p. 10

A Usage of Data Structures

• The Local Dependency Vector (DV) stores, for each peer, the highest message sequence number delivered when a message is initialized, and remains local rather than appearing in the network payload.Source: A Usage of Data Structures · p. 11
• Keeping dependency and outbound-history vectors in local records, rather than transmitted messages, preserves constant network message-size overhead while local space scales as O(n^2).Each of n isolated buffers can hold up to Mmax records, each caching an n-sized array.Source: A Usage of Data Structures · p. 11
• The Last Message Sent vector (LMSi) records the latest local sequence number sent to each peer and helps preserve the sender-side SPS invariant.A snapshot is stored in each message record and used to check causal stability before permits are released.Source: A Usage of Data Structures · p. 11
• Outbound application messages use independent FIFO queues U_i[1..n], each bounded by Mmax, so suppressed acknowledgments confine memory growth to the affected destination channel.This isolation leaves parallel channels to honest peers unaffected.Source: A Usage of Data Structures · p. 11
• Missing permits use independent FIFO queues Q_i[1..n], bounded by Qmax, which decouple acknowledgment processing from permit generation.When a queue reaches capacity, cascading eviction removes its oldest record and sends a proactive PERMIT to prevent local memory exhaustion.Source: A Usage of Data Structures · p. 11
• The Last Delivered vector (LDi) tracks the latest valid application-message sequence number delivered from each peer and serves as local causal ground truth.It populates new dependency vectors and supports rejection of duplicate or replayed messages.Source: A Usage of Data Structures · pp. 11–12
• The Last Permit Received vector (LPRi) tracks each peer's highest causal authorization and supplies a local causal ceiling for preserving the SPS invariant.It advances on permit receipt or qualifying messages and is consulted to determine whether buffered outbound messages can be released.Source: A Usage of Data Structures · p. 12

B Description of Algorithm Procedures

• causalSend checks the targeted queue's capacity, initializes a message with causal-history snapshots, updates LMSi, and attempts transmission.The message record includes a dependency vector copied from LDi and an outbound-history snapshot copied from LMSi.Source: §B.0.1 · p. 12
• When U_i reaches Mmax, the procedure evicts its oldest message and may transmit it optimistically; if it requires a permit, capacity checks cascade to Q_i.Queue overflow can cause the protocol to advance local permit state despite unresolved dependencies.Source: §B.0.1 · p. 12
• The sendMessages procedure checks unsent messages against the local permit vector and sends only when the SPS causal-dependency condition is satisfied.A blocked message stops later transmissions in that FIFO channel, without halting unrelated destination channels.Source: §B.0.2 · p. 12
• sendPermits releases a queued PERMIT only after the outbound causal-stability check confirms earlier messages to other peers were acknowledged or cleared by eviction.The permit is sent by unicast and its queue record is removed; a failed check pauses that channel's FIFO pipeline.Source: §B.0.3 · pp. 12–13
• The receive(MSG) procedure rejects stale or replayed sequence numbers, updates authorization when the permit flag is disabled, records delivery progress, acknowledges the message, and delivers its payload.Source: §B.0.4 · p. 13
• The receive(ACK) procedure filters duplicate or inflated acknowledgments, removes acknowledged messages from the sender queue, and transfers permit-dependent records into Q_i.If Q_i is full, it evicts its oldest entry and sends a proactive PERMIT before appending the new record.Source: §B.0.5 · p. 13
• The receive(PERMIT) procedure accepts only indices already delivered locally and newer than the current authorization, then advances LPRi and retries blocked messages.Source: §B.0.6 · p. 13

C Detailed Complexity Analysis

• Each application MSG carries a destination identifier, local sequence index, boolean permit flag, and application payload.Source: §C.0.1 · p. 13
• The Local Dependency Vector and outbound causal-history snapshot are kept in local buffers and omitted from serialized network payloads.Source: §C.0.1 · p. 13
• Excluding those vectors from transmitted messages keeps wire message-space overhead strictly O(1) with respect to network size n.Source: §C.0.1 · p. 13

C.0.2 Message Complexity (Number of Messages).

• Each application send uses one O(1)-size MSG, one O(1)-size ACK, and at most one O(1)-size PERMIT, giving O(1) message complexity.All tracking, verification, and clearance use localized point-to-point unicast messaging.Source: §C.0.2 · pp. 13–14
• O(n^2) local memory results from bounded isolated queues whose cached records each embed two n-sized tracking vectors.The global tracking arrays add O(n) space; the queue-record vectors produce the quadratic term.Source: §C.0.3 · p. 14

C.0.4 Computational Time Complexity.

• O(n) amortized time per message is the stated bound for Algorithm 2.The proof derives this expectation over an execution sequence of N messages in a uniform steady-state network.Source: §C.0.4 · p. 14
• Under that steady-state analysis, an active queue has probability O(1/n), balancing O(n) vector checks across each sweep of n channels.The analysis also relies on a fixed, constant number of event-driven triggers per message lifecycle.Source: §C.0.4 · p. 14