On the public citation graph

Breaking the O ( n 2 ) bit barrier

https://doi.org/10.1145/1989727.1989732

0 signed · 114 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-3-540-78524-8_17openalex-snapshot

Lower Bounds on Implementing Robust and Resilient Mediators

inferredcites →https://doi.org/10.1007/s00446-008-0069-xopenalex-snapshot

Lower bound for scalable Byzantine Agreement

inferredcites →https://doi.org/10.1016/j.csi.2007.12.004openalex-snapshot

The anatomy study of server-initial agreement for general hierarchy wired/wireless networks

inferredcites →https://doi.org/10.1038/scientificamerican0302-40openalex-snapshot

The Worldwide Computer

inferredcites →https://doi.org/10.1109/csfw.1997.596799openalex-snapshot

Unreliable intrusion detection in distributed computations

inferredcites →https://doi.org/10.1109/dsn.2006.63openalex-snapshot

Scaling Byzantine Fault-Tolerant Replication toWide Area Networks

inferredcites →https://doi.org/10.1109/focs.2006.77openalex-snapshot

Towards Secure and Scalable Computation in Peer-to-Peer Networks

inferredcites →https://doi.org/10.1109/icpads.2005.104openalex-snapshot

Byzantine Agreement Protocol using Hierarchical Groups

inferredcites →https://doi.org/10.1109/ipdpsw.2010.5470874openalex-snapshot

An empirical study of a scalable Byzantine agreement algorithm

inferredcites →https://doi.org/10.1109/mwc.2004.1368895openalex-snapshot

Designing Secure Sensor Networks

inferredcites →https://doi.org/10.1109/sfcs.1983.48openalex-snapshot

Randomized byzantine generals

inferredcites →https://doi.org/10.1109/sfcs.1985.55openalex-snapshot

The bit extraction problem or t-resilient functions

inferredcites →https://doi.org/10.1109/sffcs.1999.814586openalex-snapshot

Noncryptographic selection protocols

inferredcites →https://doi.org/10.1145/1146381.1146393openalex-snapshot

Distributed computing meets game theory

inferredcites →https://doi.org/10.1145/1294261.1294267openalex-snapshot

Zyzzyva

inferredcites →https://doi.org/10.1145/1529974.1529992openalex-snapshot

BFT

inferredcites →https://doi.org/10.1145/1538788.1538794openalex-snapshot

Contemporary approaches to fault tolerance

inferredcites →https://doi.org/10.1145/1824777.1824788openalex-snapshot

Fast asynchronous Byzantine agreement and leader election with full information

inferredcites →https://doi.org/10.1145/2455.214112openalex-snapshot

Bounds on information exchange for Byzantine agreement

inferredcites →https://doi.org/10.1145/358746.358762openalex-snapshot

On sharing secrets and Reed-Solomon codes

inferredcites →https://doi.org/10.1145/571637.571640openalex-snapshot

Practical byzantine fault tolerance and proactive recovery

inferredcites →https://doi.org/10.5555/1109557.1109667openalex-snapshot

Scalable leader election

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.2139/ssrn.4601578openalex-extracted

Practical and Fast Intensive Validation on Blockchain

inferred← citeshttps://doi.org/10.1007/978-3-030-32101-7_20openalex-snapshot

Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected $$O(n^2)$$ Communication, and Optimal Resilience

inferred← citeshttps://doi.org/10.1007/978-3-030-45388-6_9openalex-snapshot

Sublinear-Round Byzantine Agreement Under Corrupt Majority

inferred← citeshttps://doi.org/10.1007/978-3-030-91014-3_2openalex-snapshot

Byzantine Geoconsensus

inferred← citeshttps://doi.org/10.1007/978-3-031-01877-0openalex-snapshot

Fault-Tolerant Distributed Transactions on Blockchain

inferred← citeshttps://doi.org/10.1007/978-3-031-57853-3_7openalex-snapshot

Adaptive Consensus: Enhancing Robustness in Dynamic Environments

inferred← citeshttps://doi.org/10.1007/978-3-031-91736-3_2openalex-snapshot

Asynchronous Byzantine Consensus with Trusted Monotonic Counters

inferred← citeshttps://doi.org/10.1007/978-3-032-07024-1_20openalex-snapshot

Towards Optimal Parallel Broadcast Under a Dishonest Majority

