Optimality of Simultaneous Consensus with Limited Information Exchange (Extended Abstract)

Basic Information

• Paper ID: 2511.22380
• Title: Optimality of Simultaneous Consensus with Limited Information Exchange (Extended Abstract)
• Authors: Kaya Alpturer (Princeton University), Ron van der Meyden (UNSW Sydney), Sushmita Ruj (UNSW Sydney), Godfrey Wong (UNSW Sydney)
• Classification: cs.DC (Distributed Computing)
• Publication Time/Conference: TARK 2025 (Theoretical Aspects of Rationality and Knowledge 2025)
• Paper Link: https://arxiv.org/abs/2511.22380
• Conference Publication: EPTCS 437, 2025, pp. 175–189

Abstract

This paper investigates the Simultaneous Byzantine Agreement (SBA) problem under the crash failure model, focusing on the optimality of protocols with limited information exchange. Traditional research on knowledge-logic-based fault-tolerant consensus protocols concentrates on "full information" exchange approaches, which incur high costs in message size. This paper analyzes multiple limited information exchange protocols from the literature (FloodSet and its variants, Vectorized FloodSet) and proposes a novel information exchange protocol called SendWaste, which can make decisions at most one round later than the optimal full information protocol of Dwork and Moses, while requiring lower computational costs and space requirements. By implementing knowledge-based programs, the paper derives optimal protocols for each information exchange method.

Research Background and Motivation

1. Core Problem

The core problem addressed in this paper is: How can one design optimal synchronous Byzantine agreement protocols when the information exchanged between agents in a distributed system is limited?

2. Problem Significance

• Theoretical Significance: Byzantine agreement is a fundamental problem in distributed computing, closely related to consensus mechanisms and fault-tolerant system design
• Practical Value: Although full information protocols are theoretically optimal, in practical applications message size grows exponentially, and computational complexity can reach NP-hard (as in the general omission failure model)
• Real-world Needs: Practical protocols typically exchange limited information; theoretical guidance is needed to ensure these protocols fully utilize the information exchanged

3. Limitations of Existing Approaches

• Full Information Protocols: Each agent broadcasts complete local state each round, causing state space to grow exponentially over time
• Dwork-Moses Protocol: Although relatively optimal for full information, has message size O(t), space complexity O(n), and computational complexity O(nt)
• Limited Information Protocols in Literature: Lack theoretical analysis of their optimality; may not fully utilize exchanged information

4. Research Motivation

• Fill theoretical gaps: Only one paper 1 has studied Byzantine agreement optimality under limited information exchange (for the eventual agreement problem)
• Practical drive: Provide theoretical guarantees for practical protocols; determine earliest termination time given information exchange
• Optimize existing protocols: Reveal improvement opportunities in literature protocols through knowledge-theoretic analysis

Core Contributions

The main contributions of this paper include:

1. Theoretical Framework Establishment: Extends the concept of optimality under limited information exchange from eventual agreement (EBA) to synchronous agreement (SBA) problems
2. FloodSet Protocol Optimization:
   • Establishes optimal stopping condition: m ≥ min{t+1, n-1}
   • Improves literature results: terminates earlier than the usually stated t+1 when t=n-1
3. Counting FloodSet Analysis:
   • Proves the counting variant has the same optimal stopping condition as FloodSet (except special cases)
   • Proves that retaining historical counting information (perfect recall) provides no additional advantage
4. Vectorized FloodSet Improvement:
   • Discovers non-trivial early stopping conditions: m > min{t+1, n-1} - max{1, βi(r,m)}
   • Improves stopping time t+1 from Raynal11
5. New SendWaste Protocol:
   • Proposes new information exchange mechanism: transmit waste estimates rather than agent sets
   • Performance guarantee: decides at most one round later than Dwork-Moses protocol
   • Efficiency gains: computational complexity O(n), message size O(1), space complexity O(1)
6. Systematic Complexity Comparison: Provides complete comparison of all protocols across computation, message size, and space dimensions (see Table 1)

Methodology Details

Task Definition

Synchronous Byzantine Agreement (SBA) Problem includes the following specifications:

• Input: n agents, each with initial value vi ∈ {0,1}, system has at most t < n crash failures
• Output: Non-failed agents decide on value v ∈ {0,1}

Constraints:

1. Agreement: All non-failed agents decide the same value
2. Validity: Decided value must be some agent's initial value
3. Simultaneity: All non-failed agents decide in the same round
4. Termination: Each agent eventually decides or fails

