My research interests include
I have been an associate editor of the journal Distributed Computing since 2010.
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.
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.
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.
A brief announcement of this work appeared in Proc. 27th International Symposium on Distributed Computing (DISC 13), pages 567-568, 2013
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.
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.
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
To appear in Proc. 2017 ACM Symposium on Principles of Distributed Computing (PODC 17), 2017
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 1003H in the Lassonde Building (enter through Lassonde 1012 hallway)
Telephone: (416) 736-2100 ext. 33993
Mailing Address:
EECS Department
York University
4700 Keele Street
Toronto, Ontario
Canada M3J 1P3
What I did on my summer vacation, 2019