inferred← citeshttps://doi.org/10.1007/978-3-032-07035-7_6openalex-snapshot

Frosty: Bringing Strong Liveness Guarantees to the Snow Family of Consensus Protocols

inferred← citeshttps://doi.org/10.1007/978-3-319-10879-7_12openalex-snapshot

Reducing the Overhead of MPC over a Large Population

inferred← citeshttps://doi.org/10.1007/978-3-319-25258-2_14openalex-snapshot

Signature-Free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2) Messages, and Constant Time

inferred← citeshttps://doi.org/10.1007/978-3-319-49259-9_21openalex-snapshot

Near-Optimal Self-stabilising Counting and Firing Squads

inferred← citeshttps://doi.org/10.1007/978-3-319-94289-6_10openalex-snapshot

A Decentralized Sharding Service Network Framework with Scalability

inferred← citeshttps://doi.org/10.1007/978-3-642-36594-2_21openalex-snapshot

Communication Locality in Secure Multi-party Computation

inferred← citeshttps://doi.org/10.1007/978-3-662-60531-8_2openalex-snapshot

Trust Factors and Insider Threats in Permissioned Distributed Ledgers

inferred← citeshttps://doi.org/10.1007/978-981-96-9095-4_18openalex-snapshot

Walnut: A Generic Framework with Enhanced Scalability for BFT Protocols

inferred← citeshttps://doi.org/10.1007/s00145-023-09484-0openalex-snapshot

Breaking the $$O(\sqrt{n})$$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party

inferred← citeshttps://doi.org/10.1007/s00236-016-0269-yopenalex-snapshot

Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with $$t<n/3$$ t < n / 3 , $$O(n^2)$$ O ( n 2 ) messages, and constant time

inferred← citeshttps://doi.org/10.1007/s00446-018-0342-6openalex-snapshot

Near-optimal self-stabilising counting and firing squads

inferred← citeshttps://doi.org/10.1007/s00446-020-00384-1openalex-snapshot

Optimal extension protocols for byzantine broadcast and agreement

inferred← citeshttps://doi.org/10.1007/s00446-022-00428-8openalex-snapshot

Communication complexity of byzantine agreement, revisited

inferred← citeshttps://doi.org/10.1007/s00446-023-00458-wopenalex-snapshot

Byzantine consensus is $$\Theta (n^2)$$: the Dolev-Reischuk bound is tight even in partial synchrony!

inferred← citeshttps://doi.org/10.1007/s00446-024-00473-5openalex-snapshot

Communication lower bounds for cryptographic broadcast protocols

inferred← citeshttps://doi.org/10.1007/s42979-024-03405-zopenalex-snapshot

Byzantine and Honest Nodes Distribution in Random Partitions Under an Adaptive Adversary

inferred← citeshttps://doi.org/10.1016/j.comnet.2024.110773openalex-snapshot

PartChain: Scaling blockchain through account-based partitioned sharding

inferred← citeshttps://doi.org/10.1016/j.csi.2023.103820openalex-snapshot

Fast intensive validation on blockchain with scale-out dispute resolution

inferred← citeshttps://doi.org/10.1016/j.jcss.2014.10.005openalex-snapshot

Distributed agreement in dynamic peer-to-peer networks

inferred← citeshttps://doi.org/10.1016/j.jpdc.2022.07.004openalex-snapshot

How to achieve adaptive security for asynchronous BFT?

inferred← citeshttps://doi.org/10.1016/j.tcs.2024.114888openalex-snapshot

Sublinear message bounds of authenticated implicit Byzantine agreement

inferred← citeshttps://doi.org/10.1080/15427951.2016.1199391openalex-snapshot

Leader Election in Sparse Dynamic Networks with Churn

inferred← citeshttps://doi.org/10.1109/access.2022.3175998openalex-snapshot

Reaching Efficient Byzantine Agreements in Bipartite Networks

inferred← citeshttps://doi.org/10.1109/cscwd.2018.8465233openalex-snapshot

ETTF: A Trusted Trading Framework Using Blockchain in E-commerce

inferred← citeshttps://doi.org/10.1109/dsn48063.2020.00058openalex-snapshot

EPIC: Efficient Asynchronous BFT with Adaptive Security

inferred← citeshttps://doi.org/10.1109/icpads53394.2021.00097openalex-snapshot

