2 citations · 3 across the 5 of their papers we have counts for
5 papers · 1 filter
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
Shang-En Huang, Seth Pettie, Leqi Zhu
Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that…
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
Shang-En Huang, Seth Pettie, Leqi Zhu
It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault […
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen +2
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using pro…
Revisionist Simulations: A New Approach to Proving Space Lower Bounds
Faith Ellen, Rati Gelashvili, Leqi Zhu
Determining the space complexity of -obstruction-free -set agreement for is an open problem. In -obstruction-free protocols, processes are required to return in…
A Complexity-Based Hierarchy for Multiprocessor Synchronization
Faith Ellen, Rati Gelashvili, Nir Shavit +1
For many years, Herlihy's elegant computability based Consensus Hierarchy has been our best explanation of the relative power of various types of multiprocessor synchronization obj…