Faith Ellen

According to our database1, Faith Ellen
  • authored at least 115 papers between 1979 and 2017.
  • has a "Dijkstra number"2 of three.

Awards

ACM Fellow

ACM Fellow 2014, "For contributions to data structures, and the theory of distributed and parallel computing.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Limitations of Highly-Available Eventually-Consistent Data Stores.
IEEE Trans. Parallel Distrib. Syst., 2017

Pragmatic Primitives for Non-blocking Data Structures.
CoRR, 2017

A General Technique for Non-blocking Trees.
CoRR, 2017

Revisionist Simulations: A New Approach to Proving Space Lower Bounds.
CoRR, 2017

Constant-Length Labeling Schemes for Deterministic Radio Broadcast.
CoRR, 2017

Simulating a Shared Register in a System that Never Stops Changing.
CoRR, 2017

2016
Upper and Lower Bounds on the Power of Advice.
SIAM J. Comput., 2016

Universal constructions that ensure disjoint-access parallelism and wait-freedom.
Distributed Computing, 2016

A Complexity-Based Hierarchy for Multiprocessor Synchronization.
CoRR, 2016

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract].
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Concurrent Data Structures.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Deterministic Objects: Life Beyond Consensus.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract).
Proceedings of the 20th International Conference on Principles of Distributed Systems, 2016

2015
Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.
J. ACM, 2015

Simulating a Shared Register in an Asynchronous System that Never Stops Changing - (Extended Abstract).
Proceedings of the Distributed Computing - 29th International Symposium, 2015

Limitations of Highly-Available Eventually-Consistent Data Stores.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Atomic Snapshots from Small Registers.
Proceedings of the 19th International Conference on Principles of Distributed Systems, 2015

2014
Impossibility Results for Distributed Computing
Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, 2014

Tight Bounds for Adopt-Commit Objects.
Theory Comput. Syst., 2014

Tight Bounds for an Online Bin Packing Problem.
CoRR, 2014

A general technique for non-blocking trees.
Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2014

The amortized complexity of non-blocking binary search trees.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013
Tight Bounds for Set Disjointness in the Message Passing Model
CoRR, 2013

An Optimal Implementation of Fetch-and-Increment.
Proceedings of the Distributed Computing - 27th International Symposium, 2013

Pragmatic primitives for non-blocking data structures.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

A Tight Bound for Set Disjointness in the Message-Passing Model.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Bounds for Scheduling Jobs on Grid Processors.
Proceedings of the Space-Efficient Data Structures, 2013

2012
On the Inherent Sequentiality of Concurrent Objects.
SIAM J. Comput., 2012

Efficient Fetch-and-Increment.
Proceedings of the Distributed Computing - 26th International Symposium, 2012

A little advice can be very helpful.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Universal constructions that ensure disjoint-access parallelism and wait-freedom.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Faster than optimal snapshots (for a while): preliminary version.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

2011
The complexity of updating snapshot objects.
J. Parallel Distrib. Comput., 2011

Fully-adaptive algorithms for long-lived renaming.
Distributed Computing, 2011

Tight bounds for anonymous adopt-commit objects.
Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

2010
A universal construction for wait-free transaction friendly data structures.
Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

Non-blocking binary search trees.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

2008
The space complexity of unbounded timestamps.
Distributed Computing, 2008

2007
Time lower bounds for implementations of multi-writer snapshots.
J. ACM, 2007

The Space Complexity of Unbounded Timestamps.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

SNZI: scalable NonZero indicators.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

The complexity of updating multi-writer snapshot objects.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

2006
On the inherent weakness of conditional primitives.
Distributed Computing, 2006

Relationships between broadcast and shared memory in reliable anonymous distributed systems.
Distributed Computing, 2006

Fully-Adaptive Algorithms for Long-Lived Renaming.
Proceedings of the Distributed Computing, 20th International Symposium, 2006

Time-space tradeoffs for implementations of snapshots.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Maintaining Information About Nearby Processors in a Mobile Environment.
Proceedings of the Distributed Computing and Networking, 8th International Conference, 2006

The Complexity of Updating Multi-writer Snapshot Objects.
Proceedings of the Distributed Computing and Networking, 8th International Conference, 2006

2005
Graph Minors and Reliable Single Message Transmission.
SIAM J. Discrete Math., 2005

Estimating the maximum.
J. Algorithms, 2005

Introduction to the special issue DISC 2003.
Distributed Computing, 2005

Obstruction-Free Step Complexity: Lock-Free DCAS as an Example.
Proceedings of the Distributed Computing, 19th International Conference, 2005

Obstruction-Free Algorithms Can Be Practically Wait-Free.
Proceedings of the Distributed Computing, 19th International Conference, 2005

Restricted Stack Implementations.
Proceedings of the Distributed Computing, 19th International Conference, 2005

