JUMBO: Fully Asynchronous BFT Consensus Made Truly Scalable

• URL: http://arxiv.org/abs/2403.11238v1
• Date: Sun, 17 Mar 2024 14:53:38 GMT
• Title: JUMBO: Fully Asynchronous BFT Consensus Made Truly Scalable
• Authors: Hao Cheng, Yuan Lu, Zhenliang Lu, Qiang Tang, Yuxuan Zhang, Zhenfeng Zhang,
• Abstract summary: FIN-NG adapts a recent signature-free asynchronous common subset protocol FIN (CCS' 23) into the state-of-the-art framework of concurrent broadcast and agreement. We propose JUMBO, a scalable instantiation of Dumbo-NG, with only $bigO(n2)$ complexities for both authenticators and messages.
• Score: 17.532081305310513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus, e.g. Dumbo-NG (CCS' 22) and Tusk (EuroSys' 22), show promising performance through decoupling transaction dissemination and block agreement. However, when executed with a larger number $n$ of nodes, like several hundreds, they would suffer from significant degradation in performance. Their dominating scalability bottleneck is the huge authenticator complexity: each node has to multicast $\bigO(n)$ quorum certificates (QCs) and subsequently verify them for each block. This paper systematically investigates and resolves the above scalability issue. We first propose a signature-free asynchronous BFT consensus FIN-NG that adapts a recent signature-free asynchronous common subset protocol FIN (CCS' 23) into the state-of-the-art framework of concurrent broadcast and agreement. The liveness of FIN-NG relies on our non-trivial redesign of FIN's multi-valued validated Byzantine agreement towards achieving optimal quality. FIN-NG greatly improves the performance of FIN and already outperforms Dumbo-NG in most deployment settings. To further overcome the scalability limit of FIN-NG due to $\bigO(n^3)$ messages, we propose JUMBO, a scalable instantiation of Dumbo-NG, with only $\bigO(n^2)$ complexities for both authenticators and messages. We use various aggregation and dispersal techniques for QCs to significantly reduce the authenticator complexity of original Dumbo-NG implementations by up to $\bigO(n^2)$ orders. We also propose a ``fairness'' patch for JUMBO, thus preventing a flooding adversary from controlling an overwhelming portion of transactions in its output.

Related papers

• FedSGM: A Unified Framework for Constraint Aware, Bidirectionally Compressed, Multi-Step Federated Optimization [7.692336118507715]
  We introduce FedSGM, a unified framework for federated constrained optimization.<n>FedSGM addresses four major challenges in federated learning (FL): functional constraints, communication bottlenecks, local updates, and partial client participation.<n>To our knowledge, FedSGM is the first framework to unify functional constraints, compression, multiple local updates, and partial client participation.
  arXiv  Detail & Related papers  (2026-01-23T17:03:06Z)
• Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding [58.92526489742584]
  We propose provably lossless.<n> verification method that significantly boosts the expected number of accepted tokens.<n>We show that HSD yields consistent improvements in acceptance rates across diverse model families and benchmarks.
  arXiv  Detail & Related papers  (2026-01-09T11:10:29Z)
• Lifefin: Escaping Mempool Explosions in DAG-based BFT [16.7429292215009]
  Lifefin is a generic and self-stabilizing protocol designed to integrate seamlessly with DAG-based BFT protocols.<n>Lifefin allows nodes to escape mempool explosions by committing transactions with bounded resource usage even in adverse conditions.<n>Lifefin achieves comparable transaction throughput while introducing only minimal additional latency to resist similar attacks.
  arXiv  Detail & Related papers  (2025-11-20T00:00:26Z)
• Error Feedback for Muon and Friends [80.90330715662961]
  We introduce EF21-Muon, the first communication-efficient, non-Euclidean LMO-based with rigorous convergence guarantees.<n>Our theory covers non-Euclidean smooth and the more general $(L0, L1)$-smooth setting, matching best-known Euclidean rates and enabling faster convergence under suitable norm choices.
  arXiv  Detail & Related papers  (2025-10-01T08:20:08Z)
• Pipeline Parallelism is All You Need for Optimized Early-Exit Based Self-Speculative Decoding [73.67253077506672]
  Large language models (LLMs) deliver impressive generation quality, but incur very high inference cost.<n>Early-exit based self-speculative decoding (EESD) has emerged to mitigate this cost.<n>We propose Pipeline-Parallel Self-Speculative Decoding (PPSD) that fully pipelines the draft and verification work.
  arXiv  Detail & Related papers  (2025-09-19T04:51:41Z)
• Exact Certification of (Graph) Neural Networks Against Label Poisoning [50.87615167799367]
  We introduce an exact certification method for label flipping in Graph Neural Networks (GNNs) We apply our method to certify a broad range of GNN architectures in node classification tasks. Our work presents the first exact certificate to a poisoning attack ever derived for neural networks.
  arXiv  Detail & Related papers  (2024-11-30T17:05:12Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• A Study on Asynchronous Vote-based Blockchains [4.79997217554732]
  Vote-based blockchains use Byzantine Fault Tolerance consensus protocols to transition from one state to another. This paper proposes a emphvalidated strong BFT consensus model that allows leader-based coordination in asynchronous settings. Our protocol greatly reduces message complexity and is the first one to achieve linear view changes without relying on threshold signatures.
  arXiv  Detail & Related papers  (2024-09-12T15:54:40Z)
• Byzantine-resilient Federated Learning Employing Normalized Gradients on Non-IID Datasets [23.640506243685863]
  In practical federated learning (FLNGA) the presence of malicious attacks and data heterogeneity often introduces biases into the learning process. We propose a Normalized Gradient unit (Fed-M) model which normalizes uploaded local gradients to be before aggregation, achieving a time of $mathcalO(pM)$.
  arXiv  Detail & Related papers  (2024-08-18T16:50:39Z)
• Theorem-Carrying-Transaction: Runtime Certification to Ensure Safety for Smart Contract Transactions [8.32630869646569]
  We present a viable technological roadmap for the community toward this ambitious goal. Our technology, called Theorem-Carrying-Transaction (TCT), combines the benefits of concrete execution and symbolic proofs. Our prototype incurs a negligible runtime overhead, two orders of magnitude lower than a state-of-the-art approach.
  arXiv  Detail & Related papers  (2024-08-12T20:27:41Z)
• FORAY: Towards Effective Attack Synthesis against Deep Logical Vulnerabilities in DeFi Protocols [7.413607595641641]
  We introduce Foray, a highly effective attack synthesis framework against deep logical bugs in DeFi protocols. Based on our DSL, we first compile a given DeFi protocol into a token flow graph, our graphical representation of DeFi protocols. Then, we design an efficient sketch generation method to synthesize attack sketches for a certain attack goal.
  arXiv  Detail & Related papers  (2024-07-08T19:35:48Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters.
  arXiv  Detail & Related papers  (2023-10-21T18:38:13Z)
• DFedADMM: Dual Constraints Controlled Model Inconsistency for Decentralized Federated Learning [52.83811558753284]
  Decentralized learning (DFL) discards the central server and establishes a decentralized communication network. Existing DFL methods still suffer from two major challenges: local inconsistency and local overfitting.
  arXiv  Detail & Related papers  (2023-08-16T11:22:36Z)
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement [0.0]
  We extend the qubit-efficient encoding presented in [Tan et al., Quantum 5, 454 (2021) and apply it to instances of the financial transaction settlement problem constructed from data provided by a regulated financial exchange.
  arXiv  Detail & Related papers  (2023-07-14T06:58:43Z)
• WR-ONE2SET: Towards Well-Calibrated Keyphrase Generation [57.11538133231843]
  Keyphrase generation aims to automatically generate short phrases summarizing an input document. The recently emerged ONE2SET paradigm generates keyphrases as a set and has achieved competitive performance. We propose WR-ONE2SET which extends ONE2SET with an adaptive instance-level cost Weighting strategy and a target Re-assignment mechanism.
  arXiv  Detail & Related papers  (2022-11-13T09:56:24Z)
• Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction [104.41634756395545]
  We study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm. We show FedBiO has complexity of $O(epsilon-1.5)$. Our algorithms show superior performances compared to other baselines in numerical experiments.
  arXiv  Detail & Related papers  (2022-05-03T16:40:22Z)
• BinaryBERT: Pushing the Limit of BERT Quantization [74.65543496761553]
  We propose BinaryBERT, which pushes BERT quantization to the limit with weight binarization. We find that a binary BERT is hard to be trained directly than a ternary counterpart due to its complex and irregular loss landscapes. Empirical results show that BinaryBERT has negligible performance drop compared to the full-precision BERT-base.
  arXiv  Detail & Related papers  (2020-12-31T16:34:54Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  We develop an efficient programming based algorithm for sound verification of ensemble stumps. We demonstrate the first certified defense method for training ensemble stumps and trees with respect to $ell_p$ norm perturbations.
  arXiv  Detail & Related papers  (2020-08-20T03:42:40Z)
• Albatross: An optimistic consensus algorithm [1.1775652117617563]
  We introduce Albatross, a Proof-of-Stake (PoS) blockchain consensus algorithm that aims to combine the best of both worlds. At its heart, Albatross is a high-performing, speculative BFT algorithm that offers strong probabilistic finality. We prove our protocol to be secure under standard BFT assumptions and analyze its performance both on a theoretical and practical level.
  arXiv  Detail & Related papers  (2019-03-04T23:39:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.