Faith Ellen

Rati Gelashvili

Leqi Zhu

SIAM J. Comput., 2024

2023

Why Extension-Based Proofs Fail.

[BibT_eX]

[DOI]

SIAM J. Comput., August, 2023

Wait-free approximate agreement on graphs.

[BibT_eX]

[DOI]

Dan Alistarh

Joel Rybicki

Theor. Comput. Sci., February, 2023

2022

The Step Complexity of Multidimensional Approximate Agreement.

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on Principles of Distributed Systems, 2022

2021

Constant-Length Labeling Schemes for Deterministic Radio Broadcast.

[BibT_eX]

[DOI]

ACM Trans. Parallel Comput., 2021

Space Lower Bounds for the Signal Detection Problem.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2021

Extension-Based Proofs for Synchronous Message Passing.

[BibT_eX]

[DOI]

Yilun Sheng

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Reductions and Extension-Based Proofs.

[BibT_eX]

[DOI]

Kayman Brusse

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

Preface.

[BibT_eX]

[DOI]

Luís Rodrigues

Theor. Comput. Sci., 2020

Randomized distributed online algorithms against adaptive offline adversaries.

[BibT_eX]

[DOI]

Kim S. Larsen

Inf. Process. Lett., 2020

A complexity-based classification for multiprocessor synchronization.

[BibT_eX]

[DOI]

Distributed Comput., 2020

Preface.

[BibT_eX]

[DOI]

Jörg-Rüdiger Sack

Comput. Geom., 2020

Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast.

[BibT_eX]

[DOI]

Seth Gilbert

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Brief Announcement: Why Extension-Based Proofs Fail.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2019

Tight Bounds for Restricted Grid Scheduling.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2019

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

[BibT_eX]

[DOI]

Bull. EATCS, 2019

2019 Edsger W. Dijkstra Prize in Distributed Computing.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018

Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.

[BibT_eX]

[DOI]

J. ACM, 2018

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

[BibT_eX]

[DOI]

Kim S. Larsen

CoRR, 2018

2017

Limitations of Highly-Available Eventually-Consistent Data Stores.

[BibT_eX]

[DOI]

Adam Morrison

IEEE Trans. Parallel Distributed Syst., 2017

Simulating a Shared Register in a System that Never Stops Changing.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Upper and Lower Bounds on the Power of Advice.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Jeff Edmonds

Toniann Pitassi

SIAM J. Comput., 2016

Universal constructions that ensure disjoint-access parallelism and wait-freedom.

[BibT_eX]

[DOI]

Distributed Comput., 2016

A Complexity-Based Hierarchy for Multiprocessor Synchronization.

[BibT_eX]

[DOI]

CoRR, 2016

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract].

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Concurrent Data Structures.

[BibT_eX]

[DOI]

Trevor Brown

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Deterministic Objects: Life Beyond Consensus.

[BibT_eX]

[DOI]

Yehuda Afek

Eli Gafni

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract).

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on Principles of Distributed Systems, 2016

2015

Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.

[BibT_eX]

[DOI]

J. ACM, 2015

Simulating a Shared Register in an Asynchronous System that Never Stops Changing - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Atomic Snapshots from Small Registers.

[BibT_eX]

[DOI]

Leqi Zhu

Proceedings of the 19th International Conference on Principles of Distributed Systems, 2015

2014

Impossibility Results for Distributed Computing

[BibT_eX]

[DOI]

Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, ISBN: 978-3-031-02010-0, 2014

Tight Bounds for Adopt-Commit Objects.

[BibT_eX]

[DOI]

James Aspnes

Theory Comput. Syst., 2014

Tight Bounds for an Online Bin Packing Problem.

[BibT_eX]

[DOI]

CoRR, 2014

A general technique for non-blocking trees.

[BibT_eX]

[DOI]

Trevor Brown

Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2014

The amortized complexity of non-blocking binary search trees.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013

Tight Bounds for Set Disjointness in the Message Passing Model

[BibT_eX]

[DOI]

CoRR, 2013

