Eric Ruppert

My research interests include

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

Web page contents:

• Teaching
• Publications
• Other Pages
• Contact Information

Teaching

I am a coach for York's Programming Contest teams.

Past courses:

• CSE/MATH 1019: Discrete Mathematics for Computer Science (Winter 2006, Fall 2007)
• CSE 2001: Introduction to Theory of Computation (Winter 2004, Winter 2005, Fall 2005, Fall 2007, Fall 2009, Fall 2010, Winter 2011, Summer 2012)
• CSE 3101: Design and Analysis of Algorithms (Summer 2001, Fall 2001, Winter 2002, Winter 2003, Fall 2008, Winter 2012)
• CSE 4080: Computer Science Project course (Winter 2012)
• CSE 4101: Advanced Data Structures (Fall 2002, Winter 2004, Winter 2005, Winter 2009)
• CSE 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)
• 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.

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.

• 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.
  To appear in Proc. 32nd ACM Symposium on Principles of Distributed Computing (PODC 13), 2013.

• Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The.
  Byzantine Agreement with Homonyms.
  To appear in Distributed Computing, 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.

• 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.
  Technical Report CSE-2010-04 gives more details. Presentation slides.

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

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

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

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.

Other Pages

Some other assorted links

Some random quotations

Information for new grad students

Contact Information

Office: Room 3042 in the Lassonde Building (formerly known as the Computer Science and Engineering Building)
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872

Mailing Address:
Department of Computer Science and Engineering
York University
4700 Keele Street
Toronto, Ontario
Canada M3J 1P3