{"id":"f37b7375-728f-4d66-b1fd-f64fd89fc8c8","arxiv_id":"2412.05512","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"ReduceCatch reduces the number of active senders with repeated TDMA broadcasts and then uses CSMA with NACK to recover lost packets, improving latency and throughput of PBFT, Tendermint, and HotStuff in wireless ad hoc networks.","lead":"ReduceCatch is a wireless communication protocol that combines TDMA, CSMA, and NACK to make PBFT, Tendermint, and HotStuff work in dynamic ad hoc wireless networks. The authors built a LoRa-based smart-car testbed, implemented 20 consensus variants, and report that ReduceCatch lowers latency and raises throughput compared to four alternative communication stacks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"ReduceCatch's O(1) active-node reduction is not achieved for the stated NTX=log N, and the evaluation's NTX=3 is below the required threshold, so the theoretical basis for the complexity claims is not established.","rationale":"The reader's conditional verdict is reasonable. My stress-test found a more specific and checkable flaw in the same vicinity: Section IV-B's exponent (2N-2) means the naive choice NTX=log N leaves Θ(N) active nodes, contrary to Table I's footnote. The experimental NTX=3 for votes with N=10 and α=0.5 makes this concrete: expected active nodes ≈9.08, so the reduce phase is not reducing in the tested regime. This does not refute the empirical latency/throughput comparison, which may still hold because the catch phase can recover missing messages within Δ, but it invalidates the claimed asymptotic mechanism and the 'reliable' guarantee, since Δ is finite and losses of NACKs or retransmissions are not bounded. An independent sweep of NTX across the threshold, using the released code, would settle whether active-node reduction is actually responsible for the reported gains. The concern is a mathematical/parameter-constant gap, not a question of author intent.","tokens_in":15314,"tokens_out":10712,"duration_ms":108278,"concrete_test":"Recompute n from the paper's own formula for the main experiment: N=10, α=0.5, NTX=3 gives 10 - 10(0.875)^{18} ≈ 9.08. Then instrument the N-to-N vote phase to count active nodes or NACK messages at α=0.5 with NTX=3,5,6,7; if NACK counts remain Θ(N) until NTX≈7 (≈2 log_2 N) and only then drop to O(1), the Table I claim that NTX=log N yields O(1) active nodes is falsified, and the evaluation's NTX values do not exercise the asymptotic regime claimed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV-B derives n = N - N(1 - α^{NTX})^{(2N-2)} and the Table I footnote asserts O(n)=O(1) when NTX = log N. This does not follow. If NTX = log_{1/α} N, then α^{NTX}=1/N, so n ≈ N(1-e^{-2}) = 0.865N = Θ(N). The correct threshold is α^{NTX}=O(1/N^2), i.e., NTX ≥ 2 log_{1/α} N; the missing factor 2 comes from the (2N-2) exponent. In the experiments (N=10, packet loss α=0.5, NTX=3 for votes), α^{NTX}=1/8 and n = 10 - 10(1-1/8)^{18} ≈ 9.08, so the reduce phase leaves almost every node active. Consequently the O(N log N) N-to-N complexity and the O(1) catch phase are not realized in the tested configuration; the observed latency/throughput gains cannot be attributed to the claimed active-node reduction. Moreover, the catch phase is a fixed Δ-slot window, so even with a correct NTX there is no reliability guarantee: a lost NACK or retransmission is counted as a failure, not handled by a bounded-delay retry. Thus the central 'reliable communication with O(log N) complexity' claim is not supported as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ReduceCatch, a two-phase (reduce and catch) wireless communication protocol that combines TDMA, CSMA, and NACK to implement reliable 1-to-N, N-to-1, and N-to-N communication patterns for partially synchronous BFT consensus in ad hoc wireless networks. The authors claim O(log N) message and time complexity for 1-to-N communication, O(N log N + beta n) for N-to-1, and O(N log N) for N-to-N, assuming NTX = O(log N) transmissions per sender. They adapt PBFT, Tendermint, and HotStuff to single-hop and multi-hop networks, and build a LoRa-based smart-car testbed on which they measure latency and throughput of 20 protocol combinations, reporting that ReduceCatch-based protocols reduce latency and increase throughput relative to CSMA/TDMA with ACK/NACK baselines.","tokens_in":15622,"tokens_out":4589,"duration_ms":48215,"significance":"If the theoretical complexity claims and experimental results held, the paper would be a valuable systems contribution: it ships an open-source, three-layer wireless consensus testbed, implements a broad set of 20 consensus-protocol/MAC-protocol combinations, and directly addresses practical issues in adapting partially synchronous BFT to dynamic wireless networks. The experimental comparison is extensive for a testbed study, and the code release is a concrete strength. However, the core theoretical guarantee of O(1) active-node reduction is based on a miscalculated constant in the stated NTX threshold, and the reliability claim is weakened by the fixed-length catch phase. The experimental evaluation also uses NTX values below the corrected threshold, so the observed gains cannot be attributed to the claimed active-node reduction. These issues are load-bearing for the paper's central claims, though they appear repairable with revised analysis, corrected thresholds, and more careful statistical reporting.","major_comments":[{"comment":"The claim that O(n) = O(1) when NTX = log N does not follow from the formula n = N - N(1 - alpha^{NTX})^{(2N-2)}. If NTX = log_{1/alpha} N, then alpha^{NTX} = 1/N and n is approximately N(1 - e^{-2}) = Theta(N), not O(1). To obtain n = O(1) one needs alpha^{NTX} = O(1/N^2), i.e., NTX >= 2 log_{1/alpha} N plus an additive constant. The missing factor of 2 arises from the (2N-2) exponent. This invalidates the stated O(log N) message/time complexity for 1-to-N and the O(N log N) complexity for N-to-N as derived, and the Table I footnote is incorrect as written.","section":"Section IV-B and Table I"},{"comment":"The evaluation uses NTX = 5 for proposals and NTX = 3 for votes with N = 10 and packet loss rates up to alpha = 0.5. At alpha = 0.5, NTX = 3 gives alpha^{NTX} = 1/8, so n = 10 - 10(1 - 1/8)^{18} is approximately 9.08; almost every node remains active after the reduce phase. Thus the experimental configuration does not realize the O(1) active-node reduction that the paper claims, and the latency/throughput improvements in Figures 5 and 6 cannot be attributed to the reduce phase reducing the number of active nodes to a constant.","section":"Section VII-A and IV-B"},{"comment":"The catch phase has a fixed Delta-slot window, and the text states that 'Failing to complete communications within the Delta time limit is considered a failure.' This means a lost NACK or a lost retransmission is simply counted as a failure, not retried. Consequently, ReduceCatch does not provide the deterministic reliability indicated by the check marks in Table I or by the abstract's 'reliable 1-to-N, N-to-1, and N-to-N communications.' At most it provides probabilistic delivery under favorable loss conditions; the paper should state this explicitly and give the failure probability as a function of Delta, alpha, and N, or else modify the catch phase to provide an eventual-delivery guarantee.","section":"Section IV-C and Table I"},{"comment":"The active-node calculation in Section IV-B assumes independent packet losses with a fixed rate alpha, but Section IV-A and Figure 1 document bursty, correlated losses on the same LoRa hardware. Under correlated losses, repeated transmissions separated by TDMA cycles may still fail together, so the expected number of active nodes after NTX rounds can be much larger than the formula predicts. The paper should either model bursty losses, present measurements of the actual number of active nodes after the reduce phase, or justify why independence is a reasonable approximation for the evaluated settings.","section":"Section IV-A vs. IV-B"},{"comment":"The experimental claims rest on the mean of only five trials per sample point, with no confidence intervals, standard deviations, or statistical tests. Given that the differences reported are sometimes modest (e.g., average improvements of 10.77 s and 3.82 TPM), the reader cannot assess whether the observed advantages are significant or robust. Additionally, NTX and Delta are hand-tuned with no sensitivity analysis, so it is unclear how the results depend on these key parameters. The paper should report variance and ideally show performance as a function of NTX and Delta.","section":"Section VII"},{"comment":"The multi-hop design's safety and liveness argument is only sketched. The text asserts that cluster-local consensus plus global leader consensus 'ultimately ensures' safety and liveness, but it does not specify the inter-cluster communication model, the failure assumptions on routing, or the exact interaction between local consensus and global ordering. Since the multi-hop evaluation is a claimed contribution, this argument needs to be made precise or explicitly deferred with a pointer to a full proof.","section":"Section V-B"}],"minor_comments":[{"comment":"The term 'global standardization time' should be 'global stabilization time (GST)' to match the standard partial-synchrony terminology.","section":"Section III"},{"comment":"The notation 'alpha = 0 : 10% : 50%' is unclear; please write the set of evaluated loss rates explicitly.","section":"Section VII-A"},{"comment":"Tendermint1 and Tendermint2 are used without a clear definition; the paper should state which communication-pattern variant each refers to before the evaluation section.","section":"Section V-A"},{"comment":"The examples in Figure 2 use NTX = 2 or 3 and Delta = 5 or 6, but the relationship between these illustrative values and the theoretical NTX threshold is not discussed; please clarify that the figures are only illustrative.","section":"Section IV-C"},{"comment":"beta is introduced only in a footnote; please define it in the main text before Table I and explain how it is measured or bounded in the experiments.","section":"Table I"},{"comment":"The text says 'FreeRTOS ... occupies only 9 KB of memory' without specifying which memory region or configuration; this is a minor clarity issue.","section":"Section VI-B"}],"recommendation":"major_revision","confidential_remarks":"The paper has a useful experimental platform and a practical motivation, but the theoretical complexity story needs a corrected NTX threshold, and the reliability claim must be qualified to match the fixed-window catch phase. The evaluation should be redone with corrected parameters or with claims that do not rely on the O(1) active-node reduction. I believe the issues are fixable within the scope of a revision, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, this one is worth a look if you care about wireless BFT, but don't take the complexity table at face value.\n\nThe genuinely new thing is ReduceCatch, a two-phase MAC scheme (TDMA reduce, CSMA+NACK catch) tailored to partially synchronous consensus, plus an open LoRa-based testbed with 20 protocol implementations. That is substantial engineering; the code release makes it reproducible, and the comparison across PBFT, Tendermint, and HotStuff is useful.\n\nThe soft spot is in Section IV-B. The active-node calculation uses n = N - N(1 - α^{NTX})^{(2N-2)}. The paper claims NTX = O(log N) suffices to get n = O(1). It does not. With the natural interpretation NTX = log_{1/α} N, α^{NTX} = 1/N and n ≈ 0.865N. You need NTX ≥ 2 log_{1/α} N. So the O(log N) and O(N log N) claims in Table I are unsupported. In the experiments N=10, α=0.5, NTX_vote=3 gives α^{NTX}=1/8 and n≈9, so the reduce phase barely reduces active nodes. The empirical gains are probably real, but they are not explained by the stated theory. Also, the catch phase is a fixed Δ window: a lost NACK or retransmission is just counted as a failure, so there is no reliability guarantee.\n\nThe evaluation reports means of five runs with no error bars, and NTX and Δ are hand-tuned without sensitivity analysis. The independence assumption for packet loss contradicts the bursty losses shown in their own Figure 1. Treat the quantitative claims as indicative rather than definitive.\n\nEven with those problems, I would send this to referees. The testbed, the breadth of implemented protocols, and the empirical comparison are a solid contribution, and the theory can be fixed with a corrected threshold. This is not a desk reject; it needs a major revision, but a serious referee can extract real value from it. I'd bring it to a reading group and cite the testbed; just don't cite the complexity theorem.","headline":"A valuable wireless-consensus testbed and a plausible protocol, but the O(log N) complexity claim rests on a factor-of-two error in the active-node calculation and the evaluation lacks error bars.","tokens_in":16175,"tokens_out":3515,"would_cite":true,"duration_ms":33694,"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":"ReduceCatch is a two-phase communication protocol that claims O(log N) reliability for wireless BFT consensus in partially synchronous ad hoc networks.","keywords":["ReduceCatch","wireless BFT consensus","partially synchronous model","reliable communication patterns","LoRa testbed","CSMA/TDMA","NACK","ad hoc wireless networks"],"falsifier":"Measure packet delivery on a LoRa link under real interference and count active nodes after running the reduce phase with NTX = O(log N) at the paper's target alpha. If the number of nodes still missing messages remains significantly above O(1) across repeated trials—because losses are correlated in time—the stated complexity bounds for the catch phase and the consensus protocol no longer follow.","tokens_in":15110,"feed_emoji":"📡","tokens_out":4936,"duration_ms":43830,"temperature":0.7,"pith_summary":"The paper proposes ReduceCatch, a two-phase wireless communication protocol that gives reliable 1-to-N, N-to-1, and N-to-N message delivery under a partially synchronous network model. The claim is that by first using TDMA to shrink the set of nodes that still need retransmission (the reduce phase) and then using CSMA with NACK for the few stragglers (the catch phase), message complexity drops to O(log N) for one-to-many, O(N log N + beta n) for many-to-one, and O(N log N) for all-to-all, where n is the small number of active nodes left after reducing. The paper then ports PBFT, Tendermint, and HotStuff onto this communication layer and evaluates them on a moving LoRa-based smart-car testbed with 20 protocol combinations. If the complexity bounds hold, partially synchronous BFT consensus becomes practical for dynamic ad hoc wireless networks such as drone swarms and robot teams.","feed_headline":"ReduceCatch cuts wireless consensus overhead to O(log N)","feed_subtitle":"A TDMA reduce phase plus CSMA/NACK catch phase speeds PBFT, Tendermint, and HotStuff on LoRa smart-car trials.","key_machinery":"The central object is the ReduceCatch protocol itself, with two phases. The reduce phase allocates one TDMA slot per node per round and repeats for NTX rounds, spacing a node's repetitions apart so a burst of channel losses does not swallow all copies; after NTX rounds each node counts how many others it has heard and how many have heard it, and a node is considered inactive once it has both received all messages and been received by all others. The probability that a given node becomes inactive is (1 - $\\alpha$^NTX)^(2N-2), so with NTX = O(log N) the number n = N - N(1 - $\\alpha$^NTX)^(2N-2) of active nodes is O(1). The catch phase then switches to CSMA with NACK: active nodes that missed a packet send a NACK within a bound $\\Delta$, the sender retransmits, and $\\Delta$ prevents Byzantine nodes from forcing endless resends. This two-stage design is what converts a broadcast-heavy consensus pattern from O($N^{2}$) or O(N log N) overhead down to the O(log N) or O(N log N) bounds.","core_discovery":"On its own terms, the paper claims that the obstacle to partially synchronous BFT consensus in wireless networks is not the consensus logic but the communication layer: standard CSMA and TDMA with ACK/NACK scale poorly because CSMA suffers collisions and TDMA wastes slots on inactive nodes. ReduceCatch combines the two: a reduce phase uses TDMA to broadcast each sender's packet NTX times in non-consecutive slots so that, under independent packet loss with rate alpha, the expected number of nodes still missing a message becomes O(1) once NTX = O(log N); a catch phase then uses CSMA with NACK so only those few nodes request retransmission. The paper claims this yields the message and time complexities in its comparison table, and that on its testbed the ReduceCatch-enabled consensus protocols achieve lower latency and higher throughput than the four CSMA/TDMA plus ACK/NACK combinations, with the largest gains when packet loss exceeds 10%.","pith_inferences":["Inference: The independent-loss assumption used to set NTX is likely the fragile point; on real LoRa channels with bursty losses, the active-node count after the reduce phase may stay well above O(1), so a practical deployment would need an adaptive NTX or a fallback that expands the catch phase.","Inference: The complexity gains depend on the bound Delta in the catch phase being tight; a Byzantine node can force extra retransmissions within Delta, so the safety/performance trade-off deserves a dedicated analysis.","Inference: The cluster-based multi-hop extension suggests a sharding-like design; one could test whether the per-cluster reduction still pays off when inter-cluster routing overhead dominates."],"forward_implications":["Reliable 1-to-N communication (leader proposal) has message and time complexity O(log N) instead of O(N) or O(N log N) under previous schemes.","N-to-N vote collection in PBFT and Tendermint drops to O(N log N) message and time complexity, removing the quadratic bottleneck of ACK/NACK schemes.","N-to-1 collection in HotStuff and view-change phases costs O(N log N + beta n) time, where n is the O(1) active nodes after reduction.","Merging catch phases of consecutive communication patterns further cuts total latency in consensus rounds.","On the LoRa testbed, ReduceCatch-based consensus improves latency by up to 44.28 seconds and throughput by up to 14.8 TPM over the best-performing non-ReduceCatch baselines."],"supporting_citations":[{"why":"Defines PBFT, one of the three consensus protocols whose prepare/commit and view-change phases ReduceCatch is designed to accelerate.","marker":"[5]"},{"why":"Defines Tendermint, which uses N-to-N or N-to-1 plus 1-to-N communication and requires collecting all view-change messages.","marker":"[6]"},{"why":"Defines HotStuff, whose linear communication pattern relies on N-to-1 and 1-to-N exchanges that ReduceCatch optimizes.","marker":"[7]"},{"why":"Glossy, a synchronous-transmission protocol requiring sub-microsecond timing, illustrates why traditional synchronous wireless approaches do not fit partial synchrony.","marker":"[11]"},{"why":"Chaos, another synchronous flooding protocol with tight time-synchronization demands, serves as a contrast motivating ReduceCatch's asynchronous design.","marker":"[12]"},{"why":"Provides the NACK mechanism that ReduceCatch uses in the catch phase to request retransmission only from nodes that missed a packet.","marker":"[16]"},{"why":"Defines the partially synchronous network model with a global stabilization time (GST), the model under which ReduceCatch's guarantees are stated.","marker":"[30]"},{"why":"A LoRa field study documenting how environmental interference causes bursty, high packet loss, motivating the NTX repetitions in the reduce phase.","marker":"[33]"},{"why":"A LoRa networking survey covering loss characteristics and long-range suitability, supporting the choice of LoRa for the testbed.","marker":"[34]"}],"fun_headline_variants":["Wireless BFT consensus gets a reduce-and-catch speedup","ReduceCatch adapts PBFT, Tendermint, HotStuff to ad hoc wireless","Combined TDMA/CSMA scheme tames wireless consensus latency","O(log N) overhead: wireless BFT consensus scales with ReduceCatch","ReduceCatch enables partially synchronous BFT on wireless testbed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The core reduction assumes that every packet loss is independent with a fixed probability alpha, so that after NTX = O(log N) repetitions the expected number of nodes needing retransmission becomes O(1); on real wireless channels, losses come in bursts, so this expected-count calculation may severely underestimate how many active nodes remain.","fun_headline_variants_meta":{"raw":{"variants":["Wireless BFT consensus gets a reduce-and-catch speedup","ReduceCatch adapts PBFT, Tendermint, HotStuff to ad hoc wireless","Combined TDMA/CSMA scheme tames wireless consensus latency","O(log N) overhead: wireless BFT consensus scales with ReduceCatch","ReduceCatch enables partially synchronous BFT on wireless testbed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000519,"raw_usage":{"total_tokens":2515,"prompt_tokens":946,"completion_tokens":1569,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":562,"completion_tokens_details":{"reasoning_tokens":1472}},"tokens_in":562,"tokens_out":1569,"duration_ms":11283,"temperature":1.0,"reasoning_tokens":1472,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:38:56.293574+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure packet delivery on a LoRa link under real interference and count active nodes after running the reduce phase with NTX = O(log N) at the paper's target alpha. If the number of nodes still missing messages remains significantly above O(1) across repeated trials—because losses are correlated in time—the stated complexity bounds for the catch phase and the consensus protocol no longer follow.","supporting_citations":[{"cited_title":"Practical byzantine fault tolerance,","cited_arxiv_id":null,"evidence_quote":"Defines PBFT, one of the three consensus protocols whose prepare/commit and view-change phases ReduceCatch is designed to accelerate."},{"cited_title":"Hot- stuff: Bft consensus with linearity and responsiveness,","cited_arxiv_id":null,"evidence_quote":"Defines HotStuff, whose linear communication pattern relies on N-to-1 and 1-to-N exchanges that ReduceCatch optimizes."},{"cited_title":"Efficient network flooding and time synchronization with glossy,","cited_arxiv_id":null,"evidence_quote":"Glossy, a synchronous-transmission protocol requiring sub-microsecond timing, illustrates why traditional synchronous wireless approaches do not fit partial synchrony."},{"cited_title":"Chaos: Versatile and efficient all-to-all data sharing and in-network processing at scale,","cited_arxiv_id":null,"evidence_quote":"Chaos, another synchronous flooding protocol with tight time-synchronization demands, serves as a contrast motivating ReduceCatch's asynchronous design."},{"cited_title":"To nack or not to nack? negative acknowledgments in information-centric networking,","cited_arxiv_id":null,"evidence_quote":"Provides the NACK mechanism that ReduceCatch uses in the catch phase to request retransmission only from nodes that missed a packet."},{"cited_title":"Consensus in the presence of partial synchrony,","cited_arxiv_id":null,"evidence_quote":"Defines the partially synchronous network model with a global stabilization time (GST), the model under which ReduceCatch's guarantees are stated."},{"cited_title":"A study of lora: Long range & low power networks for the internet of things,","cited_arxiv_id":null,"evidence_quote":"A LoRa field study documenting how environmental interference causes bursty, high packet loss, motivating the NTX repetitions in the reduce phase."},{"cited_title":"A survey on lora networking: Research problems, current solutions, and open issues,","cited_arxiv_id":null,"evidence_quote":"A LoRa networking survey covering loss characteristics and long-range suitability, supporting the choice of LoRa for the testbed."}],"review_version":1}