Distributed operating system

  Added initial entry...
  JLSjr (talk) 04:56, 15 March 2010 (UTC)

  Added "Introduction" outline; framework of text to come...
  JLSjr (talk) 12:48, 13 March 2010 (UTC)

---

Distributed operating system is a decentralized operating system, with its functionality disseminated across multiple, independent processing entities. The system is able to project a complete, consistent, and transparent abstraction; presenting a façade, understood by a user in a familiar centralized context. This abstraction hides the system's distributed nature, not simply separating a user from inherent complexity, but preventing its indication altogether.


This is a more in-depth outline of the "Lead" section text being developed, and will be installed very soon...
DOS is an OS
  isolates and manages lower-level complexities of Hware and resources into abstractions
  organizes these abstractions, and presents higher-level interfaces of Hware and resources to apps and users
  OS is the complex mapping of these abstractions to interfaces
  in doing so, the OS presents itself as unified and simplified service to these mappings
  DOS, in this context, appears no different than would a centralized OS
  but in fact, is much different

  OS most often depicted as a discrete organizational container, positioned independently between Hware and app/programmer/etc.
  DOS, presented in a similar fashion would incorporate Hware within its organizational container
  it is the Hware that exhibits differing degrees of spatial separation; DOSs distributed quality
  to provide consistent and unified interface to this abstraction, Hware must be considered internal to the idea of DOS

  This is a very important distinction, as
  it allows a DOS to appear to a user as would a standard centralized OS; singular and local
  it makes possible many additional and beneficial services (described in later section)
  it will serve differentiate DOS from other OSs
  again, it is solely this attribute of Hware dissemination that allows for these benefits
  however, a complex internal orchestration of this attribute is required to realize these benefits

Overview

An approach to describing the unique nature of DOS
  A Distributed OS is decentralized, but has additional specific attributes; it is distributed
  compared to a standard OS which is centralized and local
  or a Network OS which is decentralized, and while possibly spatially scattered, is not distributed

  to demonstrate, consider an OSs constituent element organization: decentralized vs. distributed
  three tightly interrelated aspects to this organization:
  organizational hierarchy, degree of interconnection, sphere of control
  organizational hierarchy:
  centralized:
  dictatorship - one level
  all entities report directly to one higher-level entity
  decentralized:
  federated - one or more levels
  any given sub-level's entities reporting directly to next higher-level entity
  distributed:
  autonomous - no levels required
  all entities reporting directly/indirectly to an appointed coordinator
  degree of interconnection:
  centralized:
  single direct connection
  balloons on a string
  decentralized:
  single direct/indirect connection
  corporate org-chart (no dotted lines)
  twigs, limbs, branches of a tree
  distributed:
  multiple direct/indirect connections possible
  string art, spiro-graph (completely connected)
  spider web (closest neighbors)
  interstate system (suited to purpose)
  sphere of control:
  centralized:
  direct and absolute
  decentralized:
  shared by level, through delegation and follow-up
  distributed:
  collective, usually through mutual agreement

  DOS is an OS with a unique set of constitutional characteristics
  providing opportunity for an exceptional array of additional and extended services
  while overcoming extreme quantities and degrees of complexity in the process

Architectural features

Transparency

 Common execution paradigm across multiple distributed entities
 Complexity involves:
 asynchronous communication
 non-uniform memory access
 probability of faults
 possibility of heterogeneous remote resources
 Distributed operating system must be able to isolate users from complexities
 Provide a complete and consistent abstraction of resources, across the distributed system

Modularity

 System abstraction composed from modular subcomponents/entities
 Entities usually smaller, functionally-cohesive, cooperative, and stateful

Persistence of Entity state

 existance not time-bound, regardless of breaks in system functions continuously
 resides in nonvolatile storage; synchronized with current, stable, active copy
 Subject to consistent and timely updates
 Able to survive hardware failure

Efficiency

 Many issues can adversly affect system performance:
 latency in interactions among distributed entities
 local response facade requires remote entities' state be cached locally
 and consistently synchronized to maintain the paradigm
 Workload variations, delays, interruptions, faults, and/or crashes of entities
 Distributed processing community assists when needed

Replication

 Duplication of state among selected distributed entities, and the synchronization of that state
 Remote communication required to effect synchronization

Reliability

 Inherent redundancy across the distributed entities provides fault-tolerance
 Consistent synchronized redundancy across N nodes, tolerates up to N-1 node faults

Flexibility

 OS has lattitude in degree of exposure to externals
 Externals have lattitude in degree of exposure they accept
 Coordination of process activity
 Where run; Near user?, resources?, avail. CPU?, etc...

Scalability

 node expansion
 process migration

History

Pioneering inspirations

Connectivity abstraction

Ethernet: distributed packet switching for local computer networks^[1]

Memory access abstraction

Intercommunicating Cells, Basis for a Distributed Logic Computer^[2] (1962)

The purpose of this paper is to describe an information storage and retrieval system in which logic is distributed throughout the system. The system is made up of cells. Each cell is a small finite state machine which can communicate with its neighboring cells ... The motivation stems from our contention that in the present generation of machines the scheme of locating a quantity of information by its "address" is fundamentally a weak one...

