Bibliographies for "Theory of Distributed Computing"

Theory of Distributed Computing

Computability theory in distributed computing

• @article{FLP:FLP@JACM'85, author = {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael S.}, title = {Impossibility of Distributed Consensus with One Faulty Process}, journal = {J. ACM}, issue_date = {April 1985}, volume = {32}, number = {2}, month = apr, year = {1985}, pages = {374--382}, numpages = {9}, publisher = {ACM}, }

Foundations of Distributed Shared Memory

• @article{WaitfreeSync:Herlihy@TOPLAS91,
  author = {Herlihy, Maurice},
  title = {Wait-free Synchronization},
  journal = {ACM Trans. Program. Lang. Syst.},
  issue_date = {Jan. 1991},
  volume = {13},
  number = {1},
  month = jan,
  year = {1991},
  pages = {124--149},
  numpages = {26},
  publisher = {ACM},
  }

• @article{ComputingwithFaulty:Afek@JACM95,
  author = {Afek, Yehuda and Greenberg, David S. and Merritt, Michael and Taubenfeld, Gadi},
  title = {Computing with Faulty Shared Objects},
  journal = {J. ACM},
  issue_date = {Nov. 1995},
  volume = {42},
  number = {6},
  month = nov,
  year = {1995},
  pages = {1231--1274},
  numpages = {44},
  publisher = {ACM},
  }

• @article{FaulttolerantWaitfree:Jayanti@JACM98,
  author = {Jayanti, Prasad and Chandra, Tushar Deepak and Toueg, Sam},
  title = {Fault-tolerant Wait-free Shared Objects},
  journal = {J. ACM},
  issue_date = {May 1998},
  volume = {45},
  number = {3},
  month = may,
  year = {1998},
  pages = {451--500},
  numpages = {50},
  publisher = {ACM},
  }

Progress Properties

• @inproceedings{OntheNature:Herlihy@OPODIS'11, author = {Herlihy, Maurice and Shavit, Nir}, title = {On the Nature of Progress}, booktitle = {Proceedings of the 15th International Conference on Principles of Distributed Systems}, series = {OPODIS'11}, year = {2011}, location = {Toulouse, France}, pages = {313--328}, numpages = {16}, publisher = {Springer-Verlag}, }

Simulations (registers constructions; shared memory constructions)

• @article{Construct1WriterAtomic:Haldar@JACM'95,
  author = {Haldar, S. and Vidyasankar, K.},
  title = {Constructing 1-writer Multireader Multivalued Atomic Variables from Regular Variables},
  journal = {J. ACM},
  issue_date = {Jan. 1995},
  volume = {42},
  number = {1},
  month = jan,
  year = {1995},
  pages = {186--203},
  numpages = {18},
  publisher = {ACM},
  }

• @article{BoundedTimestamping:Dolev@SIAM J. Comput.'97,
  author = {Dolev, Danny and Shavit, Nir},
  title = {Bounded Concurrent Time-Stamping},
  journal = {SIAM J. Comput.},
  issue_date = {April 1997},
  volume = {26},
  number = {2},
  month = apr,
  year = {1997},
  pages = {418--455},
  numpages = {38},
  publisher = {Society for Industrial and Applied Mathematics},
  }

Impossibility Results and Lower Bounds

• @inproceedings{HundredImpossibility:Lynch@PODC89,
  author = {Lynch, N.},
  title = {A Hundred Impossibility Proofs for Distributed Computing},
  booktitle = {Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing},
  series = {PODC '89},
  year = {1989},
  location = {Edmonton, Alberta, Canada},
  pages = {1--28},
  numpages = {28},
  publisher = {ACM},
  address = {New York, NY, USA},
  }

• @article{HundredImpossibility:Fich@DC03,
  author = {Faith E. Fich and Eric Ruppert},
  title = {Hundreds of impossibility results for distributed computing},
  journal = {Distributed Computing},
  volume = {16},
  number = {2-3},
  pages = {121--163},
  year = {2003},
  }

Quorum Systems

• @inproceedings{Gifford@SOSP79,
  author = {Gifford, David K.},
  title = {Weighted Voting for Replicated Data},
  booktitle = {Proceedings of the Seventh ACM Symposium on Operating Systems Principles},
  series = {SOSP '79},
  year = {1979},
  location = {Pacific Grove, California, USA},
  pages = {150--162},
  numpages = {13},
  publisher = {ACM},
  }

• @article{AssignVotes:Molina@JACM85,
  author = {Garcia-Molina, Hector and Barbara, Daniel},
  title = {How to Assign Votes in a Distributed System},
  journal = {J. ACM},
  issue_date = {Oct. 1985},
  volume = {32},
  number = {4},
  month = oct,
  year = {1985},
  pages = {841--860},
  numpages = {20},
  publisher = {ACM},
  }

• @article{LoadCapacity:Naor@SIAM J. Comput.'98,
  author = {Naor, Moni and Wool, Avishai},
  title = {The Load, Capacity, and Availability of Quorum Systems},
  journal = {SIAM J. Comput.},
  issue_date = {April 1998},
  volume = {27},
  number = {2},
  month = apr,
  year = {1998},
  pages = {423--447},
  numpages = {25},
  publisher = {Society for Industrial and Applied Mathematics},
  }

The Mutual Exclusion Problems

• @article{ANewSolution:Lamport@CACM'74, author = {Lamport, Leslie}, title = {A New Solution of Dijkstra's Concurrent Programming Problem}, journal = {Commun. ACM}, issue_date = {Aug. 1974}, volume = {17}, number = {8}, month = aug, year = {1974}, pages = {453--455}, numpages = {3}, publisher = {ACM}, }

• @article{TheMutualExclusion2:Lamport@JACM'86, author = {Lamport, Leslie}, title = {The Mutual Exclusion Problem: PartII&Mdash;Statement and Solutions}, journal = {J. ACM}, issue_date = {April 1986}, volume = {33}, number = {2}, month = apr, year = {1986}, pages = {327--348}, numpages = {22}, publisher = {ACM}, }

Survey

• @article{AppraisingTwoDecades:Fischer@DC03, author = {Fischer, Michael J. and Merritt, Michael}, title = {Appraising Two Decades of Distributed Computing Theory Research}, journal = {Distrib. Comput.}, issue_date = {September 2003}, volume = {16}, number = {2-3}, month = sep, year = {2003}, pages = {239--247}, numpages = {9}, publisher = {Springer-Verlag}, }