My research interests include
Past courses:
The reason I'm glad I give exams to CS students rather than fine arts students. And a tip for software developers.
Dana Angluin,
James Aspnes,
David Eisenstat and
Eric Ruppert.
The computational power of population protocols.
Distributed Computing, 20(4), pages 279-304, 2007.
Shalom Asbell and
Eric Ruppert.
A wait-free deque with polylogarithmic step complexity.
In Proc. 27th International Conference on Principles of Distributed Computing (OPODIS 23), pages 17:1-17:22, 2023.
James Aspnes,
Faith Ellen Fich and
Eric Ruppert.
Relationships between broadcast and shared memory in reliable anonymous distributed systems.
Distributed Computing, 18(3), pages 209-219, 2006.
A preliminary version appeared at DISC 04.
Presentation slides.
James Aspnes and
Eric Ruppert.
Depth of a random binary search tree with concurrent insertions.
In Proc. 30th International Symposium on Distributed Computing (DISC 16), pages 371-384, 2016.
Hagit Attiya,
Rachid Guerraoui and
Eric Ruppert.
Partial snapshot objects.
In Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 08), pages 336-343, 2008.
Naama Ben-David,
Guy Blelloch,
Panagiota Fatourou,
Eric Ruppert and
Yihan Sun, and
Yuanhao Wei.
Space and time bounded multiversion garbage collection
In Proc. 35th International Symposium on Distributed Computing (DISC 21), pages 12:1-12:20, 2021.
A full version is available from arxiv.org.
Trevor Brown,
Faith Ellen and
Eric Ruppert.
Pragmatic primitives for non-blocking data structures.
In Proc. ACM Symposium on Principles of Distributed Computing (PODC 13), pages 13-22, 2013.
Trevor Brown,
Faith Ellen and
Eric Ruppert.
A general technique for non-blocking trees.
In Proc. 19th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP 14), pages 329-342, 2014.
Also published in ACM SIGPLAN Notices, volume 49, issue 8, 2014.
A brief announcement of this work appeared in Proc. 27th International Symposium on Distributed Computing (DISC 13), pages 567-568, 2013
Carole Delporte-Gallet,
Panagiota Fatourou,
Hugues Fauconnier and
Eric Ruppert.
When is recoverable consensus harder than consensus?
In Proc. ACM Symposium on Principles of Distributed Computing
(PODC 22), pages 198-208, 2022.
Presentation slides.
Carole Delporte-Gallet,
Hugues Fauconnier,
Rachid Guerraoui,
Anne-Marie Kermarrec,
Eric Ruppert and
Hung Tran-The.
Byzantine agreement with homonyms.
Distributed Computing, 26(5-6), pages 321-340, 2013.
A preliminary version appeared at PODC 11.
Carole Delporte-Gallet,
Hugues Fauconnier,
Rachid Guerraoui and
Eric Ruppert.
When birds die: Making population protocols fault-tolerant.
In Proc. IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS06), volume 4026 of LNCS, pages 51-66, 2006. Presentation slides.
Carole Delporte-Gallet,
Hugues Fauconnier,
Rachid Guerraoui and
Eric Ruppert.
Secretive birds: Privacy in population protocols.
In Proc. 11th International Conference on Principles of Distributed Systems (OPODIS 07), volume 4878 of LNCS, pages 329-342, 2007.
Carole Delporte-Gallet,
Hugues Fauconnier,
Petr Kuznetsov and
Eric Ruppert.
On the space complexity of set agreement.
In Proc. ACM Symposium on Principles of Distributed Computing (PODC 15), pages 271-280, 2015.
Presentation slides.
Faith Ellen,
Panagiota Fatourou,
Joanna Helga and
Eric Ruppert.
The amortized complexity of non-blocking binary search trees.
In Proc. ACM Symposium on Principles of Distributed Computing (PODC 14), pages 332-340, 2014.
Faith Ellen,
Panagiota Fatourou and
Eric Ruppert.
The space complexity of unbounded timestamps.
Distributed Computing, 21(2), pages 103-115, July 2008.
A preliminary version appeared at DISC 07.
Faith Ellen,
Panagiota Fatourou and
Eric Ruppert.
Time lower bounds for implementations of multi-writer snapshots.
Journal of the ACM, 54(6), article 30 (34 pages), December, 2007.
This article combines results that appeared, in preliminary form, at PODC 02 (presentation slides) and STOC 03.
Faith Ellen,
Panagiota Fatourou,
Eric Ruppert and
Franck van Breugel.
Non-blocking binary search trees.
In Proc. 29th ACM Symposium on Principles of Distributed Computing (PODC 10), pages 131-140, 2010.
Presentation slides.
Technical Report CSE-2010-04 gives more details.
Note: we are currently preparing a version of this paper for submission to a journal, with small improvements to the algorithm and many improvements to the proof of correctness that appeared in the technical report. Please contact me if you would like to see the revised version when it is ready.
Panagiota Fatourou,
Faith Ellen Fich and
Eric Ruppert.
Time-space tradeoffs for
implementations of snapshots.
In Proc. 38th ACM Symposium on Theory of Computing (STOC 06), pages 169-178, 2006.
Panagiota Fatourou,
Elias Papavasileiou and
Eric Ruppert.
Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries.
In Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 19), pages 275-286, 2019.
Proofs of correctness that were omitted for lack of space may be found in the technical report.
Panagiota Fatourou
and Eric Ruppert.
Lock-free Augmented Trees.
In Proc. 38th International Symposium on Distributed Computing (DISC 24), 2024. A more detailed version is also available.
Faith Fich and
Eric Ruppert.
Hundreds of impossibility results for distributed computing.
In Distributed Computing, 16(2-3), pages 121-163, 2003.
A much shorter, preliminary version appeared in the DISC 00 proceedings.
Mikhail Fomitchev and
Eric Ruppert.
Lock-free linked lists and skip lists.
In Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC 04), pages 50-59, 2004. Errata.
A more complete discussion is in Mikhail Fomitchev's M.Sc. thesis
Rachid Guerraoui and Eric Ruppert.
Anonymous and fault-tolerant shared-memory computing.
Distributed Computing, 20(3), pages 165-177, 2007.
A preliminary version appeared at DISC 05. Presentation slides.
Rachid Guerraoui and
Eric Ruppert.
Names trump malice: Tiny mobile agents can tolerate Byzantine failures.
In Proc. 36th International Colloquium on Automata, Languages and Programming (ICALP 09), volume 2, pages 484-495, 2009.
Rachid Guerraoui and Eric Ruppert.
Linearizability is not always a safety property.
In Proceedings of the International Conference on Networked Systems (NETYS 14), pages 57-69, 2014.
Rachid Guerraoui and Eric Ruppert.
A paradox of eventual linearizability in shared memory.
In Proc. ACM Symposium on Principles of Distributed Computing (PODC 14), pages 40-49, 2014.
Maurice Herlihy and Eric Ruppert.
On the existence of booster types.
In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS 00), pages 653-663, 2000.
Hossein Naderibeni and Eric Ruppert.
A wait-free queue with polylogarithmic step complexity.
Distributed Computing, 37(4), pages 309-334, December, 2024.
Invited as a selected paper from PODC 2023.
A preliminary version appeared in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 23), pages 124-134, 2023. Erratum for conference version. Presentation slides.
Younghun Roh,
Yuanhao Wei,
Eric Ruppert,
Panagiota Fatourou,
Siddhartha Jayanti,
Julian Shun.
Aggregating funnels for faster fetch&add and queues.
To appear in Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2025.
A preliminary version is available on arxiv.org.
Eric Ruppert.
Consensus numbers of multi-objects.
In Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC 98), pages 211-217, 1998.
Eric Ruppert.
Consensus numbers of transactional
objects.
In Proceedings of the 13th International Symposium on Distributed
Computing (DISC 99), volume 1693 of
LNCS,
pages 312-326, 1999.
Eric Ruppert.
Finding the k shortest paths in parallel.
Algorithmica, 28(2), pages 242-254, October, 2000. PDF file.
A preliminary version appeared at STACS 97.
Eric Ruppert.
Determining consensus numbers.
SIAM Journal on Computing, 30(4), pages 1156-1168, 2000. PDF file.
A preliminary version appeared at PODC 97.
Eric Ruppert.
The anonymous consensus hierarchy and naming problems.
In Proc. 11th International Conference on Principles of Distributed Systems (OPODIS 07), volume 4878 of LNCS, pages 386-400, 2007.
Some details omitted due to space constraints appear in a technical report.
Eric Ruppert.
Brief Announcement: Readers of wait-free unbounded registers must write
In Proc. 2017 ACM Symposium on Principles of Distributed Computing (PODC 17), pages 93-94, 2017
Yuanhao Wei,
Naama Ben-David,
Guy Blelloch,
Panagiota Fatourou,
Eric Ruppert and
Yihan Sun.
Constant-time snapshots with applications to concurrent data structures.
In Proc. ACM Symposium on Principles and Practice of Parallel Programming (PPoPP 21), pages 31--46, 2021.
A preliminary version is available on arxiv.org.
Yuanhao Wei,
Guy Blelloch,
Panagiota Fatourou and
Eric Ruppert.
Practically and theoretically efficient garbage collection for multiversioning.
In Proc. ACM Symposium on Principles and Practice of Parallel Programming (PPoPP 23), pages 66-78, 2023.
A preliminary version is available on arxiv.org.
James Aspnes
and Eric Ruppert.
An Introduction to Population Protocols.
In Middleware for Network Eccentric and Mobile Applications, pages 97-120, Springer, 2009.
A briefer version of this survey appeared
in the
Bulletin of the EATCS, 93, pages 98-117, October 2007.
Rachid Guerraoui and Eric Ruppert.
Even Small Birds are Unique: Population Protocols with Identifiers.
Technical Report CSE-2007-04, Dept of Computer Science and Engineering, York University, September 2007.
Eric Ruppert.
Parallel Algorithms for the k Shortest Paths and Related Problems.
M.Sc. thesis, University of Toronto, January 1996. Abstract.
Eric Ruppert.
The Consensus Power of Shared-Memory Distributed Systems.
Ph.D. thesis, University of Toronto, December 1999. Abstract.
Office: Room 3052 in the Lassonde Building
Telephone: (416) 736-2100 ext. 33948
Mailing Address:
EECS Department
York University
4700 Keele Street
Toronto, Ontario
Canada M3J 1P3
What I did on my summer vacation, 2019