An Optimal Implementation of Fetch-and-Increment.

[BibT_eX]

[DOI]

Philipp Woelfel

Proceedings of the Distributed Computing - 27th International Symposium, 2013

Pragmatic primitives for non-blocking data structures.

[BibT_eX]

[DOI]

Trevor Brown

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

A Tight Bound for Set Disjointness in the Message-Passing Model.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Bounds for Scheduling Jobs on Grid Processors.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

On the Inherent Sequentiality of Concurrent Objects.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Efficient Fetch-and-Increment.

[BibT_eX]

[DOI]

Vijaya Ramachandran

Philipp Woelfel

Proceedings of the Distributed Computing - 26th International Symposium, 2012

A little advice can be very helpful.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Jeff Edmonds

Toniann Pitassi

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Faster than optimal snapshots (for a while): preliminary version.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

2011

The complexity of updating snapshot objects.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2011

Fully-adaptive algorithms for long-lived renaming.

[BibT_eX]

[DOI]

Alex Brodsky

Philipp Woelfel

Distributed Comput., 2011

Tight bounds for anonymous adopt-commit objects.

[BibT_eX]

[DOI]

James Aspnes

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.

[BibT_eX]

[DOI]

Phong Chuong

Vijaya Ramachandran

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

Non-blocking binary search trees.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

2008

The space complexity of unbounded timestamps.

[BibT_eX]

[DOI]

Distributed Comput., 2008

2007

Time lower bounds for implementations of multi-writer snapshots.

[BibT_eX]

[DOI]

J. ACM, 2007

SNZI: scalable NonZero indicators.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

2006

On the inherent weakness of conditional primitives.

[BibT_eX]

[DOI]

Distributed Comput., 2006

Relationships between broadcast and shared memory in reliable anonymous distributed systems.

[BibT_eX]

[DOI]

James Aspnes

Distributed Comput., 2006

Time-space tradeoffs for implementations of snapshots.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Maintaining Information About Nearby Processors in a Mobile Environment.

[BibT_eX]

[DOI]

Sivaramakrishnan Subramanian

Jennifer L. Welch

Proceedings of the Distributed Computing and Networking, 8th International Conference, 2006

The Complexity of Updating Multi-writer Snapshot Objects.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing and Networking, 8th International Conference, 2006

2005

Graph Minors and Reliable Single Message Transmission.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

Estimating the maximum.

[BibT_eX]

[DOI]

J. Algorithms, 2005

Introduction to the special issue DISC 2003.

[BibT_eX]

[DOI]

Distributed Comput., 2005

Obstruction-Free Step Complexity: Lock-Free DCAS as an Example.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 19th International Conference, 2005

Obstruction-Free Algorithms Can Be Practically Wait-Free.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 19th International Conference, 2005

Restricted Stack Implementations.

[BibT_eX]

[DOI]

Matei David

Alex Brodsky

Proceedings of the Distributed Computing, 19th International Conference, 2005

How Hard Is It to Take a Snapshot?.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

Linear Lower Bounds on Real-World Implementations of Concurrent Objects.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

On the inherent weakness of conditional synchronization primitives.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Efficient synchronous snapshots.

[BibT_eX]

[DOI]

Alex Brodsky

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Lower bounds for adaptive collect and related objects.

[BibT_eX]

[DOI]

Yaniv Kaplan

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

2003

Hundreds of impossibility results for distributed computing.

[BibT_eX]

[DOI]

Distributed Comput., 2003

A tight time lower bound for space-optimal implementations of multi-writer snapshots.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Optimal Bounds for the Predecessor Problem and Related Problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Space-optimal multi-writer snapshot objects are slow.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Colette Johnen

Proceedings of the Distributed Computing, 15th International Conference, 2001

New Protocols for Asymmetric Communication Channels.

[BibT_eX]

John Watkinson

Micah Adler

Proceedings of the SIROCCO 8, 2001

2000

Lower Bounds in Distributed Computing.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 14th International Conference, 2000

Short Headers Suffice for Communication in a DAG with Link Failures.

