List of important publications in concurrent, parallel, and distributed computing
Encyclopedia
Consensus, synchronisation, and mutual exclusion
Synchronising concurrent processes. Achieving consensusConsensus (computer science)
Consensus is a problem in distributed computing that encapsulates the task of group agreement in the presence of faults.In particular, any process in the group may fail at any time. Consensus is fundamental to core techniques in fault tolerance, such as state machine replication.- Problem...
in a distributed system in the presence of faulty nodes, or in a wait-free manner. Mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
in concurrent systems.
Dijkstra: “Solution of a problem in concurrent programming control”
- This paper presented the first solution to the mutual exclusion problem. Leslie LamportLeslie LamportLeslie Lamport is an American computer scientist. A graduate of the Bronx High School of Science, he received a B.S. in mathematics from the Massachusetts Institute of Technology in 1960, and M.A. and Ph.D. degrees in mathematics from Brandeis University, respectively in 1963 and 1972...
writes that this work “started the field of concurrent and distributed algorithms”.
Pease, Shostak, Lamport: “Reaching agreement in the presence of faults”
Lamport, Shostak, Pease: “The Byzantine generals problem”
- .
- .
- These two papers introduced and studied the problem that is nowadays known as Byzantine fault toleranceByzantine fault toleranceByzantine fault tolerance is a sub-field of fault tolerance research inspired by the Byzantine Generals' Problem, which is a generalized version of the Two Generals' Problem....
. The 1980 paper presented the classical lower bound that agreement is impossible if at least 1/3 of the nodes are faulty; it received the Edsger W. Dijkstra Prize in Distributed Computing in 2005. The highly-cited 1982 paper gave the problem its present name, and also presented algorithms for solving the problem.
Herlihy, Shavit: “The topological structure of asynchronous computation”
Saks, Zaharoglou: “Wait-free k-set agreement is impossible …”
- . Gödel prize lecture.
- .
- These two papers study wait-free algorithms for generalisations of the consensus problem, and showed that these problems can be analysed by using topologicalTopologyTopology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
properties and arguments. Both papers received the Gödel PrizeGödel PrizeThe Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
in 2004.
Foundations of distributed systems
Fundamental concepts such as time and knowledge in distributed systems.
Halpern, Moses: “Knowledge and common knowledge in a distributed environment”
- .
- This paper formalised the notion of “knowledge” in distributed systems, demonstrated the importance of the concept of “common knowledgeCommon knowledge (logic)Common knowledge is a special kind of knowledge for a group of agents. There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum.The concept was first introduced in...
” in distributed systems, and also proved that common knowledge cannot be achieved if communication is not guaranteed. The paper received the Gödel PrizeGödel PrizeThe Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
in 1997 and the Edsger W. Dijkstra Prize in Distributed Computing in 2009.
See also
- List of important publications in computer science
- List of important publications in theoretical computer science
- This paper formalised the notion of “knowledge” in distributed systems, demonstrated the importance of the concept of “common knowledge
- These two papers study wait-free algorithms for generalisations of the consensus problem, and showed that these problems can be analysed by using topological
- .
- These two papers introduced and studied the problem that is nowadays known as Byzantine fault tolerance
- .