{"id":"9674c1c6-c629-43e3-af61-9e8c6d383786","arxiv_id":"1908.01455","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors formalize cluster-sending between Byzantine clusters, prove linear lower bounds on message and certificate complexity, and present protocols that achieve these bounds.","lead":"This paper defines the cluster-sending problem, sending a message reliably from one Byzantine cluster to another, and gives lower bounds and optimal protocols. It matters for building sharded and geo-distributed fault-tolerant systems such as blockchains and databases.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's crash lower bound is only proved for nC1≥nC2; the nC2≥nC1 case, needed for RPBS optimality, is asserted without proof and is not obtained by symmetry.","rationale":"The paper formalizes a useful primitive, and the proofs I checked for the nC1≥nC2 case and for the protocol correctness arguments appear consistent. However, Theorem 4.1 is missing half of its proof: the nC2≥nC1 case is asserted but never established, and it is not covered by symmetry because the cluster-sending problem is directional (C1 sends v and C1 must confirm receipt). This missing case is load-bearing because the RPBS protocols are claimed optimal precisely in the regime where the receiving cluster is at least as large as the sending cluster. If the lower bound for that case fails, the optimality claim for RPBS fails; if it holds, a proof still needs to be supplied. The reader's weakest_assumption focused on consensus and network reliability, which is a different concern; the reader also stated that the crash case was fully proven, which is not accurate. I do not find a counterexample in small instances, so the correct response is to require the authors to complete the proof of Theorem 4.1 before the optimality claim is fully trusted. Hence the verdict remains conditional, with the condition being a complete proof of the nC2≥nC1 case.","tokens_in":16081,"tokens_out":32511,"duration_ms":330736,"concrete_test":"Verify the missing case on the smallest non-trivial instance: nC1=3, fC1=1, nC2=5, fC2=2, giving σ2=5. Enumerate all ways a candidate protocol can send exactly 4 messages from C1 to C2. For each message assignment, check whether there exists a choice of 1 faulty C1 sender and 2 faulty C2 receivers such that all messages sent by the remaining 2 C1 senders go only to the faulty C2 receivers. If any assignment has no such blocking choice, σ2 is not a lower bound; if every assignment is blockable, the lower bound holds for this instance and the missing case needs a general combinatorial proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 4.1 states a lower bound for both size orderings via {i,j}, but the proof begins 'We assume i=1, j=2, and nC1≥ nC2' and never returns to the case nC2≥nC1. The cluster-sending problem is asymmetric: C1 sends v and C1 must confirm receipt, so simply swapping cluster names in the proof does not apply. The missing case is exactly the regime where RPBS-(σ2,bcs) and RPBS-(τ2,brs) are used (Prop. 6.5, Theorem 6.6.1), so the optimality of these protocols for nC2≥nC1 rests on an unproved lower bound. A full proof must show that any protocol with ≤σ2−1 messages has a fault pattern (fC1 faulty senders, fC2 faulty receivers) in which no message from a non-faulty C1 replica reaches a non-faulty C2 replica; the supplied top-receiver pigeonhole argument only establishes the analogous statement when the sending cluster is at least as large as the receiving cluster. Without this case, the claim that the protocols have optimal message complexity is not supported.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the cluster-sending problem, in which a value v is sent from cluster C1 to cluster C2 so that all non-faulty replicas of C2 receive v, v is sent only if C1 agreed, and C1 can confirm receipt. After formalizing the model with crash/omission/Byzantine failures, replica signing, and cluster signing, the paper gives broadcast-based protocols (RB-bcs, RB-brs), proves lower bounds on message complexity for crash failures (Theorem 4.1) and on certificate complexity for Byzantine failures with replica signing (Theorem 4.2), and then presents bijective-sending protocols (BS, SPBS, RPBS) that it claims meet these lower bounds and are therefore optimal (Theorem 6.6). The protocols exploit the observation that linear communication between clusters can replace quadratic all-to-all broadcasting.","tokens_in":16316,"tokens_out":19857,"duration_ms":191329,"significance":"If the optimality claims are fully established, the paper identifies a clean primitive for sharded Byzantine fault-tolerant systems and shows that cluster-to-cluster communication can be linear in cluster size, with matching lower bounds under two failure models. The paper's contributions are concrete and falsifiable, and the protocol constructions (bijective and partitioned bijective sending) are elegant and likely reusable. The main caveat is that one of the two cases of the crash lower bound is not proved in the text, and the Byzantine lower bound's second case is only sketched; because these cases are needed for the optimality of the RPBS protocols, the contribution is not yet fully supported.","major_comments":[{"comment":"The theorem states a lower bound for both orderings of nC1 and nC2 via the index i for the larger cluster, but the proof begins \"We assume i = 1, j = 2, and nC1 ≥ nC2\" and never treats i = 2, j = 1. This is not a symmetry argument: C1 is always the sender and must confirm receipt, and the bound counts messages from C1 to C2, so interchanging the cluster names changes the problem. The missing case is exactly the regime used by RPBS-(σ2,bcs) in Theorem 6.6(1). Please give a full proof that any protocol using at most σ2−1 messages has a failure pattern in which no message from a non-faulty C1 replica reaches a non-faulty C2 replica.","section":"Section 4, Theorem 4.1"},{"comment":"The proof of the nC2 ≥ nC1 case is only sketched. The step \"Via a contradiction argument similar to the one used in the proof of Theorem 4.1, one can show...\" needs to be written out, since the quantities involved (nfC1 − fC1, fC2 + 1, 2fC1) are not the same as in the nC1 ≥ nC2 case. More importantly, the concluding indistinguishability argument is incomplete: after partitioning CR into CR,1 and CR,2, each signed by at most fC1 distinct replicas, it is not shown that the receiving cluster cannot tell the two executions apart; in particular the number of certificates per value and the protocol's acceptance rule are not addressed. This case underpins the optimality claim for RPBS-(τ2,brs) in Theorem 6.6(2).","section":"Section 4, Theorem 4.2(2)"}],"minor_comments":[{"comment":"The sentence \"We extend the notations f(·), nf(·), n(·), f(·), and nf(·) to arbitrary sets of replicas\" duplicates f(·) and omits n(·); the notation list should be corrected.","section":"Section 2"},{"comment":"In the proof, \"nf S1 ≥ f(C1) + 1\" should be \"nf S1 ≥ fC1 + 1\", since f(C1) is a set and the count is meant.","section":"Section 5, Proposition 5.3"},{"comment":"The proof uses C both for a cluster and for the set of certificates sent in a run (\"messages C, each message representing a single certificate\"), which makes the argument harder to follow; a different name for the certificate set would help.","section":"Section 4, Theorem 4.2"},{"comment":"The letter P is used both for the chosen subset of a cluster and for a generic element of its partition (\"For each P ∈ partition(P)\"), and the same overloading occurs for z(P); renaming the partition elements would improve readability.","section":"Section 6, Propositions 6.4 and 6.5"},{"comment":"The phrase \"Byzantine failures and replica sending\" should read \"Byzantine failures and replica signing\" to match the terminology used throughout the paper.","section":"Theorem 6.6(2)"},{"comment":"Reference [22] appears as \"33nd International Symposium on Distributed Computing\"; the ordinal should be \"33rd\".","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper is a full version of a DISC 2019 brief announcement. The main substantive gap is the unproved nC2 ≥ nC1 case of Theorem 4.1, which is needed for the optimality of RPBS; I would like to see that proof supplied, together with a fully written out version of Theorem 4.2(2). I do not see a fundamental obstacle, but the current text does not yet support the optimality claim for those protocols."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe fault-tolerant cluster-sending paper is a solid theory contribution. It defines a clean primitive—sending a value reliably from one Byzantine cluster to another under crash or Byzantine failures—proves lower bounds that are linear in the cluster sizes, and presents protocols (bijective sending and partitioned variants) that match those bounds. The lower bounds appear to be genuinely new; the literature on consensus and reliable broadcast doesn't treat this multi-cluster, multi-sender, multi-receiver problem with confirmation.\n\nWhat the paper does well: the crash lower bound is carefully argued, the protocol correctness proofs are detailed, and the complexity analysis is honest. The protocols are practical in spirit, and the matching bounds make the main claim convincing. I also appreciate the explicit treatment of cluster signing versus replica signing.\n\nThe main soft spot is Theorem 4.1. The theorem states a lower bound for both size orderings, but the proof only handles nC1 >= nC2 and never returns to the other case. The cluster-sending problem is not symmetric—C1 sends and C1 must confirm—so this isn't an automatic swap. That said, the missing case does have a dual proof (swap the roles of senders and receivers in the pigeonhole argument), so the result is likely correct. Still, the authors should write it out, because the optimality of the RPBS protocols for nC2 >= nC1 depends on it.\n\nTheorem 4.2's Byzantine lower bound is also terse in places—several steps are condensed into 'one can show' and 'via a contradiction argument similar to...'. The argument is plausible, but it needs expansion for a skeptical reader. Also, the paper doesn't discuss how cluster-sending relates to multi-sender reliable broadcast, which seems like a relevant comparison and would help position the novelty.\n\nThe protocols rely on an off-the-shelf consensus protocol within each cluster, so the lower bounds don't count that internal cost. That's a reasonable modeling choice, but it should be stated more prominently.\n\nOverall, the central claims hold up. If the authors fill in the missing lower-bound case and expand the Byzantine proof, this deserves publication. I'd send it to a serious referee without hesitation. It's a useful paper for anyone designing sharded blockchains or geo-scale replicated systems.","headline":"A solid formalization of a useful cluster-sending primitive with mostly sound lower bounds and matching protocols; the crash lower bound misses one case, but it is easily patched.","tokens_in":16814,"tokens_out":7026,"would_cite":true,"duration_ms":65927,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper formalizes cluster-sending, proves linear lower bounds for it, and gives protocols that meet them.","keywords":["fault-tolerant distributed systems","Byzantine failures","crash failures","cluster-sending problem","bijective sending","communication complexity","replica signing","cluster signing"],"falsifier":"Run the worst-case crash pattern behind Theorem 4.1 for concrete small clusters, e.g. $n_{C_1}=3$, $f_{C_1}=1$, $n_{C_2}=2$, $f_{C_2}=0$; the claimed bound is $\\sigma_1=2$ messages. A protocol that reliably delivers the value with a single message in that configuration would refute the lower bound, so systematically searching all one-message sender-receiver choices under that crash pattern is a direct test.","tokens_in":15893,"feed_emoji":"📨","tokens_out":5790,"duration_ms":55608,"temperature":0.7,"pith_summary":"The paper formalizes the cluster-sending problem: sending a value from one Byzantine cluster of replicas to another so that every non-faulty replica in the destination receives it, no non-faulty destination replica accepts a value the source never agreed on, and the source can confirm delivery. The main result is a pair of lower bounds — at least $\\sigma_i$ messages under crash failures (Theorem 4.1) and at least $\\tau_i$ certificates under Byzantine failures with replica signing (Theorem 4.2) — both linear in the cluster sizes. The paper then constructs protocols (BS, SPBS, RPBS) based on bijective sending that match these bounds, so cross-cluster communication need not pay quadratic broadcast costs. A sympathetic reader would care because this supplies a foundational primitive for sharded geo-scale Byzantine systems, where clusters must cooperate without all replicas talking to all replicas.","feed_headline":"One Byzantine cluster can send to another with linear messages","feed_subtitle":"Lower bounds matched by new protocols make cross-cluster communication practical.","key_machinery":"Bijective sending is the load-bearing mechanism: choose equal-sized subsets $S_1 \\subseteq C_1$ and $S_2 \\subseteq C_2$, fix a bijection between them, and have each selected sender send the agreed value to its matched receiver. Because the sets are large enough that at least one non-faulty sender is paired with a non-faulty receiver, that receiver broadcasts the value inside $C_2$, giving receipt and confirmation. Partitioned bijective sending generalizes this to unequal clusters by cutting the larger cluster into $c$-partitions and running independent bijections for enough partitions; the lower-bound proofs use counting arguments over worst-case faulty senders and receivers. The identity that carries the argument is the relation between the required number of non-faulty sender-receiver pairs ($f_{C_2}+1$ for cluster signing, $f_{C_1}+1$ for replica signing) and the chosen subset sizes.","core_discovery":"The paper's central claim is that the cost of reliably sending a message between two Byzantine clusters is fundamentally linear, not quadratic. Under crash failures, any correct protocol must exchange at least $\\sigma_i$ messages, where $\\sigma_i$ counts the smallest number of sender-receiver pairs that survive the worst crash pattern; under Byzantine failures with replica signing, any correct protocol must exchange at least $\\tau_i$ certificates signed by distinct sender replicas. These bounds hold for asynchronous reliable communication and do not depend on delivery timing. The paper further claims that the bijective-sending protocols BS-bcs, BS-brs, and the partitioned variants SPBS and RPBS attain these bounds under the stated resilience conditions ($n_C > 3f_C$ with cluster signing or crash/omission failures, $n_C > 4f_C$ with replica signing), giving optimal communication complexity.","pith_inferences":["A fair end-to-end comparison in practice must add the local consensus cost inside each cluster, which the lower bounds deliberately exclude; for very small clusters that cost could dominate the linear cross-cluster count.","The linear bound suggests cross-shard transactions in sharded Byzantine databases can be built from this primitive; the protocols here would provide the inter-shard send step.","One testable extension is to benchmark the partitioned protocols on highly unequal cluster sizes, where certificate emulation's $O(\\|v\\| + f_{C_1})$ message size may make broadcast-based baselines competitive despite higher message counts."],"forward_implications":["No cluster-sending protocol can beat roughly $\\max(n_{C_1}, n_{C_2})$ messages or certificates, so the linear floor is now a design target.","Sharded Byzantine systems can send values between clusters with only linear wide-area messages instead of quadratic all-to-all communication.","With cluster signing, message size stays $O(\\|v\\|)$; with replica signing, certificates can be emulated at message size $O(\\|v\\| + f_{C_1})$ or optimized when certificates have constant size.","The protocols are one-way and leaderless, so they remain correct under dynamically changing faulty sets and do not require an acknowledgement phase in the reliable network model."],"supporting_citations":[{"why":"Supplies the practical Byzantine consensus protocol used as the off-the-shelf agreement step inside each sending cluster.","marker":"[10]"},{"why":"Provides the extended treatment of practical Byzantine fault tolerance that underpins the assumed intra-cluster consensus.","marker":"[11]"},{"why":"Supplies the reliable broadcasting background used to build the baseline RB cluster-sending protocols.","marker":"[28]"},{"why":"Provides Paxos as the canonical consensus protocol supporting the assumption that replicas in a cluster can agree on a value.","marker":"[29]"},{"why":"Establishes the public-key cryptography infrastructure that implements replica signing.","marker":"[31]"},{"why":"Provides threshold signatures that implement cluster signing.","marker":"[38]"}],"fun_headline_variants":["Optimal cluster sending: linear messages between Byzantine clusters","Byzantine clusters talk reliably with linear cost","Cluster-sending made optimal under Byzantine faults","Linear message complexity for cross-cluster sending","Fault-tolerant cluster sending hits lower bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The protocols assume replicas inside a cluster can reach agreement with an off-the-shelf consensus protocol and that messages sent by non-faulty replicas eventually arrive; if intra-cluster consensus is unavailable or the network can drop messages indefinitely, the correctness proofs and linear lower bounds no longer apply.","fun_headline_variants_meta":{"raw":{"variants":["Optimal cluster sending: linear messages between Byzantine clusters","Byzantine clusters talk reliably with linear cost","Cluster-sending made optimal under Byzantine faults","Linear message complexity for cross-cluster sending","Fault-tolerant cluster sending hits lower bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1476,"prompt_tokens":845,"completion_tokens":631,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":461,"completion_tokens_details":{"reasoning_tokens":562}},"tokens_in":461,"tokens_out":631,"duration_ms":6415,"temperature":1.0,"reasoning_tokens":562,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:13:43.000787+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the worst-case crash pattern behind Theorem 4.1 for concrete small clusters, e.g. $n_{C_1}=3$, $f_{C_1}=1$, $n_{C_2}=2$, $f_{C_2}=0$; the claimed bound is $\\sigma_1=2$ messages. A protocol that reliably delivers the value with a single message in that configuration would refute the lower bound, so systematically searching all one-message sender-receiver choices under that crash pattern is a direct test.","supporting_citations":[{"cited_title":"Practical byzantine fault tolerance","cited_arxiv_id":null,"evidence_quote":"Supplies the practical Byzantine consensus protocol used as the off-the-shelf agreement step inside each sending cluster."},{"cited_title":"The implementation of reliable distributed multiprocess systems","cited_arxiv_id":null,"evidence_quote":"Supplies the reliable broadcasting background used to build the baseline RB cluster-sending protocols."},{"cited_title":"Menezes, Scott A","cited_arxiv_id":null,"evidence_quote":"Establishes the public-key cryptography infrastructure that implements replica signing."}],"review_version":1}