Faith Ellen, Panagiota Fatourou, Joanna Helga and Eric Ruppert,
The Amortized Complexity of Non-blocking Binary Search Trees,
Proceedings of the 33rd Annual ACM Symposium on Principles
of Distributed Computing (PODC), July 2014, to appear.
Trevor Brown, Faith Ellen, Eric Ruppert,
A general technique for non-blocking trees,
Proceedeings of the 19th ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming (PPOPP),
February 2014, pages 329-342.
Mark Braverman, Faith Ellen, Rotem Oshman, Toni Pitassi
and Vinod Vaikuntanathan,
Tight Bounds for Set Disjointness in the Message Passing Model,
Proceedings of the 54th Annual IEEE Symposium on
Foundations of Computer Science, (FOCS),
October 2013, pages 668-677.
A brief announcement of this work also appears in
Proceedings of the 27th International Symposium on Distributed Computing
(DISC),
Lecture Notes in Computer Science, volume 8205,
October 2013,
pages 567--568.
Faith Ellen and Philipp Woelfel,
An Optimal Implementation of Fetch-and-Increment,
Proceedings of the 27th International Symposium on Distributed Computing
(DISC),
Lecture Notes in Computer Science, volume 8205,
October 2013,
pages 284--298.
Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan,
Brief Announcement: Private Channel Models in Multi-party
Communication Complexity,
Proceedings of the 27th International Symposium on Distributed Computing
(DISC),
Lecture Notes in Computer Science, volume 8205,
October 2013,
pages 575--576.
Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani and
Corentin Travers,
Wait-Free Universal Constructions that Ensure Timestamp-Ignoring
Disjoint-Access Parallelism,
5th Workshop on the Theory of Transactional Memory (WTTM 2013),
October 2013, 7 pages.
Joan Boyar and Faith Ellen,
Bounds for Scheduling Jobs on Grid Processors,
Space-Efficient Data Structures, Streams, and Algorithms,
Lecture Notes in Computer Science, Vol. 8066, August 2013, pages 12--26.
Trevor Brown, Faith Ellen, and Eric Ruppert,
Pragmatic Primitives for Non-blocking Data Structures,
Proceedings of the 32nd Annual ACM Symposium on Principles
of Distributed Computing (PODC),
July 2013, pages 13--22.
Faith Ellen, Vijaya Ramachandran, and Philipp Woelfel,
Efficient Fetch-and-Increment,
Proceedings of the 26th International Symposium on Distributed Computing
(DISC),
October 2012, pages 16-30.
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen,
Faster than Optimal Snapshots (for a While),
Proceedings of the 31st Annual ACM Symposium on Principles
of Distributed Computing (PODC),
July 2012, pages 375-383.
Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, and Corentin Travers,
Universal Constructions that Ensure Disjoint-Access Parallelism and Wait-Freedom,
Proceedings of the 31st Annual ACM Symposium on Principles
of Distributed Computing (PODC),
July 2012, pages 115-124.
Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi,
A Little Advice can be Very Helpful,
23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
January 2012, pages 615-625.
James Aspnes and Faith Ellen,
Tight Bounds for Anonymous Adopt-Commit Objects,
23rd Annual ACM Symposium on Parallel Algorithms and Architectures
(SPAA),
June 2011, pages 317-324.
Faith Ellen, Panagiota Fatourou, and Eric Ruppert,
Non-blocking Binary Search Trees,
Proceedings of the 29th Annual ACM Symposium on Principles
of Distributed Computing (PODC),
July 2010, pages 131--140.
Phong Chuong, Faith Ellen, and Vijaya Ramachandran,
A Universal Construction for Wait-Free
Transaction Friendly Data Structures,
Proceedings of the 22nd
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
June 2010, pages 335-344.
Faith Ellen, Panagiota Fatourou, and Eric Ruppert,
The Space Complexity of Unbounded Timestamps,
Proceedings of the 21st International Symposium on Distributed Computing
(DISC),
Lecture Notes in Computer Science, volume 4731,
September 2007, pages 223-237.
Faith Ellen, Yossi Lev, Victor Luchangco, and Mark Moir,
SNZI: Scalable NonZero Indicators,
Proceedings of the 26th Annual ACM Symposium on Principles
of Distributed Computing (PODC),
August 2007, pages 13-22.
Hagit Attiya, Faith Ellen, and Panagiota Fatourou,
The Complexity of Updating Multi-Writer Snapshot Objects,
Proceedings of the
8th International Conference on
Distributed Computing and Networking (ICDCN),
December 2006, pages 319--330.
A brief announcement of this work also appears in
Proceedings of the 26th Annual ACM Symposium on Principles
of Distributed Computing (PODC),
August 2007, pages 318-319.
Faith Ellen, Sivaramakrishnan Subramanian, and Jennifer Welch,
Maintaining Information about Nearby Processors in a Mobile Environment
,
Proceedings of the
8th International Conference on
Distributed Computing and Networking (ICDCN),
December 2006, pages 193--202.
Alex Brodsky, Faith Ellen, and Philipp Woelfel,
Fully Adaptive Algorithms for Long-Lived Renaming,
Proceedings of the 20th International Symposium on Distributed Computing (DISC),
Lecture Notes in Computer Science, volume 4167,
September 2006, pages 413--427.
Panagiota Fatourou, Faith Ellen Fich, and Eric Ruppert,
Time-Space Tradeoffs for Implementations of Snapshots,
38th Annual ACM Symposium on Theory of Computing (STOC),
May 2006, pages 169--178.
Faith Ellen Fich, Danny Hendler, and Nir Shavit,
Linear Lower Bounds on Real-World Implementations of
Concurrent Objects,
Proceedings of the 46th Annual Symposium on Foundations of Computer
Science (FOCS),
October 2005, pages 165--173.
Matei David, Alex Brodsky, and Faith Ellen Fich,
Restricted Stack Implementations,
Proceedings of the 19th International Symposium on Distributed Computing (DISC),
September 2005, pages 137--151.
Faith Ellen Fich, Victor Luchangco, Mark Moir, and Nir Shavit,
Obstruction-free Algorithms Can Be Practically Wait-free,
Proceedings of the 19th International Symposium on Distributed Computing (DISC),
September 2005, pages 78--92.
Faith Ellen Fich, Victor Luchangco, Mark Moir, and Nir Shavit,
Brief Announcement: Obstruction-Free Step Complexity:
Lock-free DCAS as an Example,
Proceedings of the 19th International Symposium on Distributed Computing (DISC),
September 2005, pages 493--494.
Faith Ellen Fich,
How Hard is it to Take a Snapshot?,
Proceedings of 31st Annual Conference on Current Trends in
Theory and Practice of Informatics (SOFSEM),
Lecture Notes in Computer Science, volume 3381, January 2005, pages 27--35.
James Aspnes, Faith Ellen Fich, and Eric Ruppert,
Relationships Between Broadcast and Shared Memory in Reliable Anonymous
Distributed Systems,
18th International Symposium on Distributed Computing (DISC),
Lecture Notes in Computer Science, volume 3274,
October 2004, pages 207--217.
Alex Brodsky and Faith Ellen Fich,
Efficient Synchronous Snapshots,
23rd Annual ACM Symposium on Principles of Distributed Computing (PODC),
July 2004, pages 70--79.
Hagit Attiya, Faith Ellen Fich, and Yaniv Kaplan,
Lower Bounds for Adaptive Collect and Related Objects,
23rd Annual ACM Symposium on Principles of Distributed Computing (PODC),
July 2004, pages 60--69.
Faith Ellen Fich, Danny Hendler, and Nir Shavit,
On the Inherent Weakness of Conditional Synchronization Primitives,
23rd Annual ACM Symposium on Principles of Distributed Computing (PODC),
July 2004, pages 80--87.
Panagiota Fatourou, Faith E. Fich, and Eric Ruppert,
A Tight Time Lower Bound for Space-Optimal Implementations
of Multi-Writer Snapshots,
35th Annual ACM Symposium on Theory of Computing (STOC),
June 2003, pages 259--268.
Panagiota Fatourou, Faith E. Fich, and Eric Ruppert,
Space-Optimal Multi-Writer Snapshot Objects Are Slow,
21st Annual ACM Symposium on Principles of
Distributed Computing (PODC),
July 2002, pages 13--20.
Faith E. Fich and Colette Johnen,
A Linear Space Self-Stabilizing Leader Election Algorithm
on a Unidirectional Ring,
15th International Symposium on Distributed Computing
(DISC),
Lecture Notes in Computer Science, volume 2180, October 2001, pages 224--239.
John Watkinson, Micah Adler, and Faith E. Fich,
New Protocols for Asymmetric Communication Channels,
8th International Colloquium on Structural
Information and Communication Complexity (SIROCCO),
June 2001, pages 337--350.
Faith E. Fich and Eric Ruppert,
Lower Bounds in Distributed Computing,
14th International Symposium on Distributed Computing (DISC),
Lecture Notes in Computer Science, volume 1914,
September 2000, pages 1--28.
Faith E. Fich and Andreas Jakoby,
Short Headers Suffice for Communication in a DAG with Link Failures,
14th International Symposium on Distributed Computing (DISC),
Lecture Notes in Computer Science, volume 1914,
September 2000, pages 360--373.
Micah Adler, Faith E. Fich, Leslie Goldberg, and Michael Paterson,
Tight Size Bounds for Packet Headers in Narrow Meshes,
Twenty Seventh International Colloquium on Automata,
Languages and Programming (ICALP),
Lecture Notes in Computer Science, volume 1853, July 2000,
pages 756--767.
Paul Beame and Faith E. Fich,
Optimal Bounds for the Predecessor Problem,
31st Annual ACM Symposium on Theory of Computing (STOC),
May 1999, pages 295--304.
Micah Adler and Faith E. Fich,
The Complexity of End-to-End Communication in Memoryless Networks,
18th Annual ACM Symposium on Principles of Distributed Computing (PODC),
May 1999, pages 239--248.
Faith E. Fich,
End-to-End Communication,
Second International Conference On Principles Of Distributed
Systems (OPODIS),
December 16, 1998, pages 37--43.
Faith Fich and Peter Bro Miltersen,
Tables Should be Sorted (on Random Access Machines),
Proceedings of the Fourth Workshop on Algorithms and Data Structures (WADS),
Lecture Notes in Computer Science, volume 955,
August 1995, pages 482--494.
Faith Fich, Maurice Herlihy, and Nir Shavit,
On the Space Complexity of Randomized Synchronization,
Proceedings of the 12th ACM Symposium on Principles of Distributed Computing
(PODC),
August 1993, pages 241--249.
Paul Beame, Faith Fich, and Rakesh Sinha,
Separating the Power of CREW and EREW
PRAMs with Small Communication Width,
Proceedings of the Third Workshop on Algorithms and Data Structures (WADS),
Lecture Notes in Computer Science, volume 709,
August 1993, pages 163--174.
Patrick Dymond, Faith Fich, Naomi Nishimura,
Prabhakar Ragde, and Walter Ruzzo,
Pointers versus Arithmetic in PRAMs,
8th Annual Conference on Structure in Complexity Theory,
May 1993, pages 239--252.
Faith Fich, Russell Impagliazzo, Bruce Kapron, Valerie King, and
Miroslaw Kutylowski,
Limits on the Power of Parallel Random Access Machines with Weak Forms
of Write Conflict Resolution,
Proceeding of the Tenth Annual
Symposium on Theoretical Aspects of Computing (STACS),
Lecture Notes in Computer Science, volume 665,
February 1993, pages 386--397.
Faith E. Fich, Miroslaw Kowaluk, Krzysztof Lorys,
Miroslaw Kutylowski, and Prabhakar Ragde,
Retrieval of scattered information by EREW, CREW and CRCW PRAMs,
Third Scandinavian Workshop on Algorithm Theory (SWAT),
Lecture Notes in Computer Science, volume 621,
July 1992, pages 30--41.
Faith Fich, Ian Munro, and Patricio Poblete,
Permuting,
Proceedings of the 31st Annual Symposium on Foundations of Computer
Science (FOCS),
October 1990, pages 372--381.
Faith Fich and Vijaya Ramachandran,
Lower Bounds for Parallel Computation on Linked Structures,
Proceedings of the 2nd ACM Symposium on Parallel Algorithms and
Architectures (SPAA),
July 1990, pages 109--116.
Faith Fich and Avi Wigderson, Towards Understanding Exclusive Read,
Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures
(SPAA),
June 1989, pages 76--82.
A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson,
A Tradeoff Between Search and Update Time for the
Implicit Dictionary Problem,
Proceedings of the Thirteenth International Colloquium on Automata, Languages,
and Programming (ICALP),
Lecture Notes in Computer Science, volume 226, July 1986, pages 50--59.
Faith E. Fich, Prabhakar Ragde, and Avi Wigderson,
Relations Between Concurrent-Write Models of Parallel Computation,
Proceedings of the Third ACM Symposium on Principles of Distributed
Computing (PODC),
July 1984, pages 179--189.
Faith E. Fich and Martin Tompa,
The Parallel Complexity of Exponentiating Polynomials over Finite Fields,
Proceedings of the Seventeenth Annual ACM Symposium on Theory of
Computing (STOC),
May 1985, pages 38--47.
A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson,
A Time-Space Tradeoff for Element Distinctness,
Proceedings of the Third Annual Symposium on Theoretical Aspects of
Computer Science (STACS),
January 1986, pages 353--358.
F. Fich, F. Meyer auf der Heide, P. Ragde, and A. Wigderson,
One, Two, Three . . . Infinity: Lower Bounds for Parallel Communication,
Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing
(STOC),
May 1985, pages 48--58.
Allan Borodin, Faith E. Fich, Danny Dolev, and Wolfgang Paul,
Bounds for Width Two Branching Programs,
Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC),
April 1983, pages 87--93.
Faith E. Fich,
New Bounds for Parallel Prefix Circuits,
Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC),
April 1983, pages 100--109.
Faith E. Fich,
Lower Bounds for the Cycle Detection Problem,
Proceedings of the Thirteenth Annual ACM
Symposium on Theory of Computing (STOC),
May 1981, pages 96--105.
Faith E. Fich and John A. Brzozowski,
A Characterization of a Dot-Depth Two Analogue of Generalized Definite
Languages,
Proceedings of the Sixth International Colloquium on Automata, Languages
and Programming (ICALP),
Lecture Notes in Computer Science, volume 71,
July 1979, pages 230--244.