The association of an address with a quantity of information is very much the result of the type of computer organization we now have. Writing a program in machine language, one rarely deals with the quantities of information themselves. A programmer normally must know where these quantities of information are located. He then manipulates their addresses according to the problem at hand. An address in this way often assumes the role of the name of a piece of information...

Process abstraction

The Structure of the "THE"-Multiprogramming^[3] (1968)

A multiprogramming system is described in which all activities are divided over a number of sequential processes. These sequential processes are placed at various hierarchical levels, in each of which one or more independent abstractions have been implemented. The hierarchical structure proved to be vital for the verification of the logical soundness of the design and the correctness of its implementation.

Component abstraction

HYDRA:The Kernel of a Multiprocessor Operating System^[4] (1974)
The design philosophy of HYDRA ... suggest that, at the heart of the system, one should build a collection of facilities of "universal applicability" and "absolute reliability" -- a set of mechanisms from which an arbitrary set of operating system facilities and policies can be conveniently, flexibly, efficiently, and reliably constructed.
Defining a kernel with all the attributes given above is difficult, and perhaps impractical... It is, nevertheless, the approach taken in the HYDRA system. Although we make no claim either that the set of facilities provided by the HYDRA kernel ... we do believe the set provides primitives which are both necessary and adequate for the construction of a large and interesting class of operating environments. It is our view that the set of functions provided by HYDRA will enable the user of C.mmp to create his own operating environment without being confined to predetermined command and file systems, execution scenarios, resource allocation policies, etc.

Initial composition

The National Software Works: A Distributed Processing System^[5] (1975)

The National Software Works (NSW) is a significant new step in the development of distributed processing systems and computer networks. NSW is an ambitious project to link a set of geographically distributed and diverse hosts with an operating system which appears as a single entity to a prospective user.

Complete instantiation

The Rosco Distributed Operating System^[6] (1979)

Roscoe is an operating system implemented at the University of Wisconsin that allows a network of microcomputers to cooperate to provide a general-purpose computing facility. The goal of the Roscoe network is to provide a general-purpose computation resource in which individual resources such as files and processors are shared among processes and control is distributed in a non-hierarchical fashion. All processors are identical. Similarly, all processors run the same operating system kernel. However, they may differ in the peripheral units connected to them. No memory is shared between processors. All communication involves messages explicitly passed between physically connected processors. No assumptions are made about the topology of interconnection.

The decision not to use logical or physical sharing of memory for communication is influenced both by the constraints of currently available hardware and by our perception of cost bottlenecks likely to arise as the number of processors increases.

Foundational Work

Coherent memory abstraction

 Algorithms for scalable synchronization on shared-memory multiprocessors^[7]
 A N algorithm for mutual exclusion in decentralized systems^[8]

File System abstraction

 Measurements of a distributed file system^[9]
 Memory coherence in shared virtual memory systems^[10]

Transaction abstraction

 Transactions
 Sagas^[11]

 Transactional Memory
 Composable memory transactions^[12]
 Transactional memory: architectural support for lock-free data structures^[13]
 Software transactional memory for dynamic-sized data structures^[14]
 Software transactional memory^[15]

Persistence abstraction

 OceanStore: an architecture for global-scale persistent storage^[16]

Coordinator abvstraction

 Weighted voting for replicated data^[17]
 Consensus in the presence of partial synchrony^[18]

Reliability abstraction

 Sanity checks
 The Byzantine Generals Problem^[19]
 Fail-stop processors: an approach to designing fault-tolerant computing systems^[20]

 Recoverability
 Distributed snapshots: determining global states of distributed systems^[21]
 Optimistic recovery in distributed systems^[22]

Current Research

replicated model extended to a component object model

 Architectural Design of E1 Distributed Operating System^[23]
 The Cronus distributed operating system^[24]
 Fine-grained mobility in the emerald system^[25]
 Design and development of MINIX distributed operating system^[26]

Future Directions

System able to provide low-level complexity exposure, in proportion to trust and accepted responsibility

 Application performance and flexibility on exokernel systems.^[27]
 Scale and performance in the Denali isolation kernel.^[28]

Infrastructure focus on multi-processor/core

 The multikernel: a new OS architecture for scalable multicore systems.^[29]
 Corey: an Operating System for Many Cores.^[30]

System extends a consistent and stable impression of processing over extremes in heterogeneity

 Helios: heterogeneous multiprocessing with satellite kernels.^[31]

System able to provide effective, stable, and beneficial view of vastly inceased complexity on multiple levels

 Tesselation

References

