{"id":"d999e920-527f-488c-a6b1-bfa48ecdd80d","arxiv_id":"2412.01999","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"HAMAVA is a Byzantine-fault-tolerant geo-replication protocol that supports heterogeneous clusters and dynamic membership while preserving safety and liveness.","lead":"This paper introduces a way to keep synchronized database replicas organized into geographic clusters when clusters have different sizes and members join or leave over time. The protocol tolerates malicious failures, works with different local consensus methods, and is evaluated on Google Cloud.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The inter-cluster certificate authenticates individual operations but not the completeness of the round batch, so a Byzantine leader can forward a valid subset to some clusters and Lemma 5's |ops|=|ops'| is unproven; Agreement and Total order fail as written.","rationale":"The weakest load-bearing point is the inter-cluster certificate, but not only in the way the reader stated. The reader identified the implementability of per-operation certificates for arbitrary local consensus; my concern is that, even granting that interface, the formal certificate is too weak for Lemma 5. The proof needs the forwarded batch to be exactly the committed batch, yet the validity check only certifies membership of each included operation. The Byzantine omission attack I describe is a direct counterexample to Theorems 2 and 3 that does not require forging any signature or violating any line of the algorithm. I credit the paper's substantial protocol design, the two instantiations, and the experiments, but the formal safety theorem is the central claim, and this gap is in the formal argument itself. I also note the other gaps the reader raised (timer backoff promised in Lemma 2 but absent from Algorithm 2; leader-election guarantees asserted without proof; code not released), but the batch-completeness issue is the most decisive because it affects safety, not just liveness or scope. A single targeted test with a malicious leader sending a strict subset of a committed batch would settle whether the implementation shares the flaw or whether the paper's abstraction is unfaithful; either outcome requires substantial revision, so the verdict should move to REJECT.","tokens_in":33580,"tokens_out":10791,"duration_ms":114124,"concrete_test":"Take the promised AVA-HotStuff/AVA-BFT-SMaRt implementation (or a faithful simulation of Algorithm 1 with two remote clusters). Make the leader of C_j Byzantine: complete local ordering of a three-operation batch {A,B,C}, then send Inter(r,C_j,{A,B},valid_certs) to f+1 replicas of cluster C1 and Inter(r,C_j,{A,B,C},valid_certs) to f+1 replicas of cluster C2. Run one round and compare the operation sets executed by all correct replicas. If they differ, Theorem 2 is violated as written. If the implementation rejects the subset because its certificate covers the whole batch, then the published per-operation certificate interface (Alg. 1 line 15; Alg. 7 lines 17-19) does not match the implementation, and the \"consensus-agnostic\" claim needs to be re-scoped to protocols that emit whole-batch certificates.","verdict_should_be":"REJECT","load_bearing_attack":"The central safety claim (Theorems 2 and 3) rests on Lemma 5, which says every pair of correct processes receives the same operations from each cluster in each round. The proof of Lemma 5 assumes |ops| = |ops'| for any two delivered Local messages, but the protocol never establishes this. Algorithm 1 line 15 only requires that each operation in ops carry at least 2×f_j+1 signatures from cluster C_j; it does not require ops to be the whole batch that C_j's local TOB committed in round r. A Byzantine leader of C_j can therefore locally order a batch {A,B,C}, then call inter-broadcast(r, {A,B}, certs) toward one remote cluster and inter-broadcast(r, {A,B,C}, certs) toward another. Every operation has a valid quorum certificate, so the receiving correct replicas accept, broadcast Local, set operations_j <- ops, and stop timer_j (Alg. 1 lines 16-19). No remote leader change is triggered because the cluster appears to have sent something. Correct processes in different clusters then execute different sets for C_j in that round, contradicting Theorem 2. This is not fixed by the leader-election or complaint machinery, and it is independent of whether the per-operation certificate interface is implementable in view-based protocols: even with the interface granted, the formal protocol lacks a batch-completeness certificate. The omitted operation is executed only in C_j, so Agreement and Total order do not follow from the stated algorithm.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents HAMAVA, a Byzantine fault-tolerant geo-replication protocol for heterogeneous clusters with dynamic membership. The protocol divides replicas into clusters, lets each cluster order transactions and reconfiguration requests locally, then exchanges the resulting operations between clusters through an inter-cluster broadcast, and finally executes all operations in a deterministic global order. The paper states and proves safety and liveness properties (Theorems 1-3), claims the protocol is consensus-agnostic, and reports experimental results from instantiations with HotStuff and BFT-SMaRt on Google Cloud, including comparisons with GeoBFT and measurements under reconfiguration and failures.","tokens_in":33850,"tokens_out":9710,"duration_ms":84974,"significance":"If the claimed properties were established, HAMAVA would be a meaningful step toward scalable and reconfigurable Byzantine geo-replication: it supports heterogeneous cluster sizes and dynamic membership while preserving per-cluster fault thresholds, and it reduces global communication relative to non-clustered replication. The paper contains a substantial algorithmic presentation, explicit theorem statements and proof attempts, and a broad evaluation that compares against GeoBFT and studies reconfiguration frequency, network latency, and leader failures. However, the central safety proof has a load-bearing gap: the inter-cluster broadcast authenticates individual operations but not the completeness of the round batch, and Lemma 5, on which Theorems 2 and 3 rest, is therefore false as stated. The liveness proof also assumes an exponential timer backoff that does not appear in the protocol code, and the 'consensus-agnostic' claim is stronger than the required certificate interface justifies.","major_comments":[{"comment":"The inter-cluster broadcast authenticates individual operations but not the completeness of the round batch. A Byzantine leader of cluster C_j can locally order a batch {A,B,C} and call inter-broadcast(r,{A,B},certs) toward one remote cluster and inter-broadcast(r,{A,B,C},certs) toward another; line 15 checks only that each operation in ops carries at least 2f_j+1 signatures, so every operation in both messages has a valid certificate. Correct receivers in both clusters broadcast Local, set operations_j <- ops, and stop timer_j (lines 16-19), so no remote leader change is triggered. The proof of Lemma 5 uses the assertion '|ops|=|ops'|' without deriving it from any protocol action, which makes the lemma false as stated. Since Lemma 5 is the premise for Theorems 2 and 3, Agreement and Total order do not follow. The problem also occurs within a single remote cluster: a correct process may receive two valid Local messages from C_j with different subsets and overwrite operations_j at line 18, so two correct processes in the same remote cluster can end the round with different operations_j.","section":"§III (Alg. 1), §IX Lemma 5, §X-B"},{"comment":"The liveness proof assumes that remote-leader-change timers grow unboundedly after GST, as the proof of Lemma 2 states, 'the timer for remote leader change increases exponentially and eventually, all the messages are delivered within a bounded delay after GST.' However, the protocol code does not implement this backoff: Algorithm 2 initializes timer_j to the fixed value Delta and line 20 resets timer_j to Delta after every complaint. Under a partial-synchrony schedule in which message delays exceed Delta, the proof's assumption does not hold, and the conclusion that all correct processes eventually adopt the same correct leader is not established. This gap affects the proof of Theorem 1 (Validity) and the eventual-progress part of the liveness claim.","section":"Alg. 2, lines 3 and 20; §X-A Lemma 2 proof"},{"comment":"The 'consensus-agnostic' claim is stronger than what the protocol actually requires. The local replication mechanism must deliver, for each ordered operation, a commit certificate containing at least 2f_i+1 signatures from distinct members of the cluster (Algorithm 7 lines 17-19; Algorithm 1 line 15). Many total-order broadcast and BFT consensus implementations do not expose per-operation quorum-signed certificates; the paper demonstrates only HotStuff and BFT-SMaRt. The claim should be restricted to local mechanisms that can be adapted to emit such certificates, and the certificate interface should be stated explicitly as part of the total-order broadcast abstraction rather than implied by 'any local replication mechanism.' This issue is independent of the batch-completeness gap in the first major comment: even when per-operation certificates are available, the batch itself is not certified.","section":"Abstract; §II System and Threat Model; Alg. 7"}],"minor_comments":[{"comment":"The sentence 'The Byzantine replicas of C2 and C2 are the red replicas {p3} and {p1,p2} respectively' should presumably read 'C1 and C2' rather than 'C2 and C2.'","section":"§II.A"},{"comment":"The proof refers to 'rb' and 'the validity of reliable broadcast,' but Algorithm 1 uses the AuthenticatedBestEffortBroadcast abstraction abeb at line 16; the abstraction names should be aligned.","section":"§X-A Lemma 1 proof"},{"comment":"The paper alternates between the names HAMAVA and AVA for the same system, and the abstract says 'we present AVA' while the title and body use HAMAVA; the naming should be made consistent.","section":"Title and Abstract"},{"comment":"The caption for the latency-breakdown experiment does not clearly identify which panel corresponds to AVA-BFTSMART and which to AVA-HOTSTUFF, making the left/right labels in the caption hard to follow.","section":"Fig. 4a"}],"recommendation":"major_revision","confidential_remarks":"The batch-completeness flaw in Lemma 5 is the main barrier to accepting the paper's correctness claims. If the authors revise, they should add a batch-level certificate that commits to the whole set of operations ordered in a round, modify Algorithm 1 to verify and preserve that certificate, and re-prove Lemma 5 and the theorems that depend on it. They should also align the liveness proof with the actual timer behavior in Algorithm 2 and re-examine whether the required certificate interface is realizable for their stated local consensus instantiations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, here's my read of Hamava. It tackles a real, open problem: clustered Byzantine replication with dynamic membership and heterogeneous cluster sizes. As far as I can tell from the cited literature, it is the first to combine those properties, and it ships two implementations (HotStuff and BFT-SMaRt) with geo-distributed experiments including a comparison to GeoBFT. The inter-cluster communication design—per-operation quorum certificates and per-cluster f_i thresholds for complaint amplification—is sensible and mostly well explained.\n\nThe problem is in the safety argument, and it's load-bearing. The paper's Lemma 5 claims that in every round, two correct processes receive the same operations from each cluster. The proof says 'by the agreement property of TOB and |ops|=|ops'|, ops and ops' contain the same set.' But the protocol never establishes |ops|=|ops'|. The inter-broadcast (Algorithm 1) requires each operation in ops to carry 2f_j+1 signatures; it does not require ops to be the entire batch that the source cluster's local total-order broadcast committed in that round. A Byzantine leader that locally ordered {A,B,C} in round r can send {A,B} to one remote cluster and {A,B,C} to another. Every forwarded operation has a valid certificate, so the receiving correct replicas accept, broadcast Local, set operations_j <- ops, and stop the timer. No remote leader change triggers, because the cluster appears to have sent something. Correct processes in different clusters then execute different sets for that round, contradicting Theorems 2 and 3. The complaint/leader-change machinery does not catch this, because it only fires when a cluster sends nothing. This is not a minor gap; the central safety theorem is unproven and in fact false for the stated algorithm.\n\nThe liveness side has related soft spots: Lemma 2's proof assumes the remote-leader-change timer grows exponentially, but Algorithm 2 resets it to a fixed Delta; the leader-election module's guarantees are asserted rather than proved; and the paper promises code release but no artifact is included. The experimental figures have no error bars, which is typical for systems papers and not disqualifying, but it means the performance claims are impressions, not measurements.\n\nWho is this for? Researchers working on geo-replicated BFT and membership churn. The idea space and the experimental infrastructure are worth engaging with. But the protocol as written is not safe against a Byzantine leader who cherry-picks which locally ordered operations to forward. That needs to be fixed—most likely by requiring the local TOB to emit a batch-level completeness certificate—before the paper is publishable. If the authors can do that, the paper could be a good contribution. I'd send it to peer review: the problem matters, the work is substantial, and a revision could address the hole. I would not cite the current version as a correct protocol.","headline":"The reconfiguration and heterogeneity contributions are real, but the inter-cluster broadcast has a batch-completeness hole that breaks Agreement and Total order as written.","tokens_in":34433,"tokens_out":2882,"would_cite":false,"duration_ms":27012,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Clustered Byzantine replication can let replicas join and leave clusters, support unequal cluster sizes, and still guarantee agreement and a total order on operations.","keywords":["Byzantine fault tolerance","clustered replication","reconfiguration","dynamic membership","geo-replication","consensus-agnostic","heterogeneous clusters"],"falsifier":"Instantiate the meta-protocol with a local ordering engine that does not expose per-operation quorum signatures, such as a view-based protocol whose only signed artifact is a per-view change summary. If the correct leader of a cluster cannot assemble the required $2f_j+1$ certificate for its own operations (Algorithm 1, line 15), no other cluster will accept its batch and the system will stall even with a correct leader, contradicting the claimed termination; if the acceptance check is loosened instead, a Byzantine leader can ship under-signed operations that make different clusters accept different sets, contradicting Agreement. Either outcome is directly observable with the paper's own protocol description.","tokens_in":33276,"feed_emoji":"🌍","tokens_out":13997,"duration_ms":131522,"temperature":0.7,"pith_summary":"HAMAVA claims that Byzantine-fault-tolerant replicated databases can be both geo-clustered and reconfigurable: replicas in different regions are grouped into clusters that may differ in size, and members may join or leave without a separate global consensus step for membership. The paper proves that this preserves safety and liveness, stated as Validity (every requested operation is eventually executed), Agreement (all correct processes execute the same operations in the same round), and Total order (a consistent execution order across processes). The design is a round-based meta-protocol: clusters order transactions locally, exchange only operations that carry signatures from a quorum of their source cluster, replace misbehaving leaders even in remote clusters, and apply membership changes uniformly at the next round boundary. If correct, the result is a permissioned blockchain or replicated database that churns its membership like a public network while keeping per-cluster Byzantine tolerance. Experiments instantiate the meta-protocol with HotStuff and BFT-SMaRt and report that heterogeneity raises throughput, reconfiguration costs little, and leader failures recover within a timeout.","feed_headline":"Replicas join and leave geo-clusters without breaking safety","feed_subtitle":"Heterogeneous clusters keep agreeing while members churn, and either HotStuff or BFT-SMaRt can run inside.","key_machinery":"The load-bearing object is the operation certificate: each locally ordered operation is shipped to other clusters together with a signature set from at least $2f_j+1$ distinct members of its source cluster $C_j$, and remote replicas accept inter-cluster messages only when every certificate is valid (Algorithm 1, line 15). This certificate is what lets a cluster trust operations it never ordered itself, and the Agreement proof (Lemma 5) derives equality of received operation sets from quorum intersection on these certificates. Three sub-protocols hang off it: inter-cluster broadcast, which sends each batch to only $f_j+1$ remote replicas (at least one correct) that re-broadcast locally; heterogeneous remote leader change, which uses $f_j+1$ and $2f_j+1$ complaint-signature thresholds together with per-cluster counters $cn_j$ and $rcn_j$ to make Byzantine-forced or replayed leader changes impossible; and the Byzantine Reliable Dissemination (BRD) module, an echo/ready broadcast with timestamped valid sets carried across leader changes, which aggregates reconfiguration requests so that a Byzantine leader cannot drop them. Reconfigurations are deliberately handled as an unordered aggregated set in a workflow parallel to transaction ordering, and take effect only at the round boundary, so they never compete with transactions for consensus slots.","core_discovery":"HAMAVA's central claim is that heterogeneous, reconfigurable clustered Byzantine replication is achievable: as long as no cluster has more than one-third Byzantine members, clusters of different sizes can agree on a consistent execution history while replicas join and leave and leaders misbehave. The protocol proceeds in rounds with three stages: in stage one, each cluster orders its transactions with any local total-order broadcast and, in parallel, collects join and leave requests into an unordered set; in stage two, the cluster leader broadcasts the locally ordered operations to other clusters, sending the operations together with certificates of at least $2f_j+1$ signatures from the source cluster to $f_j+1$ members of each remote cluster, where they are re-broadcast locally; in stage three, every replica executes the received operations in a fixed cluster order. If a remote leader withholds its operations, a complaint mechanism that requires $f_j+1$ and then $2f_j+1$ signatures, protected by monotonic complaint counters, triggers the replacement of that remote leader. Reconfigurations are applied only in stage three, so every cluster adopts the same membership for the following round, which the authors prove closes both the forged-certificate and the censorship attacks that stale membership views enable, yielding Theorem 1 (Validity), Theorem 2 (Agreement), and Theorem 3 (Total order). The authors also report implementations over HotStuff and BFT-SMaRt whose measurements show throughput gains from heterogeneity and modest cost from reconfiguration.","pith_inferences":["I read the paper's 'consensus-agnostic' claim as bounded by its certificate interface: a local engine that cannot expose a per-operation quorum signature set would need an adapter before the agreement proofs apply, since only HotStuff and BFT-SMaRt are instantiated and both naturally emit such certificates.","A combination stress test the paper does not run, membership churn arriving in the same round as a leader failure, would exercise the interaction between the reconfiguration workflow and remote leader change, where worst-case recovery timing might differ from the isolated fault scenarios reported.","Because the order of reconfiguration requests within a round is immaterial, the protocol extends naturally to batched membership policies such as admission quotas or per-round rate limits without touching the safety argument.","The signed-complaint channel used for remote leader change is a generic cross-cluster accountability mechanism; the same structure could carry other governance actions, such as auditing a remote cluster or certifying its configuration."],"forward_implications":["Clusters can adopt joins and leaves at every round boundary without a global membership consensus, because reconfiguration sets are collected in parallel with ordering and applied uniformly in stage three.","Heterogeneous deployments are safe: since every inter-cluster message is sized and checked by the target cluster's own $f_j$, large clusters cannot exploit stale smaller thresholds to forge certificates, and small clusters cannot be censored by senders aiming at outdated larger thresholds.","Operators can trade layout for speed: with a fixed number of nodes, splitting into more clusters improves throughput and latency, and placing each cluster inside one region outperforms spreading it across regions.","Leader failure including a Byzantine leader that behaves locally but stalls inter-cluster communication is recoverable: the remote leader change protocol replaces the leader within a configurable timeout, and measured throughput returns to its prior level.","Reconfiguration is cheap in practice: the measured throughput drop during concentrated join and leave churn stays small, at most about 12% for the HotStuff instantiation and 10% for the BFT-SMaRt instantiation in the frequency experiments."],"supporting_citations":[{"why":"Supplies the HotStuff instantiation, one of the two local consensus engines used to substantiate the claim that HAMAVA is consensus-agnostic.","marker":"[9]"},{"why":"Supplies the BFT-SMaRt instantiation, the second local consensus engine on which the paper demonstrates the meta-protocol.","marker":"[36]"},{"why":"The GeoBFT clustered replication design that HAMAVA extends with heterogeneity and reconfiguration, and the experimental baseline in the comparison experiments.","marker":"[27]"},{"why":"The earlier Steward wide-area clustered BFT protocol with a leader-site bottleneck, used as the contrast that motivates the leaderless inter-cluster broadcast design.","marker":"[26]"},{"why":"SmartMerge, a prior reconfiguration-by-merging approach for non-clustered replication that HAMAVA contrasts with to argue it avoids a single consensus bottleneck for membership.","marker":"[31]"},{"why":"Dyno, a prior dynamic BFT protocol that orders membership through consensus instances, the alternative the paper compares against for non-clustered reconfiguration.","marker":"[30]"},{"why":"Defines the partial synchrony timing model that the liveness proofs, timers, and global stabilization time arguments assume.","marker":"[40]"},{"why":"The extended report that carries the full proofs of the lemmas and theorems only stated in this paper, including the sub-protocol correctness arguments.","marker":"[41]"}],"fun_headline_variants":["Heterogeneous clusters support dynamic membership in geo-replication","Reconfigurable geo-replication tolerates join/leave and Byzantine faults","HAMAVA lets clusters differ in size while replicas churn safely","Dynamic membership meets Byzantine fault tolerance in geo-replication","Safety and liveness proven for reconfigurable heterogeneous clusters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The design assumes that whatever local method a cluster uses to order its own transactions can be made to attach, to every ordered operation, a signed certificate from more than two-thirds of that cluster's current members; if a chosen local mechanism cannot produce such per-operation certificates, clusters can neither assemble valid outgoing messages nor verify incoming ones.","fun_headline_variants_meta":{"raw":{"variants":["Heterogeneous clusters support dynamic membership in geo-replication","Reconfigurable geo-replication tolerates join/leave and Byzantine faults","HAMAVA lets clusters differ in size while replicas churn safely","Dynamic membership meets Byzantine fault tolerance in geo-replication","Safety and liveness proven for reconfigurable heterogeneous clusters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000223,"raw_usage":{"total_tokens":1511,"prompt_tokens":1054,"completion_tokens":457,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":372}},"tokens_in":670,"tokens_out":457,"duration_ms":4346,"temperature":1.0,"reasoning_tokens":372,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:57:39.346192+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instantiate the meta-protocol with a local ordering engine that does not expose per-operation quorum signatures, such as a view-based protocol whose only signed artifact is a per-view change summary. If the correct leader of a cluster cannot assemble the required $2f_j+1$ certificate for its own operations (Algorithm 1, line 15), no other cluster will accept its batch and the system will stall even with a correct leader, contradicting the claimed termination; if the acceptance check is loosened instead, a Byzantine leader can ship under-signed operations that make different clusters accept different sets, contradicting Agreement. Either outcome is directly observable with the paper's own protocol description.","supporting_citations":[{"cited_title":"Hot- Stuff: BFT consensus with linearity and responsiveness,","cited_arxiv_id":null,"evidence_quote":"Supplies the HotStuff instantiation, one of the two local consensus engines used to substantiate the claim that HAMAVA is consensus-agnostic."},{"cited_title":"The next 700 BFT protocols,","cited_arxiv_id":null,"evidence_quote":"Supplies the BFT-SMaRt instantiation, the second local consensus engine on which the paper demonstrates the meta-protocol."},{"cited_title":"ResilientDB: Global scale resilient blockchain fabric,","cited_arxiv_id":null,"evidence_quote":"The GeoBFT clustered replication design that HAMAVA extends with heterogeneity and reconfiguration, and the experimental baseline in the comparison experiments."},{"cited_title":"Steward: Scaling Byzantine fault-tolerant replication to wide area networks,","cited_arxiv_id":null,"evidence_quote":"The earlier Steward wide-area clustered BFT protocol with a leader-site bottleneck, used as the contrast that motivates the leaderless inter-cluster broadcast design."},{"cited_title":"Smartmerge: A new approach to reconfiguration for atomic storage,","cited_arxiv_id":null,"evidence_quote":"SmartMerge, a prior reconfiguration-by-merging approach for non-clustered replication that HAMAVA contrasts with to argue it avoids a single consensus bottleneck for membership."},{"cited_title":"Foundations of dynamic BFT,","cited_arxiv_id":null,"evidence_quote":"Dyno, a prior dynamic BFT protocol that orders membership through consensus instances, the alternative the paper compares against for non-clustered reconfiguration."},{"cited_title":"You are where you have been: Sybil detection via geo-location analysis in OSNs,","cited_arxiv_id":null,"evidence_quote":"Defines the partial synchrony timing model that the liveness proofs, timers, and global stabilization time arguments assume."}],"review_version":1}