Distributed operating system: Difference between revisions

Revision as of 15:37, 26 July 2020

Revision as of 15:46, 26 July 2020

Line 40:

Research and experimentation efforts began in earnest in the 1970s and continued through 1990s, with focused interest peaking in the late 1980s. A number of distributed operating systems were introduced during this period; however, very few of these implementations achieved even modest commercial success.

Fundamental and pioneering implementations of primitive distributed operating system component concepts date to the early 1950s.<ref name=dyseac>{{cite journal |last1=Leiner |first1=Alan L. |title=System Specifications for the DYSEAC |journal=Journal of the ACM |date=April 1954 |volume=1 |issue=2 |pages=57–81 |doi=10.1145/320772.320773 |doi-access=free |via=ACM Digital Library}}</ref><ref name=lincoln_tx2>{{cite conference |title=The Lincoln TX-2 Input-Output System |first=James W. |last=Forgie |date=February 26–28, 1957 |conference=Western Joint Computer Conference: Techniques for Reliability |publisher=Association for Computing Machinery |___location=Los Angeles, California |pages=156–160 |isbn=9781450378611 |doi=10.1145/1455567.1455594 |doi-access=free |via=ACM Digital Library}}</ref><ref name=intercomm_cells>{{cite conference |author=C. Y. Lee |title=Intercommunicating cells, basis for a distributed logic computer |date=December 4–6, 1962 |conference=Fall Joint Computer Conference |publisher=Association for Computing Machinery |via=ACM Digital Library |___location=Philadelphia, Pennsylvania |pages=130–136 |doi=10.1145/1461518.1461531 |doi-access=free}}</ref> Some of these individual steps were not focused directly on distributed computing, and at the time, many may not have realized their important impact. These pioneering efforts laid important groundwork, and inspired continued research in areas related to distributed computing.<ref name="Dreyfus_1958_Gamma60">{{citation |title=System design of the Gamma 60 |author-first=Phillippe |author-last=Dreyfus |author-link=Philippe Dreyfus |work=Proceedings of the May 6–8, 1958, [[Western Joint Computer Conference]]: Contrasts in Computers |___location=Los Angeles |date=1958-05-08 |orig-year=1958-05-06 |id=IRE-ACM-AIEE '58 (Western) |publication-place=ACM, New York, NY, USA |pages=130–133 |url=https://www.computer.org/csdl/proceedings/afips/1958/5052/00/50520130.pdf |access-date=2017-04-03 |url-status=live |archive-url=https://web.archive.org/web/20170403224547/https://www.computer.org/csdl/proceedings/afips/1958/5052/00/50520130.pdf |archive-date=2017-04-03}}</ref><ref>Leiner, A. L., Notz, W. A., Smith, J. L., and Weinberger, A. 1958. Organizing a network of computers to meet deadlines. In Papers and Discussions Presented At the December 9–13, 1957, Eastern Joint Computer Conference: Computers with Deadlines To Meet (Washington, D.C., December 09–13, 1957). IRE-ACM-AIEE '57</ref><ref>Leiner, A. L., Smith, J. L., Notz, W. A., and Weinberger, A. 1958. PILOT, the NBS multicomputer system. In Papers and Discussions Presented At the December 3–5, 1958, Eastern Joint Computer Conference: Modern Computers: Objectives, Designs, Applications (Philadelphia, Pennsylvania, December 03–05, 1958). AIEE-ACM-IRE '58 (Eastern). ACM, New York, NY, 71-75.</ref><ref>Bauer, W. F. 1958. Computer design from the programmer's viewpoint. In Papers and Discussions Presented At the December 3–5, 1958, Eastern Joint Computer Conference: Modern Computers: Objectives, Designs, Applications (Philadelphia, Pennsylvania, December 03–05, 1958). AIEE-ACM-IRE '58 (Eastern). ACM, New York, NY, 46-51.</ref><ref>Leiner, A. L., Notz, W. A., Smith, J. L., and Weinberger, A. 1959. PILOT—A New Multiple Computer System. J. ACM 6, 3 (Jul. 1959), 313-335.</ref><ref>Estrin, G. 1960. [https://dl.acm.org/doi/abs/10.1145/1460361.1460365 Organization of computer systems: the fixed plus variable structure computer]. In Papers Presented At the May 3–5, 1960, Western Joint IRE-AIEE-ACM Computer Conference (San Francisco, California, May 03–05, 1960). IRE-AIEE-ACM '60 (Western). ACM, New York, NY, 33-40.</ref>

In the mid-1970s, research produced important advances in distributed computing. These breakthroughs provided a solid, stable foundation for efforts that continued through the 1990s.

Line 91:

====Coherent memory abstraction====

{{pad|2em}} Algorithms for scalable synchronization on [[shared memory|shared-memory]] multiprocessors <ref>Mellor-Crummey, J. M. and Scott, M. L. 1991. [https://dl.acm.org/doi/abs/10.1145/103727.103729 Algorithms for scalable synchronization on shared-memory multiprocessors]. ACM Trans. Comput. Syst. 9, 1 (Feb. 1991), 21-65.</ref>

====File System abstraction====

{{pad|2em}}Measurements of a [[distributed file system]]<ref>Baker, M. G., Hartman, J. H., Kupfer, M. D., Shirriff, K. W., and Ousterhout, J. K. 1991. [http://people.csail.mit.edu/ledlie/resources/papers/1991/baker.ps Measurements of a distributed file system]. In Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles (Pacific Grove, California, United States, October 13–16, 1991). SOSP '91. ACM, New York, NY, 198-212.</ref>

<br />{{pad|2em}}Memory coherence in shared virtual memory systems <ref>Li, K. and Hudak, P. 1989. Memory coherence in shared virtual memory systems. ACM Trans. Comput. Syst. 7, 4 (Nov. 1989), 321-359.</ref>

Line 102:

{{pad|2em}}''Transactional Memory''

<br />{{pad|4em}}Composable memory transactions<ref>Harris, T., Marlow, S., [[Simon Peyton Jones|Peyton-Jones, S.]], and Herlihy, M. 2005. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.77.3476&rep=rep1&type=pdf Composable memory transactions]. In Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Chicago, IL, USA, June 15–17, 2005). PPoPP '05. ACM, New York, NY, 48-60.</ref>

<br />{{pad|4em}}Transactional memory: architectural support for lock-free data structures <ref>Herlihy, M. and Moss, J. E. 1993. [http://hpl.americas.hp.net/techreports/Compaq-DEC/CRL-92-7.pdf Transactional memory: architectural support for lock-free data structures]. In Proceedings of the 20th Annual international Symposium on Computer Architecture (San Diego, California, United States, May 16–19, 1993). ISCA '93. ACM, New York, NY, 289-300.</ref>

<br />{{pad|4em}}Software transactional memory for dynamic-sized data structures<ref>Herlihy, M., Luchangco, V., Moir, M., and Scherer, W. N. 2003. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.8787&rep=rep1&type=pdf Software transactional memory for dynamic-sized data structures]. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing (Boston, Massachusetts, July 13–16, 2003). PODC '03. ACM, New York, NY, 92-101.</ref>

<br />{{pad|4em}}Software transactional memory<ref>Shavit, N. and Touitou, D. 1995. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.474.5928&rep=rep1&type=pdf Software transactional memory]. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing (Ottawa, Ontario, Canada, August 20–23, 1995). PODC '95. ACM, New York, NY, 204-213.</ref>

====Persistence abstraction====

{{pad|2em}}OceanStore: an architecture for global-scale persistent storage <ref>Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Wells, C., and Zhao, B. 2000. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.439.4822&rep=rep1&type=pdf OceanStore: an architecture for global-scale persistent storage]. In Proceedings of the Ninth international Conference on Architectural Support For Programming Languages and Operating Systems (Cambridge, Massachusetts, United States). ASPLOS-IX. ACM, New York, NY, 190-201.</ref>