Boosting Byzantine Protocols in Large Sparse Networks with High System Assumption Coverage

inferred← citeshttps://doi.org/10.1109/icpads53394.2021.00098openalex-snapshot

Simulating Authenticated Broadcast in Networks of Bounded Degree

inferred← citeshttps://doi.org/10.1109/ipdps.2018.00112openalex-snapshot

Tiny Groups Tackle Byzantine Adversaries

inferred← citeshttps://doi.org/10.1109/ipdps.2019.00094openalex-snapshot

Network Size Estimation in Small-World Networks Under Byzantine Faults

inferred← citeshttps://doi.org/10.1109/sp61157.2025.00244openalex-snapshot

Signature-Free Atomic Broadcast with Optimal $O(n^{2})$ Messages and $O(1)$ Expected Time

inferred← citeshttps://doi.org/10.1109/sp63933.2026.00029openalex-snapshot

Scalable Accountable Byzantine Agreement and Beyond

inferred← citeshttps://doi.org/10.1109/srds47363.2019.00024openalex-snapshot

Making Speculative BFT Resilient with Trusted Monotonic Counters

inferred← citeshttps://doi.org/10.1109/srds69199.2025.00016openalex-snapshot

Randomized vs. Deterministic? Practical Randomized Synchronous BFT in Expected Constant Time

inferred← citeshttps://doi.org/10.1109/tdsc.2025.3621057openalex-snapshot

Scaling Blockchain via Dynamic Sharding

inferred← citeshttps://doi.org/10.1109/tifs.2024.3515854openalex-snapshot

Synchronous Byzantine Agreement With O(n) Messages and O(1) Expected Time

inferred← citeshttps://doi.org/10.1109/tifs.2024.3516541openalex-snapshot

Byzantine Fault Tolerance With Non-Determinism, Revisited

inferred← citeshttps://doi.org/10.1109/tpds.2023.3239993openalex-snapshot

On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement

inferred← citeshttps://doi.org/10.1145/2484239.2484269openalex-snapshot

Early-deciding consensus is expensive

inferred← citeshttps://doi.org/10.1145/2611462.2611468openalex-snapshot

Signature-free asynchronous byzantine consensus with t < n/3 and o(n 2 ) messages

inferred← citeshttps://doi.org/10.1145/2785953openalex-snapshot

Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time

inferred← citeshttps://doi.org/10.1145/2902945.2902958openalex-snapshot

Distributed Computing Column 61

inferred← citeshttps://doi.org/10.1145/2902945.2902959openalex-snapshot

Distributed Algorithmic Foundations of Dynamic Networks

inferred← citeshttps://doi.org/10.1145/2976749.2978389openalex-snapshot

A Secure Sharding Protocol For Open Blockchains

inferred← citeshttps://doi.org/10.1145/2976749.2978399openalex-snapshot

The Honey Badger of BFT Protocols

inferred← citeshttps://doi.org/10.1145/3154273.3154333openalex-snapshot

Proof of Work Without All the Work

inferred← citeshttps://doi.org/10.1145/3210377.3210399openalex-snapshot

Breaking the $ilde$Omega($sqrt{n})$ Barrier

inferred← citeshttps://doi.org/10.1145/3212734.3212751openalex-snapshot

Sublinear Message Bounds for Randomized Agreement

inferred← citeshttps://doi.org/10.1145/3293611.3331570openalex-snapshot

Bootstrapping Public Blockchains Without a Trusted Setup

inferred← citeshttps://doi.org/10.1145/3293611.3331629openalex-snapshot

Communication Complexity of Byzantine Agreement, Revisited

inferred← citeshttps://doi.org/10.1145/3318041.3355457openalex-snapshot

SoK

inferred← citeshttps://doi.org/10.1145/3339471openalex-snapshot

Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus

inferred← citeshttps://doi.org/10.1145/3382734.3405708openalex-snapshot

Brief Announcement: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP

inferred← citeshttps://doi.org/10.1145/3457588.3457600openalex-snapshot

Byzantine Agreement with Less Communication

inferred← citeshttps://doi.org/10.1145/3465084.3467484openalex-snapshot

Byzantine Agreement and Leader Election

inferred← citeshttps://doi.org/10.1145/3465084.3467897openalex-snapshot

Breaking the O(√ n)-Bit Barrier

inferred← citeshttps://doi.org/10.1145/3490148.3538588openalex-snapshot

