These papers are not necessarily related to my research. But they were ground breaking / revolutionary / just great papers in general. Alternatively named "Papers Older Than I Am."
Statecharts: A Visual Formalism for Complex Systems
@article{harel1987statecharts,
title={Statecharts: A visual formalism for complex systems},
author={Harel, David},
journal={Science of computer programming},
volume={8},
number={3},
pages={231--274},
year={1987},
publisher={Elsevier}
}
Experience with Processes and Monitors in Mesa
- Lampson, Butler W and Redell, David D
- Likely a good source for priority inversion information (although SysPapers#Sha1990Priority is cited). Talks about problems and pitfalls with monitors (mutual exclusion mechanism) for Pilot / Mesa (I think OS and Lang). Interesting: processes are first class objects in the Mesa language. TODO: finish.
- Attach:Lampson1980Monitors.pdf
@article{lampson1980experience,
title={Experience with processes and monitors in Mesa},
author={Lampson, Butler W and Redell, David D},
journal={Communications of the ACM},
volume={23},
number={2},
pages={105--117},
year={1980},
publisher={ACM}
}
The Byzantine Generals Problem
- Lamport, Leslie and Shostak, Robert and Pease, Marshall
- This paper applies rigor to thinking about fault tolerant system and demonstrates an unintuitive result: to handle m traitors, a system with open messages must have 3m + 1 total actors. If messages may be signed, any number of traitors may be handled. Note that the problem specifies that all loyal actors must act consistently, but do not have to have come to the same conclusion.
The generals are working to reach a consensus. A traitor may cast the tie-breaking vote that makes that consensus "attack" instead of "retreat," so long as every loyal general ends up taking the same action. To apply this formalism to an actual system, refer to section 6 which also explains the reasoning behind the assumptions.
Remember, this isn't voting: it is a way to have the generals all act consistently.
- Attach:Lamport82Byzantine.pdf
@article{lamport1982byzantine,
title={The Byzantine generals problem},
author={Lamport, Leslie and Shostak, Robert and Pease, Marshall},
journal={ACM Transactions on Programming Languages and Systems (TOPLAS)},
volume={4},
number={3},
pages={382--401},
year={1982},
publisher={ACM}
}
Communicating Sequential Processes
- Hoare, Charles Antony Richard
- Describes a possible programming language in which data flow in and out of a system is a primitive operation, just as assignment is considered. This allows the programmer to construct programs in terms of concurrent processes. Pulls from Dijkstra's guarded commands, and is non-deterministic; the idea of fairness is mentioned for the switch construct, but left to the implementation Gives an incomplete specification (and no implementation), but has many example problems and solutions.
I stumbled upon this paper while watching Rob Pike's "Concurrency is not Parrallelism" presentation. The paper is certainly a foundation for further studies in Programming Languages. Being unfamiliar with the notation (Hoare uses a custom notation similar to Backus-Naur Form, which I am hardly acquainted), and the general area, I found the language hard to conceptualize. This is also likely due to the ideas presented being fairly alien, even 30 plus years after it was written. Although these constructs are part of many languages (such as Google's Go), they are usually not included at a primitive level.
- Attach:Hoare78Sequential.pdf
@article{hoare1978communicating,
title={Communicating sequential processes},
author={Hoare, Charles Antony Richard},
journal={Communications of the ACM},
volume={21},
number={8},
pages={666--677},
year={1978},
publisher={ACM}
}
The Use of Triple-Modular Redundancy to Improve Computer Reliability
@article{lyons1962use,
title={The use of triple-modular redundancy to improve computer reliability},
author={Lyons, Robert E and Vanderkulk, Wouter},
journal={IBM Journal of Research and Development},
volume={6},
number={2},
pages={200--209},
year={1962},
publisher={IBM}
}
Reliability Analysis of N-modular Redundancy Systems with Intermittent and Permanent Faults
@article{koren1979reliability,
title={Reliability analysis of N-modular redundancy systems with intermittent and permanent faults},
author={Koren, Israel and Su, Stephen Y. H.},
journal={Computers, IEEE Transactions on},
volume={100},
number={7},
pages={514--520},
year={1979},
publisher={IEEE}
}
The N-Version Approach to Fault-Tolerant Software
@article{avizienis1985n,
title={The N-version approach to fault-tolerant software},
author={Avizienis, Algirdas and others},
journal={IEEE Trans. Software Eng.},
volume={11},
number={12},
pages={1491--1501},
year={1985}
}
Interposition Agents: Transparently Interposing User Code at the System Interface
- Jones, Michael B
- The paper presents a toolkit for building agents which can interpose on the system interface, which for 4.3 BSD entails system calls and signals. Evaluates the performance given several types of agents, from a simple time system call rewrite to a more complex tracking of every single system call. The impact of this paper comes from the case laid out for interposition as a powerful systems technique, as well as the observation that it is the system abstractions (files, groups, pipes and so on) that are of greatest concern when implementing interposition. While there is a large number of system calls, they actually just interact with a small number of core system abstractions.
The paper stresses the use of object oriented techniques for implementing the toolkit, which seems unnecessary. The performance seems abysmal in some cases (and not just because it was a system from '93-94). Using "formatting my dissertation" as one of the test cases is hilarious. Check the Related Work section to gain an understanding of how novel this idea was at the time of writing.
- Attach:Jones94Interposition.pdf
@inproceedings{jones1994interposition,
title={Interposition agents: Transparently interposing user code at the system interface},
author={Jones, Michael B},
booktitle={ACM SIGOPS Operating Systems Review},
volume={27},
number={5},
pages={80--93},
year={1994},
organization={ACM}
}
Fail-stop processors: an approach to designing fault-tolerant computing systems
- Schlichting, Richard D and Schneider, Fred B
- Same Schneider as Distributed Systems 2nd Edition chapter 8. References the Byzantine Generals Problem for voting (2f+1). Discusses using multiple processors to turn hardware faults into fail-stop faults. TODO: finish summary.
- Attach:schlichting1983fail.pdf
@article{schlichting1983fail,
title={Fail-stop processors: an approach to designing fault-tolerant computing systems},
author={Schlichting, Richard D and Schneider, Fred B},
journal={ACM Transactions on Computer Systems (TOCS)},
volume={1},
number={3},
pages={222--238},
year={1983},
publisher={ACM}
}
Distributed Systems 2nd Edition, Editor Sape Mullender (1993)
Chapter 7:
Chapter 8: The Primary-Backup Approach
@inproceedings{budhiraja1993primary,
title={The primary-backup approach},
author={Budhiraja, Navin and Marzullo, Keith and Schneider, Fred B and Toueg, Sam},
booktitle={Distributed systems (2nd Ed.)},
pages={199--216},
year={1993},
organization={ACM Press/Addison-Wesley Publishing Co.}
}
