Concepts for Distributed Systems Design

This book is written for computer programmers, analysts and scientists, as well as computer science students, as an intro­ duction to the principles of distributed system design. The emphasis is placed on a clear understanding of the concepts, rather than on details; and the reader will learn about the struc­ ture of distributed systems, their problems, and approaches to their design and development. The reader should have a basic knowledge of computer systems and be familiar with modular design principles for software development. He should also be aware of present-day remote-access and distributed computer applications. The book consists of three parts which deal with prin­ ciples of distributed systems, communications architecture and protocols, and formal description techniques. The first part serves as an introduction to the broad meaning of "distributed system". We give examples, try to define terms, and discuss the problems that arise in the context of parallel and distributed processing. The second part presents the typical layered protocol architecture of distributed systems, and discusses problems of compatibility and interworking between heterogeneous computer systems. The principles of the lower layer functions and protocols are explained in some detail, including link layer protocols and network transmission services. The third part deals with specification issues. The role of specifications in the design of distributed systems is explained in general, and formal methods for the specification, analysis and implementation of distributed systems are discussed.

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).