How Hard Is It to Take a Snapshot?.
Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

Linear Lower Bounds on Real-World Implementations of Concurrent Objects.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems.
Proceedings of the Distributed Computing, 18th International Conference, 2004

On the inherent weakness of conditional synchronization primitives.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Efficient synchronous snapshots.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Lower bounds for adaptive collect and related objects.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

2003
Hundreds of impossibility results for distributed computing.
Distributed Computing, 2003

A tight time lower bound for space-optimal implementations of multi-writer snapshots.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
Optimal Bounds for the Predecessor Problem and Related Problems.
J. Comput. Syst. Sci., 2002

Space-optimal multi-writer snapshot objects are slow.
Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 2002

2001
A Space Optimal, Deterministic, Self-Stabilizing, Leader Election Algorithm for Unidirectional Rings.
Proceedings of the Distributed Computing, 15th International Conference, 2001

New Protocols for Asymmetric Communication Channels.
Proceedings of the SIROCCO 8, 2001

2000
Lower Bounds in Distributed Computing.
Proceedings of the Distributed Computing, 14th International Conference, 2000

Short Headers Suffice for Communication in a DAG with Link Failures.
Proceedings of the Distributed Computing, 14th International Conference, 2000

Tight Size Bounds for Packet Headers in Narrow Meshes.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999
Optimal Bounds for the Predecessor Problem.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

The Complexity of End-to-End Communication in Memoryless Networks.
Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, 1999

1998
On the Space Complexity of Randomized Synchronization.
J. ACM, 1998

On Searching Sorted Lists: A Near-Optimal Lower Bound
Electronic Colloquium on Computational Complexity (ECCC), 1998

End to End Communication.
Proceedings of the Distributed Computing, 1998

1997
Infrastructure issues related to theory of computing research.
SIGACT News, 1997

Strategic directions in research in theory of computing.
SIGACT News, 1997

Separating the Power of EREW and CREW PRAMs with Small Communication Width.
Inf. Comput., 1997

1996
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.
J. Comput. Syst. Sci., 1996

Pointers versus Arithmetic in PRAMs.
J. Comput. Syst. Sci., 1996

Infrastructure Issues Related to Theory of Computing Research.
ACM Comput. Surv., 1996

1995
Permuting in Place.
SIAM J. Comput., 1995

Retrieval of Scattered Information by EREW, CREW, and CRCW PRAMs.
Computational Complexity, 1995

Tables Should Be Sorted (On Random Access Machines).
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

1994
Bounds on Certain Multiplications of Affine Combinations.
Discrete Applied Mathematics, 1994

1993
Separating the Power of EREW and CREW PRAMs with Small Communication Width.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.
Proceedings of the STACS 93, 1993

On the Space Complexity of Randomized Synchronization.
Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, 1993

Pointers versus Arithmetic in PRAMs.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
Retrieval of scattered information by EREW, CREW and CRCW PRAMs.
Proceedings of the Algorithm Theory, 1992

1990
Toward Understanding Exclusive Read.
SIAM J. Comput., 1990

Preface.
Discrete Applied Mathematics, 1990

Lower Bounds for Parallel Computation on Linked Structures.
SPAA, 1990

Permuting
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
On the Power of Concurrent-Write PRAMs With Read-Only Memory
Inf. Comput., November, 1989

Towards Understanding Exclusive Read.
SPAA, 1989

1988
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Theor. Comput. Sci., 1988

Relations Between Concurrent-Write Models of Parallel Computation.
SIAM J. Comput., 1988

The parallel complexity of exponentiating polynomials over finite fields.
J. ACM, 1988

Simulations Among Concurrent-Write PRAMs.
Algorithmica, 1988

1987
A Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput., 1987

1986
Bounds for Width Two Branching Programs.
SIAM J. Comput., 1986

A Time-Space Tradeoff for Element Distinctness.
Proceedings of the STACS 86, 1986

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985
The Parallel Complexity of Exponentiating Polynomials over Finite Fields
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

1984
On generalized locally testable languages.
Discrete Mathematics, 1984

Relations Between Concurrent-Write Models of Parallel Computation.
Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984

1983
Lower Bounds for the Cycle Detection Problem.
J. Comput. Syst. Sci., 1983

New Bounds for Parallel Prefix Circuits
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Bounds for Width Two Branching Programs
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
A homomorphic characterization of regular languages.
Discrete Applied Mathematics, 1982

1981
Lower Bounds for the Cycle Detection Problem
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980
Languages of R-Trivial Monoids.
J. Comput. Syst. Sci., 1980

1979
A Generalized Setting for Fixpoint Theory.
Theor. Comput. Sci., 1979

A Characterization of a Dot-Depth Two Analogue of Generalized Definite Languages.
Proceedings of the Automata, 1979


  Loading...