Crash Failure Model (Crasht):

• Failed agents can send any subset of messages in their crash round
• Send no messages after crashing
• At most t agents fail

Model Architecture

1. Protocol Decomposition Framework

This paper decomposes SBA protocols into two components: (P, E)

• Information Exchange Protocol E: Defines what information agents record and what messages they send
• Decision Protocol P: Defines when and what value agents decide

Formal definition of Information Exchange Protocol Ei as a six-tuple:

• Li: Set of local states
• Ii ⊆ Li: Set of initial states
• Ai: Set of allowed actions
• Mi: Set of messages that can be sent
• μi: Li × Ai → ∏j∈Agt(Mi ∪ {⊥}): Message selection function
• δi: Li × Le × Ai × ∏j∈Agt(Mj ∪ {⊥}) → Li: State transition function

2. Knowledge-Based Programs

The core knowledge-based program Popt_i is defined as:

if Ki(CN(∃0)) then decidei(0)
else if Ki(CN(∃1)) then decidei(1)
else noop

Where:

• Ki(φ): Agent i knows φ
• CN(φ): Common knowledge of non-failed agents
• ∃v: There exists an agent with initial value v

Key Insight (Lemma 1): If agent i decides v at (r,m), then (I,r,m) ⊨ CN(∃v)

3. Optimality Definition

Partial Order: P ≤E P' if and only if in all corresponding runs, when P decides, P' also decides

Optimal Protocol: No strictly better protocol exists (i.e., P ≤E P' implies P' ≤E P)

Optimal Implementation Theorem (Theorem 2): The implementation of knowledge-based program Popt is an optimal SBA protocol relative to its information exchange E

Technical Innovations

1. Information Storage Relationship Theory

Definition: E1 stores more information than E2 if in corresponding runs: (r1,m) ~i (r3,m) ⟹ (r2,m) ~i (r4,m)

Corollary (Proposition 1): If E1 stores information ≥ E2, then: (IE1,r1,m) ⊨ ¬CN φ ⟹ (IE2,r2,m) ⊨ ¬CN φ

This theoretical tool enables transferring knowledge acquisition conclusions through information quantity comparison.

2. Clean Round Concept

Definition: A round is clean if all non-failed agents receive the same set of messages

Key Properties:

• After a clean round, all agents have identical state (Lemma 5)
• A clean round must occur within t+1 rounds (at most t failures)
• When t=n-1, agents can decide by round n-1

3. Waste Estimation Concept

