Eric Ruppert

My research interests include

• Models of Distributed Computing
• Distributed Algorithms
• Computability and Computational Complexity

Web page contents:

• Teaching
• Publications
• Contact Information

Teaching

Past courses:

• EECS/MATH 1019: Discrete Mathematics for Computer Science (Winter 2006, Fall 2007)
• EECS 1560: Introduction to Computing for Mathematics and Statistics (Winter 2017)
• EECS 2001: Introduction to Theory of Computation ( Winter 2004, Winter 2005, Fall 2005, Fall 2007, Fall 2009, Fall 2010, Winter 2011, Summer 2012, Fall 2014, Summer 2015, Winter 2016, Fall 2016, Fall 2023)
• EECS 3101: Design and Analysis of Algorithms ( Summer 2001, Fall 2001, Winter 2002, Winter 2003, Fall 2008, Winter 2012, Fall 2015, Winter 2018, Winter 2020, Winter 2023 )
• EECS 4080: Computer Science Project course (Winter 2012, Summer 2019)
• EECS 4101/5101: Advanced Data Structures ( Fall 2002, Winter 2004, Winter 2005, Winter 2009, Winter 2019, Summer 2020, Fall 2022, Summer 2023 )
• EECS 4115/5115: Computational Complexity ( Fall 2012, Fall 2020 )
• COSC 6115: Computational Complexity ( Winter 2001, Winter 2009, Fall 2010, Fall 2012 )
• COSC 6117: Theory of Distributed Systems (Winter 2002, reading version COSC6002 in Winter 2003, Fall 2003, Fall 2004, Winter 2006, Winter 2008, Fall 2008, Fall 2009, Fall 2011, Fall 2014, Winter 2016, Fall 2016, Winter 2023)
• CSC238: Discrete Mathematics for Computer Science (University of Toronto; Summer 1998)

The reason I'm glad I give exams to CS students rather than fine arts students. And a tip for software developers.

Publications

Conference and Journal Papers

• 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.

Other Publications

• 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.

Contact Information

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