[BibT_eX]

[DOI]

Andreas Jakoby

Proceedings of the Distributed Computing, 14th International Conference, 2000

Tight Size Bounds for Packet Headers in Narrow Meshes.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Optimal Bounds for the Predecessor Problem.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

The Complexity of End-to-End Communication in Memoryless Networks.

[BibT_eX]

[DOI]

Micah Adler

Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, 1999

1998

On the Space Complexity of Randomized Synchronization.

[BibT_eX]

[DOI]

Maurice Herlihy

J. ACM, 1998

On Searching Sorted Lists: A Near-Optimal Lower Bound

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

End to End Communication.

[BibT_eX]

Proceedings of the Distributed Computing, 1998

1997

Infrastructure issues related to theory of computing research.

[BibT_eX]

[DOI]

SIGACT News, 1997

Strategic directions in research in theory of computing.

[BibT_eX]

[DOI]

SIGACT News, 1997

Separating the Power of EREW and CREW PRAMs with Small Communication Width.

[BibT_eX]

[DOI]

Rakesh K. Sinha

Inf. Comput., 1997

1996

Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

Pointers versus Arithmetic in PRAMs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

1995

Permuting in Place.

[BibT_eX]

[DOI]

J. Ian Munro

Patricio V. Poblete

SIAM J. Comput., 1995

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

[BibT_eX]

[DOI]

Comput. Complex., 1995

Tables Should Be Sorted (On Random Access Machines).

[BibT_eX]

[DOI]

Peter Bro Miltersen

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

1994

Bounds on Certain Multiplications of Affine Combinations.

[BibT_eX]

[DOI]

Kim S. Larsen

Discret. Appl. Math., 1994

1990

Toward Understanding Exclusive Read.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

Preface.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1990

Lower Bounds for Parallel Computation on Linked Structures.

[BibT_eX]

[DOI]

Vijaya Ramachandran

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

Permuting

[BibT_eX]

[DOI]

J. Ian Munro

Patricio V. Poblete

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

1989

On the Power of Concurrent-Write PRAMs With Read-Only Memory

[BibT_eX]

[DOI]

Inf. Comput., November, 1989

Towards Understanding Exclusive Read.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

1988

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.

[BibT_eX]

[DOI]

Allan Borodin

Friedhelm Meyer auf der Heide

Eli Upfal

Theor. Comput. Sci., 1988

Relations Between Concurrent-Write Models of Parallel Computation.

[BibT_eX]

[DOI]

Prabhakar Ragde

SIAM J. Comput., 1988

The parallel complexity of exponentiating polynomials over finite fields.

[BibT_eX]

[DOI]

Martin Tompa

J. ACM, 1988

Simulations Among Concurrent-Write PRAMs.

[BibT_eX]

[DOI]

Prabhakar Ragde

Algorithmica, 1988

1987

A Time-Space Tradeoff for Element Distinctness.

[BibT_eX]

[DOI]

Allan Borodin

Friedhelm Meyer auf der Heide

Eli Upfal

SIAM J. Comput., 1987

1986

Bounds for Width Two Branching Programs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

1985

One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Prabhakar Ragde

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

1984

On generalized locally testable languages.

[BibT_eX]

[DOI]

Janusz A. Brzozowski

Discret. Math., 1984

1983

Lower Bounds for the Cycle Detection Problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1983

New Bounds for Parallel Prefix Circuits

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

A homomorphic characterization of regular languages.

[BibT_eX]

[DOI]

Karel Culík II

Arto Salomaa

Discret. Appl. Math., 1982

1980

Languages of R-Trivial Monoids.

[BibT_eX]

[DOI]

Janusz A. Brzozowski

J. Comput. Syst. Sci., 1980

1979

A Generalized Setting for Fixpoint Theory.

[BibT_eX]

[DOI]

Edward A. Ashcroft

Theor. Comput. Sci., 1979

A Characterization of a Dot-Depth Two Analogue of Generalized Definite Languages.

[BibT_eX]

[DOI]