6 papers
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…
The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing
Joan Boyar, Faith Ellen, Kim S. Larsen
This work is a continuation of efforts to define and understand competitive analysis of algorithms in a distributed shared memory setting, which is surprisingly different from the…
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…
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…