====Coordinator abstraction====

{{pad|2em}} Weighted voting for replicated data <ref>Gifford, D. K. 1979. [http://pages.cs.wisc.edu/~remzi/Classes/739/Spring2004/Papers/p150-gifford.pdf Weighted voting for replicated data]. In Proceedings of the Seventh ACM Symposium on Operating Systems Principles (Pacific Grove, California, United States, December 10–12, 1979). SOSP '79. ACM, New York, NY, 150-162</ref>

<br />{{pad|2em}} Consensus in the presence of partial synchrony <ref>Dwork, C., Lynch, N., and Stockmeyer, L. 1988. [https://groups.csail.mit.edu/tds/papers/Lynch/MIT-LCS-TM-270.pdf Consensus in the presence of partial synchrony]. J. ACM 35, 2 (Apr. 1988), 288-323.</ref>

====Reliability abstraction====

{{pad|2em}}''Sanity checks''

<br />{{pad|4em}}The Byzantine Generals Problem <ref>Lamport, L., Shostak, R., and Pease, M. 1982. [http://people.cs.uchicago.edu/~shanlu/teaching/33100_wi15/papers/byz.pdf The Byzantine Generals Problem]. ACM Trans. Program. Lang. Syst. 4, 3 (Jul. 1982), 382-401.</ref>

<br />{{pad|4em}}Fail-stop processors: an approach to designing fault-tolerant computing systems <ref>Schlichting, R. D. and Schneider, F. B. 1983. Fail-stop processors: an approach to designing fault-tolerant computing systems. ACM Trans. Comput. Syst. 1, 3 (Aug. 1983), 222-238.</ref>