Faith Ellen

Orcid: 0000-0003-4473-931X

Affiliations:
  • University of Toronto, Department of Computer Science, ON, Canada


According to our database1, Faith Ellen authored at least 113 papers between 1979 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 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 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Revisionist Simulations: A New Approach to Proving Space Lower Bounds.
SIAM J. Comput., 2024

2023
Why Extension-Based Proofs Fail.
SIAM J. Comput., August, 2023

Wait-free approximate agreement on graphs.
Theor. Comput. Sci., February, 2023

2022
The Step Complexity of Multidimensional Approximate Agreement.
Proceedings of the 26th International Conference on Principles of Distributed Systems, 2022

2021
Constant-Length Labeling Schemes for Deterministic Radio Broadcast.
ACM Trans. Parallel Comput., 2021

Space Lower Bounds for the Signal Detection Problem.
Theory Comput. Syst., 2021

Extension-Based Proofs for Synchronous Message Passing.
Proceedings of the 35th International Symposium on Distributed Computing, 2021

Reductions and Extension-Based Proofs.
Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020
Preface.
Theor. Comput. Sci., 2020

Randomized distributed online algorithms against adaptive offline adversaries.
Inf. Process. Lett., 2020

A complexity-based classification for multiprocessor synchronization.
Distributed Comput., 2020

Preface.
Comput. Geom., 2020

Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast.
Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Brief Announcement: Why Extension-Based Proofs Fail.
Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

2019
Emulating a Shared Register in a System That Never Stops Changing.
IEEE Trans. Parallel Distributed Syst., 2019

Tight Bounds for Restricted Grid Scheduling.
Int. J. Found. Comput. Sci., 2019

Edsger W. Dijkstra Prize in Distributed Computing 2019 - Call for Nominations.
Bull. EATCS, 2019

2019 Edsger W. Dijkstra Prize in Distributed Computing.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018
Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.
J. ACM, 2018

The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing.
CoRR, 2018

2017
Limitations of Highly-Available Eventually-Consistent Data Stores.
IEEE Trans. Parallel Distributed Syst., 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 Comput., 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

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, ISBN: 978-3-031-02010-0, 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

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 Distributed Comput., 2011

Fully-adaptive algorithms for long-lived renaming.
Distributed Comput., 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 Comput., 2008

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

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

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

Relationships between broadcast and shared memory in reliable anonymous distributed systems.
Distributed Comput., 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. Discret. Math., 2005

Estimating the maximum.
J. Algorithms, 2005

Introduction to the special issue DISC 2003.
Distributed Comput., 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
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 Comput., 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
Electron. Colloquium Comput. Complex., 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

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

Retrieval of Scattered Information by EREW, CREW, and CRCW PRAMs.
Comput. Complex., 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.
Discret. Appl. Math., 1994

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

Preface.
Discret. Appl. Math., 1990

Lower Bounds for Parallel Computation on Linked Structures.
Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 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.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 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

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.
Discret. Math., 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

1982
A homomorphic characterization of regular languages.
Discret. Appl. Math., 1982

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...