Eric Ruppert

My research interests include

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

I am serving on the programme committee for SPAA 2020 and PPoPP 2021.

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 )
• 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 )
• 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 )
• EECS 4115: Computational Complexity (Fall 2012)
• 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 )
• 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.

• 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

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