4 citations · 7 across the 8 of their papers we have counts for
8 papers · 1 filter
Wait-free approximate agreement on graphs
Dan Alistarh, Faith Ellen, Joel Rybicki
Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to…
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…
Pragmatic Primitives for Non-blocking Data Structures
Trevor Brown, Faith Ellen, Eric Ruppert
We define a new set of primitive operations that greatly simplify the implementation of non-blocking data structures in asynchronous shared-memory systems. The new operations opera…
A General Technique for Non-blocking Trees
Trevor Brown, Faith Ellen, Eric Ruppert
We describe a general technique for obtaining provably correct, non-blocking implementations of a large class of tree data structures where pointers are directed from parents to ch…
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…
Constant-Length Labeling Schemes for Deterministic Radio Broadcast
Faith Ellen, Barun Gorain, Avery Miller +1
Broadcast is one of the fundamental network communication primitives. One node of a network, called the , has a message that has to be learned by all other nodes.…
Simulating a Shared Register in a System that Never Stops Changing
Hagit Attiya, Hyun Chul Chung, Faith Ellen +2
Simulating a shared register can mask the intricacies of designing algorithms for asynchronous message-passing systems subject to crash failures, since it allows them to run algori…
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…