skip to main content
10.1145/1146381.1146383acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Century papers at the first quarter-century milestone

Published: 23 July 2006 Publication History

Abstract

My talk intends to look back at the first 25 years of PODC to surface issues regarding its potential impact in light of the extensive spread out of Distributed Computing. Distributed computing expands to a level that no one anticipated even few years ago. In the near future distributed computing will be part of every aspect of our life -- from monitoring personal health to environment tracking, from communication to commuting and will be applied from within a chip through a multi-cpu machine to a virtual globally spanned machine. Society will be completely depended on the ability to continuously provide services at one level or another. The various systems will interact and will never be in a steady state. Are we ready to address such issues? Is the tool-box PODC have developed over the last quarter century will help the community to address the challenges of such systems.When PODC was founded there were skeptics that did not view Distributed Computing as a viable field of Computer Science. Few pioneers envisioned the role it will play and decided that it is an identified discipline with specific focus of interest that will benefit from having a separate conference.An impact is a multi facet notion and there is no single scale to measure it. In the talk I will discuss the impact of PODC from several angles. PODC went through several cycles over the years, from the first very few embryonic years, through a period of stability, some hard years and the emerging focus over the last few years.To get an independent perspective I chose to also look at PODC through the eyes of Google Scholar. I listed regular papers that have at least 100 references to the PODC version and to the subsequent paper in a journal (when I noticed one). The compiled list was different than any list I would have compiled myself1. In the talk I will discuss the list presented in the bibliography and will explore various objective measures that are reflected by it. I will compare it to various other topics and will try to raise issues that the PODC community needs to discuss toward its future role in the continuously expanding Distributed Computing discipline.I will also comment on various emerging fields in which Distributed Computing will play a major role and will point out challenges that the main-stream research in PODC is not capable of addressing.

References