Dwork-Moses Waste: W(r) = maxk≥0{#KF(r,k) - k}

• #KF(r,k): Maximum number of failures in distributed knowledge at round k

SendWaste Estimation: di = max{di-1, received dj, hi - m}

• hi: Number of missing messages in round m
• Estimate: hi - m (observed "waste" in current round)

Innovation Points:

• No need to maintain failed agent sets, only count
• Message size reduced from O(t) to O(1)
• Computational complexity reduced from O(nt) to O(n)

Experimental Setup

Theoretical Analysis Methods

This is a pure theory paper without experimental data; results are established through formal proofs. Main analysis methods:

1. Knowledge-Theoretic Semantic Analysis: Using interpreted systems and indistinguishability relations
2. Inductive Proof: Induction on run time and states
3. Constructive Proof: Proving necessity through counterexamples
4. Corresponding Run Comparison: Comparing different protocols' behavior under identical failure patterns

Evaluation Criteria

Protocol quality is evaluated across the following dimensions:

1. Decision Time: Earliest round of first decision
2. Computational Complexity: Computation per agent per round
3. Message Size: Bits per message
4. Space Complexity: State storage per agent

Comparison Baselines

• FloodSet Lynch 1996
• Counting FloodSet Castañeda et al. 2017
• Vectorized FloodSet Raynal 2002
• Dwork-Moses Protocol Dwork & Moses 1990 - Optimal full information protocol

Experimental Results

Main Theoretical Results

1. FloodSet and Its Optimization (Theorem 3)

Original Stopping Condition: m = t+1

Optimized Stopping Condition: m ≥ min{t+1, n-1}

Proof Outline:

• Necessity: Lemma 2 shows no common knowledge when m < min{t+1, n-1}
• Sufficiency: After min{t+1, n-1} rounds, a clean round must occur; common knowledge follows from Lemmas 5-6

Improvement Significance: When t=n-1, can decide by round n-1 instead of round n

2. Counting FloodSet (Theorem 4)

Stopping Condition: m ≥ min{t+1, n-1} or hi ≥ n-1

Key Observation:

• When hi ≥ n-1, agent i knows at most one other agent is alive
• Can immediately decide min Wi

Comparison with FloodSet: Only earlier when detecting n-1 missing messages

3. Counting FloodSet with Perfect Recall (Theorem 5)

Stopping Condition: m ≥ min{t+1, n-1} or ∃k≤m(hik ≥ n-1)

Important Finding: Retaining history provides no additional advantage

• Unlike EBA (where historical information is useful)
• Cost: Increased space but no performance gain

Information Storage Relationship (Lemma 7): Ecount(pr) ≥ Ecount ≥ Eflood

4. Vectorized FloodSet (Theorem 6)

Stopping Condition: m > min{t+1, n-1} - max{1, βi(r,m)}

Where βi(r,m) is the number of agents from which agent i did not receive messages in round 1

Analysis:

• Larger βi(r,m) enables earlier decision
• When βi(r,m) = n-1, can decide after round 1
• Improves stopping time t+1 from literature 11

Special Case Comparison:

• When hi ≥ n-1, Counting FloodSet can decide but Vectorized FloodSet cannot
• In other cases, Vectorized FloodSet performs at least as well

5. SendWaste Protocol (Theorem 7-8)

Stopping Condition: m ≥ min{t+1, n-1} - dN

Where dN = maxi∈N(r,m) di(r,m) is the maximum waste estimate among non-failed agents

Comparison with Dwork-Moses (Theorem 8):

• If Dwork-Moses decides at round m', SendWaste decides at round m
• Guarantee: m' ≤ m ≤ m'+1 (at most one round later)

Efficiency Gains:

Comprehensive Performance Comparison

Table 1 Summary (per agent per round):

Decision Time Ranking (from worst to best):

1. FloodSet: min{t+1, n-1} (worst)
2. Counting FloodSet: same as above, but earlier in special cases
3. Vectorized FloodSet: possibly earlier (depends on β)
4. SendWaste: close to Dwork-Moses
5. Dwork-Moses: optimal (full information)

Key Insights

1. Power of Clean Rounds: Once a clean round occurs, common knowledge is immediately established
2. Limitations of Counting: Counting only current round is insufficient to surpass FloodSet
3. Uselessness of History: For SBA, historical counting provides no advantage (contrast with EBA)
4. Advantages of Vectorization: Associating agents with values provides early stopping
5. Efficiency of Estimation: Estimating waste is more efficient than maintaining sets

Related Work

1. Knowledge Theory and Distributed Algorithms

Foundational Work:

• Halpern & Moses (1990) 6: Establishes framework for knowledge and common knowledge in distributed environments
• Fagin et al. (1995) 5: "Reasoning About Knowledge" lays theoretical foundation

Knowledge-Theoretic Analysis of Byzantine Agreement:

• Dwork & Moses (1990) 4: Proves SBA requires common knowledge; proposes optimal full information protocol
• Moses & Tuttle (1988) 10: Uses common knowledge for programming synchronous actions

2. Limited Information Exchange

Direct Predecessor:

• Alpturer, Halpern & van der Meyden (2023) 1: First to study limited information optimality for EBA (send omission model)

Classical Protocols:

• Lynch (1996) 7: Original description of FloodSet protocol
• Castañeda et al. (2017) 3: Predicate-based early decision; introduces counting mechanism
• Raynal (2002) 11: Vectorized FloodSet

3. Computational Complexity

NP-hard Results:

• Moses (2009) 9: Optimal synchronous agreement under general omission equivalent to NP-oracle
• Moses & Tuttle (1988) 10: Full information protocols require NP-hard computation in general omission model

4. Unbeatable Consensus

• Castañeda, Gonczarowski & Moses (2022) 2: Studies unbeatable consensus protocols

Positioning of This Work

Advantages over Related Work:

1. First Systematic Study: Limited information optimality for SBA (1 only studies EBA)
2. Multi-Protocol Analysis: Comparison of multiple information exchanges in unified framework
3. New Protocol Design: SendWaste fills performance-efficiency tradeoff gap
4. Theoretical Improvements: Corrects and improves stopping conditions from literature

Relationship with 1:

• Methodology continuation: Uses knowledge-based program implementation framework
• Different problems: SBA vs EBA (stronger simultaneity requirement)
• Different failure models: Crash failures vs send omission

Conclusions and Discussion

Main Conclusions

1. Optimality of FloodSet Variants:
   • FloodSet and its counting variant achieve optimality for their respective information exchanges
   • Stopping condition is m ≥ min{t+1, n-1} (with possible early stopping exceptions)
   • Retaining historical counts is unhelpful for SBA
2. Improvement of Vectorized FloodSet:
   • Establishes non-trivial early stopping conditions
   • Improves original result from Raynal 11
   • But inferior to Counting FloodSet in some cases
3. Practicality of SendWaste:
   • Approaches full information optimality in decision time (at most one round later)
   • Significantly more efficient than Dwork-Moses protocol
   • Provides good balance between theoretical optimality and practical feasibility
4. Value of Theoretical Framework:
   • Knowledge-based program method effectively characterizes optimality
   • Information storage relationship theory facilitates protocol comparison
   • Provides systematic analysis method for limited information exchange protocols

Limitations

1. Unique Decision Assumption

Current Setting:

• Allows agents to decide multiple times on the same value
• Local state does not record fact of having decided
• Does not satisfy "Unique Decision" property

Impact:

• Facilitates protocol comparison and information exchange analysis
• But differs from standard SBA specification

Author's Note:

• Conjecture that modification to unique decision version preserves optimality
• Results from van der Meyden 8 support this conjecture
• Requires different proof techniques (future work)

2. Failure Model Limitations

Current Model: Only considers crash failures

Not Covered:

• General omission failures (send/receive omission)
• Byzantine failures (malicious behavior)

Challenges:

• Full information optimal protocol for general omission requires NP-hard computation 10
• Polynomial-time limited information protocols are particularly valuable

3. Synchrony Assumption

Strong Assumptions:

• Synchronized clocks
• Known message delivery time bounds
• Round-based communication

Practical Limitations:

• Inapplicable in asynchronous systems
• Partial synchrony model not considered

4. Binary Agreement

Simplification: Only considers Values = {0, 1}

Extensibility: Multi-valued agreement may require different analysis

Future Directions

1. General Omission Failure Model (Explicitly Stated by Authors)

Goal: Find polynomial-time SBA protocol optimal under limited information exchange

Significance:

• Full information optimality requires NP-hard computation
• Limited information may avoid computational complexity
• High practical value

2. Unique Decision Property

Work:

• Modify protocols to record decision state
• Prove modified protocols remain optimal
• Apply techniques from van der Meyden 8

3. Asynchronous and Partial Synchrony Models

Extensions:

• Study limited information optimality in asynchronous environments
• Analysis of partial synchrony model

4. Byzantine Failures

Challenges:

• Malicious agents can send false information
• Requires more complex verification mechanisms

5. Practical Implementation and Verification

Directions:

• Practical system implementation of SendWaste protocol
• Performance benchmarking
• Formal verification tool development

In-Depth Evaluation

Strengths

1. Theoretical Rigor (★★★★★)

Formal Completeness:

• Complete mathematical framework: interpreted systems, knowledge-theoretic semantics, optimality definitions
• All theorems have rigorous proofs (though extended abstract omits details)
• Clear logical reasoning chains

Methodological Innovation:

• Information storage relationship theory (Proposition 1) provides elegant comparison tool
• Knowledge-based program implementation framework unifies optimality analysis

2. Practical Value (★★★★☆)

SendWaste Protocol:

• Resolves contradiction between theoretical optimality and practical efficiency
• Concrete complexity improvements (O(nt)→O(n), O(t)→O(1))
• Suitable for scenarios with large t (large-scale distributed systems)

Protocol Optimization:

• Improves stopping conditions from literature
• Provides theoretical guarantees for practical systems

3. Systematic Analysis (★★★★★)

Comprehensive Coverage:

• Analyzes multiple protocols from literature
• Comparison under unified framework
• Clear performance table (Table 1)

Deep Insights:

• Reveals historical information useless for SBA (contrast with EBA)
• Explains value of different information types

4. Writing Clarity (★★★★☆)

Good Structure:

• Logical flow from background to specific protocols
• Separate sections for each protocol, facilitating understanding

Readability:

• Balances technical details with intuitive explanations
• Clear pseudocode

Weaknesses

1. Missing Experimental Validation (★★☆☆☆)

Pure Theory:

• No actual system implementation
• No performance benchmarking
• No comparison with practical protocols (Paxos, Raft)

Impact:

• Actual performance improvements not quantified
• Constant factors and hidden costs unknown

2. Extended Abstract Limitations (★★★☆☆)

Proof Omissions:

• Most theorem proofs not provided
• Difficult to verify technical details
• Requires reference to full version

Limited Depth:

• Some protocol analyses relatively shallow
• Insufficient discussion of boundary cases

3. Limited Applicability (★★★☆☆)

Strong Assumptions:

• Synchronous model limitation
• Only crash failures
• Binary agreement

Generalizability:

• Unclear whether results extend to other settings

4. Gap with Practical Protocols (★★☆☆☆)

Industrial Protocols:

• No discussion of relationship with Paxos, Raft, etc.
• Practical system considerations (network latency, partial failures) not addressed

Impact Assessment

1. Contribution to Field (★★★★★)

Theoretical Progress:

• Fills gap in SBA limited information optimality
• Provides new perspective for distributed algorithm design

Methodology:

• Knowledge-based program framework applicable to other problems
• Information storage relationship theory has universal applicability

2. Citation Potential (★★★★☆)

Likely Citation Scenarios:

• Distributed consensus protocol research
• Knowledge theory applications in computer science
• Fault-tolerant system design
• Blockchain consensus mechanisms

Limitations:

• High theory content may limit engineering field citations

3. Reproducibility (★★★★☆)

Theoretical Results:

• Mathematical proofs verifiable
• Framework clearly reproducible

Implementation:

• Protocol descriptions sufficiently detailed
• But no code implementation

4. Inspiration for Future Research (★★★★★)

Explicit Directions:

• General omission failure model
• Unique decision property
• Practical system implementation

Potential Extensions:

• Other failure models
• Asynchronous environments
• Multi-valued agreement

Applicable Scenarios

1. Ideal Application Scenarios

Large-Scale Synchronous Systems:

• Both node count n and fault tolerance parameter t are large
• SendWaste advantages clear (vs Dwork-Moses)

Resource-Constrained Environments:

• Message size sensitive (e.g., IoT)
• Limited computational capacity
• FloodSet or SendWaste suitable

Theoretical Research:

• Distributed algorithm optimality analysis
• Knowledge theory application research

2. Inapplicable Scenarios

Asynchronous Systems:

• No synchronized clock assumption
• Requires different theoretical framework

Byzantine Environments:

• Presence of malicious nodes
• Requires additional verification mechanisms

Strong Real-Time Requirements:

• Requires deterministic delay guarantees
• May need more aggressive early stopping

3. Practical System Considerations

Integration with Industrial Protocols:

• SendWaste ideas may inspire Raft/Paxos optimization
• Requires adaptation to partial synchrony model

Hybrid Approaches:

• Use limited information in normal cases
• Switch to full information in exceptional cases

Key References (Critical Works)

1. Alpturer, Halpern & van der Meyden (2023): PODC 2023, direct predecessor of this work, studies limited information optimality for EBA
2. Dwork & Moses (1990): I&C, classical work establishing connection between SBA and common knowledge; proposes optimal full information protocol
3. Halpern & Moses (1990): JACM, foundational theory of knowledge and common knowledge in distributed environments
4. Lynch (1996): "Distributed Algorithms" textbook, source of FloodSet protocol
5. Moses & Tuttle (1988): Algorithmica, uses common knowledge for programming synchronous actions
6. Raynal (2002): PRDC, source of Vectorized FloodSet
7. Castañeda et al. (2017): NETYS, source of Counting FloodSet
8. van der Meyden (2024): Under submission, related work on unique decision property

Overall Assessment

• Theoretical Contribution: ★★★★★ (5/5)
• Practical Value: ★★★★☆ (4/5)
• Rigor: ★★★★★ (5/5)
• Innovation: ★★★★☆ (4/5)
• Completeness: ★★★☆☆ (3/5, limited by extended abstract format)

Comprehensive Evaluation: This is a high-quality theoretical computer science paper making important contributions to optimality analysis of distributed consensus protocols. The proposal of the SendWaste protocol demonstrates how theoretical insights guide practical system design. Although lacking experimental validation, rigorous theoretical analysis and systematic protocol comparison make it an important reference in the field. For scholars researching distributed algorithms, knowledge theory applications, or fault-tolerant system design, this paper provides valuable theoretical tools and analysis methods.