4 citations · 7 across the 8 of their papers we have counts for
11 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…
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…
Tight Bounds for Restricted Grid Scheduling
Joan Boyar, Faith Ellen
The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remai…
Tight Bounds for Set Disjointness in the Message Passing Model
Mark Braverman, Faith Ellen, Rotem Oshman +2
In a multiparty message-passing model of communication, there are players. Each player has a private input, and they communicate by sending messages to one another over private…