A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables

inferred← citeshttps://doi.org/10.1145/3491003.3491005openalex-snapshot

Message Complexity of Multi-Valued Implicit Agreement with Shared Random Bits

inferred← citeshttps://doi.org/10.1145/3503042openalex-snapshot

BFT in Blockchains: From Protocols to Use Cases

inferred← citeshttps://doi.org/10.1145/3519935.3520015openalex-snapshot

Byzantine agreement in polynomial time with near-optimal resilience

inferred← citeshttps://doi.org/10.1145/3583668.3594596openalex-snapshot

On the Amortized Communication Complexity of Byzantine Broadcast

inferred← citeshttps://doi.org/10.1145/3583668.3594599openalex-snapshot

Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication

inferred← citeshttps://doi.org/10.1145/3618260.3649736openalex-snapshot

Optimal Load-Balanced Scalable Distributed Agreement

inferred← citeshttps://doi.org/10.1145/3631461.3631548openalex-snapshot

Sublinear Message Bounds of Authenticated Implicit Byzantine Agreement

inferred← citeshttps://doi.org/10.1145/3662158.3662780openalex-snapshot

All Byzantine Agreement Problems Are Expensive

inferred← citeshttps://doi.org/10.1145/3662158.3662792openalex-snapshot

DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication

inferred← citeshttps://doi.org/10.1145/3662158.3662815openalex-snapshot

On the Communication Complexity of Secure Multi-Party Computation With Aborts

inferred← citeshttps://doi.org/10.1145/3732772.3733520openalex-snapshot

Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement

inferred← citeshttps://doi.org/10.1145/3732772.3733553openalex-snapshot

Improved Byzantine Agreement under an Adaptive Adversary

inferred← citeshttps://doi.org/10.1145/3796701.3815918openalex-snapshot

Reaching Univalency with Subquadratic Communication

inferred← citeshttps://doi.org/10.1145/3796701.3815954openalex-snapshot

Balanced and Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Sub-Quadratic Communication

inferred← citeshttps://doi.org/10.1155/2019/3674274openalex-snapshot

MWPoW: Multiple Winners Proof of Work Protocol, a Decentralisation Strengthened Fast-Confirm Blockchain Protocol

inferred← citeshttps://doi.org/10.2200/s01068ed1v01y202012dtm065openalex-snapshot

Fault-Tolerant Distributed Transactions on Blockchain

inferred← citeshttps://doi.org/10.4230/lipics.disc.2020.31openalex-snapshot

Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols

inferred← citeshttps://doi.org/10.4304/jnw.9.4.932-940openalex-snapshot

An Improved Byzantine Fault-tolerant Program for WSNs

inferred← citeshttps://doi.org/10.48550/arxiv.1204.0641openalex-snapshot

Agreement in Directed Dynamic Networks

inferred← citeshttps://doi.org/10.48550/arxiv.1206.1522openalex-snapshot

DEX: Self-healing Expanders

inferred← citeshttps://doi.org/10.48550/arxiv.1608.00214openalex-snapshot

Near-Optimal Self-Stabilising Counting and Firing Squads

inferred← citeshttps://doi.org/10.48550/arxiv.1608.07923openalex-snapshot

Recent Results on Fault-Tolerant Consensus in Message-Passing Networks

inferred← citeshttps://doi.org/10.48550/arxiv.1708.01285openalex-snapshot

Proof of Work Without All the Work: Computationally Efficient Attack-Resistant Systems

inferred← citeshttps://doi.org/10.48550/arxiv.2004.01939openalex-snapshot

A Lower Bound for Byzantine Agreement and Consensus for Adaptive Adversaries using VDFs

inferred← citeshttps://doi.org/10.48550/arxiv.2007.13175openalex-snapshot

Optimal Communication Complexity of Authenticated Byzantine Agreement

inferred← citeshttps://doi.org/10.48550/arxiv.2111.02162openalex-snapshot

Byzantine Agreement with Less Communication: Recent Advances

inferred← citeshttps://doi.org/10.5555/2095116.2095163openalex-snapshot

Towards robust and efficient computation in dynamic peer-to-peer networks

inferred← citeshttps://doi.org/10.7763/ijcte.2015.v7.942openalex-snapshot

New Approach to Improve the Generalized Byzantine Agreement Problem

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.