[1]
Arthur J. Bernstein, Nathan Goodman, "Concurrency Control Algorithms for Multiversion Database Systems", In Proceedings of the first PODC, 209--215, 1982.
[2]
Michael Ben-Or, "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols", In Proceedings of the second PODC, 27--30, 1983.
[3]
Ralph-Johan Back, Reino Kurki-Suonio, "Decentralization of Process Nets with Centralized Control", In Proceedings of the second PODC, 131--142, 1983.
[4]
Paris C. Kanellakis, Scott A. Smolka, "CCS Expressions, Finite State Processes,and THree Problems of Equivalence", In Proceedings of the second PODC, 228--240, 1983.
[5]
Joseph Y. Halpern, Yoram Moses, "Knowledge and Common Knowledge in a Distributed Environment", In Proceedings of the third PODC, 50--61, 1984.
[6]
Jennifer Lundelius, Nancy A. Lynch, "ANew Fault-Tolerant Algorithm for Clock Synchronization", In Proceedings of the third PODC, 75--88, 1984.
[7]
Joseph Y. Halpern, Barbara Simons, H. Raymond Strong, Danny Dolev, "Tolerant Clock Synchronization", In Proceedings of the third PODC, 89--102, 1984.
[8]
Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer, "Consensus in the Presence of Partial Synchrony (Preliminary Version)", In Proceedings of the third PODC, 103--118, 1984.
[9]
T. K. Srikanth, Sam Toueg, "Optimal Clock Synchronization", In Proceedings of the fourth PODC, 71--86, 1985.
[10]
K. Mani Chandy, Jayadev Misra, "How Processes Learn", In Proceedings of the fourth PODC, 204--214, 1985.
[11]
Butler W. Lampson, "Designing a Global Name Service", In Proceedings of the fifth PODC, 1--10, 1986.
[12]
Kai Li, Paul Hudak, "Memory Coherence in Shared Virtual Memory Systems", In Proceedings of the fifth PODC, 229--239, 1986.Kai Li, Paul Hudak, "Memory Coherence in Shared Virtual Memory Systems", In Proceedings of the fifth PODC, 229--239, 1986.
[13]
Alan J. Demers, Daniel H. Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard E. Sturgis, Daniel C. Swinehart, Douglas B. Terry, "Epidemic Algorithms for Replicated Database Maintenance", In Proceedings of the sixth PODC, 1--12, 1987.
[14]
Nancy A. Lynch, Mark R. Tuttle, "Hierarchical Correctness Proofs for Distributed Algorithms", In Proceedings of the sixth PODC, 137--151, 1987.
[15]
Maurice Herlihy, "Impossibility and Universality Results for Wait-Free Synchronization", In Proceedings of the seventh PODC, 276--290, 1988.
[16]
A. Prasad Sistla, Jennifer L. Welch, "E .cient Distributed Recovery Using Message Logging", In Proceedings of the eighth PODC, 223--238, 1989.
[17]
Robert P. Kurshan, Kenneth L. McMillan, "A Structural Induction Theorem for Processes", In Proceedings of the eighth PODC, 239--247, 1989.
[18]
Yehuda Afek, Danny Dolev, Hagit Attiya, Eli Gafni, Michael Merritt, Nir Shavit, "Snapshots of Shared Memory", In Proceedings of the ninth PODC, 1--13, 1990.
[19]
Rivka Ladin, Barbara Liskov, Liuba Shrira Lazy Replication, "Exploiting the Semantics of Distributed Services", In Proceedings of the ninth PODC, 43--57, 1990.
[20]
Shmuel Katz, Kenneth J. Perry, "Self-Stabilizing Extensions for Message-Passing Systems", In Proceedings of the ninth PODC, 91--101, 1990.
[21]
Shlomi Dolev, Amos Israeli, Shlomo Moran, "Self-Stabilization of Dynamic Systems Assuming only Read/Write Atomicity", In Proceedings of the ninth PODC, 103--117, 1990.
[22]
Hagit Attiya, Amotz Bar-Noy, Danny Dolev, "Memory Robustly in Message-Passing Systems", In Proceedings of the ninth PODC, 363--375, 1990.
[23]
Rafail Ostrovsky, Moti Yung, "How to Withstand Mobile Virus Attacks", In Proceedings of the tenth PODC, 51--59, 1991.
[24]
Rajeev Alur, Tomas Feder, Thomas A. Henzinger, "The Benefits of Relaxing Punctuality", In Proceedings of the tenth PODC, 139--152, 1991.
[25]
Martin Abadi, Mark R. Tuttle, "A Semantics for a Logic of Authentication", In Proceedings of the tenth PODC, 201--216, 1991.
[26]
Tushar Deepak Chandra, Sam Toueg, "Unreliable Failure Detectors for Asynchronous Systems", In Proceedings of the tenth PODC, 325--340, 1991.
[27]
Aleta Ricciardi, Kenneth P. Birman, "Using Process Groups to Implement Failure Detection in Asynchronous Environments", In Proceedings of the tenth PODC, 341--353, 1991.
[28]
Marc Shapiro, Peter Dickman, David Plainfosse, "Robust, Distributed References and Acyclic Garbage Collection", In Proceedings of the eleventh PODC, 135--146, 1992.
[29]
Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg, "The Weakest Failure Detector for Solving Consensus", In Proceedings of the eleventh PODC, 147--158, 1992.
[30]
Robbert van Renesse, Kenneth P. Birman, Roy Friedman, Mark Hayden, David A. Karr, "Framework for Protocol Composition in Horus", In Proceedings of the fourteenth PODC, 80--89, 1995.
[31]
Nir Shavit, Dan Touitou, "Software Transactional Memory", In Proceedings of the fourteenth PODC, 204--213, 1995.
[32]
Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg, "On the Impossibility of Group Membership", In Proceedings of the fifteenth PODC, 322--330, 1996.
[33]
Alan Fekete, Nancy A. Lynch, Alexander A. Shvartsman, "Specifying and Using a Partitionable Group Communication Service", In Proceedings of the sixteenth PODC, 53--62, 1997.
[34]
Michael Mitzenmacher, "How Useful Is Old Information?", In Proceedings of the sixteenth PODC, 83--91, 1997.
[35]
Marcos Kawazoe Aguilera, Robert E. Strom, Daniel C. Sturman, Mark Astley, Tushar Deepak Chandra, "Matching Events in a Content-Based Subscription System", In Proceedings of the eighteenth PODC, 53--61, 1999.
[36]
Antonio Carzaniga, David S. Rosenblum, Alexander L. Wolf, "Achieving scalability and expressiveness in an Internet-scale event noti .cation service", In Proceedings of the nineteenth PODC, 219--227, 2000.
[37]
Michael Mitzenmacher, "Compressed bloom .lters", In Proceedings of the twentieth PODC, 144--150, 2001.
[38]
Erran L. Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, Roger Wattenhofer, "Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks", In Proceedings of the twentieth PODC, 264--273, 2001.
[39]
Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, Scott Shenker, "A BGP-based mechanism for lowest-cost routing", In Proceedings of the twenty first PODC, 173--182, 2002.
[40]
Dahlia Malkhi, Moni Naor, David Ratajczak, "Viceroy:a scalable and dynamic emulation of the butterfly", In Proceedings of the twenty first PODC, 183--192, 2002.
[41]
Sitaram Iyer, Antony I. T. Rowstron, Peter Druschel, "Squirrel:a decentralized peer-to-peer web cache", In Proceedings of the twenty first PODC, 213--222, 2002.
[42]
David Liben-Nowell, Hari Balakrishnan, David R. Karger, "Analysis of the evolution of peer-to-peer systems", In Proceedings of the twenty first PODC, 233--242, 2002.

Cited By

View all
  • (2014)How to withstand mobile virus attacks, revisitedProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611474(293-302)Online publication date: 15-Jul-2014

Index Terms

  1. Century papers at the first quarter-century milestone

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
    July 2006
    230 pages
    ISBN:1595933840
    DOI:10.1145/1146381
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 July 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. distributed algorithms
    2. distributed systems

    Qualifiers

    • Article

    Conference

    PODC06

    Acceptance Rates

    Overall Acceptance Rate 740 of 2,477 submissions, 30%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2014)How to withstand mobile virus attacks, revisitedProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611474(293-302)Online publication date: 15-Jul-2014

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media