Faith Ellen

Q: What Schools Are Affiliated With Faith Ellen

Faith Ellen is affiliated with the following schools: University of California, Berkeley, University of Toronto, University of Washington

Faith Ellen's AcademicInfluence.com Rankings

Faith Ellen

Computer Science

#2777

World Rank

#2908

Historical Rank

Database

#8921

World Rank

#9378

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Faith Ellen Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Faith Ellen is a professor of computer science at the University of Toronto who studies distributed data structures and the theory of distributed computing. She earned her bachelor's degree and master's from the University of Waterloo in 1977 and 1978, respectively, and doctorate in 1982 from the University of California, Berkeley under the supervision of Richard Karp; her dissertation concerned lower bounds for cycle detection and parallel prefix sums. She joined the faculty of the University of Washington in 1983, and moved to Toronto in 1986. From 1997 to 2001, she was the vice chair of SIGACT, the leading international society for theory of computation. From 2006 to 2009, she was chair of the steering committee for PODC, a top international conference for theory of distributed computing. In 2014, she also co-authored the book, Impossibility Results for Distributed Computing.

(See a Problem?)

Faith Ellen's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Non-blocking binary search trees (2010) (196)
Optimal Bounds for the Predecessor Problem and Related Problems (2002) (188)
Relations between concurrent-write models of parallel computation (1984) (178)
Hundreds of impossibility results for distributed computing (2003) (157)
SNZI: scalable NonZero indicators (2007) (107)
A general technique for non-blocking trees (2014) (103)
Optimal bounds for the predecessor problem (1999) (97)
On the space complexity of randomized synchronization (1993) (75)
A Tight Bound for Set Disjointness in the Message-Passing Model (2013) (74)
Limitations of Highly-Available Eventually-Consistent Data Stores (2015) (68)
Obstruction-Free Algorithms Can Be Practically Wait-Free (2005) (61)
Bounds for width two branching programs (1983) (61)
Languages of R-Trivial Monoids (1980) (60)
A universal construction for wait-free transaction friendly data structures (2010) (55)
New Bounds for Parallel Prefix Circuits (1983) (52)
One, two, three . . . infinity: lower bounds for parallel computation (1985) (50)
A Time-Space Tradeoff for Element Distinctness (1987) (48)
The Complexity of Computation on the Parallel Random Access Machine (1993) (44)
Impossibility Results for Distributed Computing (2014) (43)
Universal constructions that ensure disjoint-access parallelism and wait-freedom (2012) (42)
On the Inherent Sequentiality of Concurrent Objects (2012) (41)
Permuting in Place (1995) (41)
Pragmatic primitives for non-blocking data structures (2013) (38)
The amortized complexity of non-blocking binary search trees (2014) (35)
Linear lower bounds on real-world implementations of concurrent objects (2005) (33)
Relationships between broadcast and shared memory in reliable anonymous distributed systems (2004) (33)
Tables Should Be Sorted (On Random Access Machines) (1995) (33)
On the space complexity of randomized synchronization (1998) (29)
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem (1986) (28)
Fully-adaptive algorithms for long-lived renaming (2006) (27)
Tight Bounds for Adopt-Commit Objects (2014) (26)
The parallel complexity of exponentiating polynomials over finite fields (1988) (26)
A homomorphic characterization of regular languages (1982) (25)
On the inherent weakness of conditional synchronization primitives (2004) (24)
Space-Efficient Data Structures, Streams, and Algorithms (2013) (24)
How Hard Is It to Take a Snapshot? (2005) (24)
The space complexity of unbounded timestamps (2007) (21)
The parallel complexity of exponentiating polynomials over finite fields (1985) (20)
New Protocols for Asymmetric Communication Channels (2001) (20)
A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract] (2016) (20)
Space-optimal multi-writer snapshot objects are slow (2002) (19)
An Optimal Implementation of Fetch-and-Increment (2013) (18)
A tight time lower bound for space-optimal implementations of multi-writer snapshots (2003) (18)
Simulating a Shared Register in an Asynchronous System that Never Stops Changing - (Extended Abstract) (2015) (18)
Deterministic Objects: Life Beyond Consensus (2016) (17)
Time lower bounds for implementations of multi-writer snapshots (2007) (17)
Lower bounds for adaptive collect and related objects (2004) (16)
A Space Optimal, Deterministic, Self-Stabilizing, Leader Election Algorithm for Unidirectional Rings (2001) (16)
Time-space tradeoffs for implementations of snapshots (2006) (16)
Constant-Length Labeling Schemes for Deterministic Radio Broadcast (2017) (15)
A little advice can be very helpful (2012) (14)
The complexity of end-to-end communication in memoryless networks (1999) (13)
Obstruction-Free Step Complexity: Lock-Free DCAS as an Example (2005) (12)
Simulations among concurrent-write PRAMs (1988) (12)
Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity (2015) (12)
Restricted Stack Implementations (2005) (11)
Why extension-based proofs fail (2018) (11)
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution (1993) (11)
Lower bounds for parallel computation on linked structures (1990) (11)
A Complexity-Based Hierarchy for Multiprocessor Synchronization (2016) (10)
Revisionist Simulations: A New Approach to Proving Space Lower Bounds (2017) (10)
Retrieval of scattered information by EREW, CREW and CRCW PRAMs (1992) (10)
A Characterization of a Dot-Depth Two Analogue of Generalized Definite Languages (1979) (10)
The complexity of updating multi-writer snapshot objects (2006) (10)
Pointers versus arithmetic in PRAMs (1993) (9)
Emulating a Shared Register in a System That Never Stops Changing (2017) (9)
Bounds for Scheduling Jobs on Grid Processors (2013) (8)
On the inherent weakness of conditional primitives (2006) (8)
Tight bounds for anonymous adopt-commit objects (2011) (7)
Lower Bounds for the Cycle Detection Problem (1983) (7)
Towards understanding exclusive read (1989) (7)
Toward Understanding Exclusive Read (1990) (7)
Efficient synchronous snapshots (2004) (7)
On generalized locally testable languages (1984) (7)
Wait-free approximate agreement on graphs (2021) (7)
Estimating the maximum (2005) (6)
On Searching Sorted Lists: A Near-Optimal Lower Bound (1998) (6)
The complexity of updating snapshot objects (2011) (6)
End to End Communication (1998) (6)
Faster than optimal snapshots (for a while): preliminary version (2012) (6)
Graph Minors and Reliable Single Message Transmission (2005) (6)
Tight Size Bounds for Packet Headers in Narrow Meshes (2000) (6)
Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast (2020) (6)
Maintaining Information About Nearby Processors in a Mobile Environment (2006) (6)
Reductions and Extension-Based Proofs (2021) (5)
A complexity-based classification for multiprocessor synchronization (2019) (5)
Atomic Snapshots from Small Registers (2015) (4)
Brief Announcement: Why Extension-Based Proofs Fail (2020) (4)
Lower Bounds in Distributed Computing (2000) (3)
Upper and Lower Bounds on the Power of Advice (2016) (3)
Short Headers Suffice for Communication in a DAG with Link Failures (2000) (3)
On the Power of Concurrent-Write PRAMs With Read-Only Memory (1989) (3)
Efficient Fetch-and-Increment (2012) (3)
Separating the Power of EREW and CREW PRAMs with Small Communication Width (1993) (3)
A Generalized Setting for Fixpoint Theory (1979) (2)
Randomized distributed online algorithms against adaptive offline adversaries (2020) (2)
Extension-Based Proofs for Synchronous Message Passing (2021) (2)
Bounds on Certain Multiplications of Affine Combinations (1992) (2)
Constant-Length Labeling Schemes for Deterministic Radio Broadcast (2021) (2)
Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity (2018) (1)
Concurrent Data Structures (2016) (1)
Wait-Free Universal Constructions that ensure Timestamp-Ignoring Disjoint-Access Parallelism (2013) (0)
Upper and Lower Bounds on the Power of Advice Arkadev Chattopadhyay (2016) (0)
D C ] 1 0 A ug 2 01 7 Simulating a Shared Register in a System that Never Stops Changing ∗ (2018) (0)
WHY EXTENSION-BASED (2023) (0)
Infrastructure Issues Related to Theory of Computing Research (1996) (0)
Preface (1990) (0)
Space Lower Bounds for the Signal Detection Problem (2020) (0)
Preface (2020) (0)
The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing (2018) (0)
Session details: R5 (2009) (0)
Session details: Brief announcements (2008) (0)
Tight Bounds for an Online Bin Packing Problem (2014) (0)
Edsger W. Dijkstra Prize in Distributed Computing 2019 - Call for Nominations (2019) (0)
Introduction to the special issue DISC 2003 (2005) (0)
Erratum (2018) (0)
Session details: Session 2 (2017) (0)
Permuting (1990) (0)
Tight Bounds for Restricted Grid Scheduling (2014) (0)
Retrieval of scattered information by EREW, CREW, and CRCW PRAMs (1995) (0)
Preface (2020) (0)
Tight Bounds for Adopt-Commit Objects (2013) (0)
Universal constructions that ensure disjoint-access parallelism and wait-freedom (2016) (0)
Strategic directions in research in theory of computing (1997) (0)
A complexity-based classification for multiprocessor synchronization (2019) (0)
Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract) (2016) (0)
2019 Edsger W. Dijkstra Prize in Distributed Computing (2019) (0)
The Step Complexity of Multidimensional Approximate Agreement (2022) (0)
Distributed Computing, 17th International Conference, DISC 2003, Sorrento, Italy, October 1-3, 2003, Proceedings (2003) (0)
Session details: Coherency and concurrency (2011) (0)

This paper list is powered by the following services:

Other Resources About Faith Ellen

en.wikipedia.org

What Schools Are Affiliated With Faith Ellen?

Faith Ellen is affiliated with the following schools:

Faith Ellen's Academic­Influence.com Rankings