1. Metcalfe, R. M. and Boggs, D. R. 1976. Ethernet: distributed packet switching for local computer networks. Commun. ACM 19, 7 (Jul. 1976), 395-404.
2. Lee, C. Y. 1962. Intercommunicating cells, basis for a distributed logic computer. In Proceedings of the December 4-6, 1962, Fall Joint Computer Conference (Philadelphia, Pennsylvania, December 04 - 06, 1962). AFIPS '62 (Fall).
3. Dijkstra, E. W. 1968. The structure of the “THE”-multiprogramming system. Commun. ACM 11, 5 (May. 1968), 341-346.
4. Wulf, W., Cohen, E., Corwin, W., Jones, A., Levin, R., Pierson, C., and Pollack, F. 1974. HYDRA: the kernel of a multiprocessor operating system. Commun. ACM 17, 6 (Jun. 1974), 337-345.
5. Millstein, R. E. 1977. The National Software Works: A distributed processing system. In Proceedings of the 1977 Annual Conference ACM '77. ACM, New York, NY, 44-52.
6. Solomon, M. H. and Finkel, R. A. 1979. The Roscoe distributed operating system. In Proceedings of the Seventh ACM Symposium on Operating Systems Principles (Pacific Grove, California, United States, December 10 - 12, 1979). SOSP '79.
7. Mellor-Crummey, J. M. and Scott, M. L. 1991. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9, 1 (Feb. 1991), 21-65.
8. Maekawa, M. 1985. A N algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst. 3, 2 (May. 1985), 145-159.
9. Baker, M. G., Hartman, J. H., Kupfer, M. D., Shirriff, K. W., and Ousterhout, J. K. 1991. 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.
10. Li, K. and Hudak, P. 1989. Memory coherence in shared virtual memory systems. ACM Trans. Comput. Syst. 7, 4 (Nov. 1989), 321-359.
11. Garcia-Molina, H. and Salem, K. 1987. Sagas. In Proceedings of the 1987 ACM SIGMOD international Conference on Management of Data (San Francisco, California, United States, May 27 - 29, 1987). U. Dayal, Ed. SIGMOD '87. ACM, New York, NY, 249-259.
12. Harris, T., Marlow, S., Peyton-Jones, S., and Herlihy, M. 2005. 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.
13. Herlihy, M. and Moss, J. E. 1993. 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.
14. Herlihy, M., Luchangco, V., Moir, M., and Scherer, W. N. 2003. 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.
15. Shavit, N. and Touitou, D. 1995. Software transactional memory. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing (Ottowa, Ontario, Canada, August 20 - 23, 1995). PODC '95. ACM, New York, NY, 204-213.
16. Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Wells, C., and Zhao, B. 2000. 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.
17. Gifford, D. K. 1979. 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
18. Dwork, C., Lynch, N., and Stockmeyer, L. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (Apr. 1988), 288-323.
19. Lamport, L., Shostak, R., and Pease, M. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4, 3 (Jul. 1982), 382-401.
20. 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.
21. Chandy, K. M. and Lamport, L. 1985. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 1 (Feb. 1985), 63-75.
22. Strom, R. and Yemini, S. 1985. Optimistic recovery in distributed systems. ACM Trans. Comput. Syst. 3, 3
23. L.B. Ryzhyk, A.Y. Burtsev. Architectural design of E1 distributed operating system. System Research and Information Technologies international scientific and technical journal, October 2004, Kiev, Ukraine.
24. Vinter, S. T. and Schantz, R. E. 1986. The Cronus distributed operating system. In Proceedings of the 2nd Workshop on Making Distributed Systems Work (Amsterdam, Netherlands, September 08 - 10, 1986). EW 2. ACM, New York, NY, 1-3.
25. Jul, E., Levy, H., Hutchinson, N., and Black, A. 1987. Fine-grained mobility in the emerald system. In Proceedings of the Eleventh ACM Symposium on Operating Systems Principles (Austin, Texas, United States, November 08 - 11, 1987). SOSP '87. ACM, New York, NY, 105-106.
26. Ramesh, K. S. 1988. Design and development of MINIX distributed operating system. In Proceedings of the 1988 ACM Sixteenth Annual Conference on Computer Science (Atlanta, Georgia, United States). CSC '88. ACM, New York, NY, 685.
27. M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Héctor M. Briceño, Russell Hunt, David Mazières, Thomas Pinckney, Robert Grimm, John Jannotti, and Kenneth Mackenzie. In the Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP '97), Saint-Malô, France, October 1997.
28. Whitaker, A., Shaw, M., and Gribble, S. D. 2002. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation
29. Baumann, A., Barham, P., Dagand, P., Harris, T., Isaacs, R., Peter, S., Roscoe, T., Schüpbach, A., and Singhania, A. 2009. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (Big Sky, Montana, USA, October 11 - 14, 2009). SOSP '09.
30. S. Boyd-Wickizer, H. Chen, R. Chen, Y. Mao, F. Kashoek, R. Morris, A. Pesterev, L. Stein, M. Wu, Y. Dai, Y. Zhang, and Z. Zhang. Proceedings of the 2008 Symposium on Operating Systems Design and Implementation (OSDI), December 2008.
31. Nightingale, E. B., Hodson, O., McIlroy, R., Hawblitzel, C., and Hunt, G. 2009. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (Big Sky, Montana, USA, October 11 - 14, 2009). SOSP '09.

External links

• Coming Soon...