Concepts for Distributed Systems Design

I: The Nature of Distributed Systems.- 1. Distributed systems: examples and definition.- 1.1 Distribution of control and data in existing systems.- 1.1.1 Systems distributed over long distance.- 1.1.1.1 Remote access.- 1.1.1.2 Computer networks.- 1.1.1.3 Systems for distributed processing.- 1.1.2 Locally distributed systems.- 1.1.3 Multi-processor systems.- 1.1.4 Virtual distribution.- 1.2 Classification of distributed systems.- 1.2.1 Degree of coupling.- 1.2.2 Interconnection structure.- 1.2.3 Interdependence of components.- 1.2.4 Synchronization between components.- 1.3 Definition of "distributed system".- 2. Parallelism.- 2.1 Parallel processes and applications.- 2.2 Constraints on independence.- 2.3 Modular system structure and abstraction.- 3. Common problems.- 3.1 Cooperation.- 3.1.1 Compatibility.- 3.1.2 Synchronization.- 3.2 Distributed resource sharing.- 3.3 Naming and addressing.- 3.3.1 Search strategies for link editors.- 3.3.2 Naming of I/O flows.- 3.3.3 Addressing scheme of telephone networks.- 3.3.4 Process addressing by ports.- 3.4 Protection.- 3.4.1 Protection in distributed systems.- 3.5 Error recovery.- 3.5.1 Error detection.- 3.5.2 Recovery by retry.- 3.5.3 Redundant hardware.- 3.5.4 The design principle of recovery blocks.- 3.6 Real time considerations.- 3.6.1 Time-outs.- 3.6.2 Clock synchronization in distributed systems.- II: Distributed System Architecture and Communication Protocols.- 4. Architecture of distributed systems.- 4.1 Layered hierarchical system structure and physical distribution.- 4.2 Typical structure of a distributed system.- 4.2.1 Communication over a dedicated circuit.- 4.2.2 Communication through a network.- 4.2.3 A uniform transport service.- 4.2.4 Higher level protocols.- 4.3 Compatibility and interworking issues.- 4.3.1 Requirements for compatibility.- 4.3.2 Network interconnection.- 4.3.3 System interworking and adaptation.- 5. Message transport requirements and data transmission networks.- 5.1 Message transport requirements.- 5.2 Data transmission services.- 5.2.1 Dedicated circuits.- 5.2.2 Switching.- 5.2.3 Circuit and packet switching.- 5.3 The transport protocol.- 6. Link protocols.- 6.1 Transmission of bits.- 6.1.1 Interface procedures.- 6.1.2 Physical transmission media.- 6.1.3 Bit synchronization.- 6.2 Transparency and framing.- 6.2.1 Bit-oriented method.- 6.2.2 Character-oriented method.- 6.2.3 Method based on envelope transmission.- 6.3 Transmission error detection and correction.- 6.3.1 Principles.- 6.3.2 Error detecting codes.- 6.3.3 Error correcting codes.- 6.4 Retransmission protocols.- 6.4.1 Principles.- 6.4.2 The "alternating bit" protocol.- 6.4.3 The HDLC classes of procedures.- 6.4.4 Multiplexing.- 7. Technological developments and standards.- III: Formal Description Techniques.- 8. Role of specifications in the design of distributed systems.- 8.1 Specification of different scope and detail.- 8.1.1 The "reference model".- 8.1.2 Service specifications.- 8.1.3 Protocol specifications.- 8.1.4 Implementation specifications.- 8.2 System design validation.- 8.3 Protocol implementation assessment.- 8.4 Protocol implementation.- 9. A state transition formalism for the description of systems.- 9.1 The basic model.- 9.1.1 Transition systems.- 9.1.2 Operations.- 9.1.3 Transitions and relations between states.- 9.1.4 Abstraction.- 9.1.5 Parallelism and functionality.- 9.2 Reachability and execution sequences.- 9.2.1 Possible operation sequences.- 9.2.2 Liveness.- 9.2.3 Equivalence between systems.- 9.3 Synchronization mechanisms.- 9.4 Non-instantaneous operations.- 9.4.1 Mutual exclusion.- 9.4.2 Queueing condiserations and scheduling.- 9.5 Processes.- 9.5.1 The concept.- 9.5.2 Cooperation.- 9.5.3 Mutual exclusion.- 9.6 The induction principle.- 9.7 Distinction between "control structure" and "interpretation".- 9.8 Assertions.- 9.9 Formalized specification methods for systems with parallelism.- 10. A formal description technique for distributed systems.- 10.1 Discussion of specification concepts.- 10.1.1 Components and their interactions.- 10.1.2 Ports and interconnections.- 10.1.3 Elements of a specification.- 10.2 A transport service specification.- 10.2.1 Ports and interaction primitives.- 10.2.2 Local rules for a service access point.- 10.2.3 Specification of the service provider component.- 10.3 Step-wise refinement of specifications.- 10.3.1 The internal structure of components: examples.- 10.3.2 Comments on component substructure.- 10.3.3 Port refinements.- References.- Annex: Possible approaches to stepwise refinement, protocol specification and implementation.- Annex 1: A general transition model for protocols and communication services (G.v. Bochmann).- Annex 2: Development and structure of an X.25 implementation (G.v. Bochmann and J. Tankoano).- Annex 3: Structured specification of communicating systems (G.v. Bochmann and M. Raynal).