1 INTRODUCTION TO DISTRIBUTED SYSTEMS

1.1　WHAT IS A DISTRIBUTED SYSTEM?

1.2 GOALS

1.2.1 Advantages of Distributed Systems over Centralized Systems

1.2.2 Advantages of Distributed Systems over Independent PCs

1.2.3 Disadvantages of Distributed Systems

1.3 HARDWARE CONCEPTS

1.3.1 Bus-Based Multiprocessors

1.3.2 Switched Multiprocessors

1.3.3 Bus-Based Multicomputers

1.3.4 Switched Multicomputers

1.4 SOFTWARE CONCEPTS

1.4.1 Network Operating Systems

Contents

PREFACE　

1.4.2 True Distributed Systems

1.4.3 Multiprocessor Timesharing Systems

1.5.1 Transparency

1.5 DESIGN ISSUES

1.5.2 Flexibility

1.5.3 Reliability

1.5.4 Performance

1.5.5 Scalability

1.6 SUMMARY

2 COMMUNICATION IN DISTRIBUTED SYSTEMS

2.1 LAYERED PROTOCOLS

2.1.2 The Data Link Layer

2.1.1 The Physical Layer

2.1.3 The Network Layer

2.1.4 The Transport Layer

2.1.5 The Session Layer

2.1.6 The Presentation Layer

2.1.7 The Application Layer

2.2 ASYNCHRONOUS TRANSFER MODE NETWORKS

2.2.1 What Is Asynchronous Transfer Mode?

2.2.2 The ATM Physical Layer

2.2.3 The ATM Layer

2.2.4 The ATM Adaptation Layer

2.2.5 ATM Switching

2.2.6 Some Implications of ATM for Distributed Systems

2.3 THE CLIENT-SERVER MODEL

2.3.1 Clients and Servers

2.3.2 An Example Client and Server

2.3.3 Addressing

2.3.4 Blocking versus Nonblocking Primitives

2.3.5 Buffered versus Unbuffered Primitives

2.3.6 Reliable versus Unreliable Primitives

2.3.7 Implementing the Client-Server Model

2.4 REMOTE PROCEDURE CALL

2.4.1 Basic RPC Operation

2.4.2 Parameter Passing

2.4.3 Dynamic Binding

2.4.4 RPC Semantics in the Presence of Failures

2.4.5 Implementation Issues

2.4.6 Problem Areas

2.5.1 Introduction to Group Communication

2.5 GROUP COMMUNICATION

2.5.2 Design Issues

2.5.3 Group Communication in ISIS

2.6 SUMMARY

3 SYNCHRONIZATION IN DISTRIBUTED SYSTEMS

3.1 CLOCK SYNCHRONIZATION

3.1.1 Logical Clocks

3.1.2 Physical Clocks

3.1.3 Clock Synchronization Algorithms

3.1.4 Use of Synchronized Clocks

3.2 MUTUAL EXCLUSION

3.2.1 A Centralized Algorithm

3.2.2 A Distributed Algorithm

3.2.3 A Token Ring Algorithm

3.2.4 A Comparison of the Three Algorithms

3.3 ELECTION ALGORITHMS

3.3.1 The Bully Algorithm

3.3.2 A Ring Algorithm

3.4.1 Introduction to Atomic Transactions

3.4 ATOMIC TRANSACTIONS

3.4.2 The Transaction Model

3.4.3 Implementation

3.4.4 Concurrency Control

3.5 DEADLOCKS IN DISTRIBUTED SYSTEMS

3.5.1 Distributed Deadlock Detection

3.5.2 Distributed Deadlock Prevention

3.6 SUMMARY

4.1 THREADS

4 PROCESSES AND PROCESSORS IN DISTRIBUTED SYSTEMS

4.1.1 Introduction to Threads

4.1.2 Thread Usage

4.1.3 Design Issues for Threads Packages

4.1.4 Implementing a Threads Package

4.1.5 Threads and RPC

4.2 SYSTEM MODELS

4.2.1 The Workstation Model

4.2.2 Using Idle Workstations

4.2.3 The Processor Pool Model

4.2.4 AHybridModel

4.3 PROCESSOR ALLOCATION

4.3.1 Allocation Models

4.3.2 Design Issues for Processor Allocation Algorithms

4.3.3 Implementation Issues for Processor Allocation Algorithms

4.3.4 Example Processor Allocation Algorithms

4.4 SCHEDULING IN DISTRIBUTED SYSTEMS

4.5.1 Component Faults

4.5 FAULT TOLERANCE

4.5.2 System Failures

4.5.3 Synchronous versus Asynchronous Systems

4.5.4 Use of Redundancy

4.5.5 Fault Tolerance Using Active Replication

4.5.6 Fault Tolerance Using Primary-Backup

4.5.7 Agreement in Faulty Systems

4.6 REAL-TIME DISTRIBUTED SYSTEMS

4.6.1 What Is a Real-Time System?

4.6.2 Design Issues

4.6.3 Real-Time Communication

4.6.4 Real-Time Scheduling

4.7 SUMMARY

5 DISTRIBUTED FILE SYSTEMS

5.1 DISTRIBUTED FILE SYSTEM DESIGN

5.1.1 The File Service Interface

5.1.2 The Directory Server Interface

5.1.3 Semantics of File Sharing

5.2 DISTRIBUTED FILE SYSTEM IMPLEMENTATION

5.2.1 File Usage

5.2.2 System Structure

5.2.3 Caching

5.2.4 Replication

5.2.5 An Example:Sun's Network File System

5.2.6 Lessons Learned

5.3 TRENDS IN DISTRIBUTED FILE SYSTEMS

5.3.1 New Hardware

5.3.2 Scalability

5.3.3 Wide Area Networking

5.3.5 Fault Tolerance

5.3.4 Mobile Users

5.3.6 Multimedia

5.4 SUMMARY

6 DISTRIBUTED SHARED MEMORY

6.1 INTRODUCTION

6.2 WHAT IS SHARED MEMORY?

6.2.1 On-Chip Memory

6.2.2 Bus-Based Multiprocessors

6.2.3 Ring-Based Multiprocessors

6.2.4 Switched Multiprocessors

6.2.5 NUMA Multiprocessors

6.2.6 Comparison of Shared Memory Systems

6.3 CONSISTENCY MODELS

6.3.1 Strict Consistency

6.3.2 Sequential Consistency

6.3.3 Causal Consistency

6.3.4 PRAM Consistency and Processor Consistency

6.3.5 Weak Consistency

6.3.6 Release Consistency

6.3.7 Entry Consistency

6.3.8 Summary of Consistency Models

6.4 PAGE-BASED DISTRIBUTED SHARED MEMORY

6.4.1 Basic Design

6.4.2 Replication

6.4.3 Granularity

6.4.4 Achieving Sequential Consistency

6.4.5 Finding the Owner

6.4.6 Finding the Copies

6.4.7 Page Replacement

6.4.8 Synchronization

6.5 SHARED-VARIABLE DISTRIBUTED SHARED MEMORY

6.5.1 Munin

6.5.2 Midway

6.6 OBJECT-BASED DISTRIBUTED SHARED MEMORY

6.6.1 Objects

6.6.2 Linda

6.6.3 Orca

6.7 COMPARISON

6.8 SUMMARY

7 CASE STUDY 1:AMOEBA

7.1 INTRODUCTION TO AMOEBA

7.1.1 History of Amoeba

7.1.2 Research Goals

7.1.3 The Amoeba System Architecture

7.1.4 The Amoeba Microkernel

7.1.5 The Amoeba Servers

7.2.1 Capabilities

7.2 OBJECTS AND CAPABILITIES IN AMOEBA

7.2.2 Obiect Protection

7.2.3 Standard Operations

7.3 PROCESS MANAGEMENT IN AMOEBA

7.3.1 Processes

7.3.2 Threads

7.4 MEMORY MANAGEMENT IN AMOEBA

7.4.1 Segments

7.4.2 Mapped Segments

7.5 COMMUNICATION IN AMOEBA

7.5.1 Remote Procedure Call

7.5.2 Group Communication in Amoeba

7.5.3 The Fast Local Internet Protocol

7.6 THE AMOEBA SERVERS

7.6.1 The Bullet Server

7.6.2 The Directory Server

7.6.3 The Replication Server

7.6.4 The Run Server

7.6.6 The TCP/IP Server

7.6.5 The Boot Server

7.6.7 Other Servers

7.7 SUMMARY

8 CASE STUDY 2:MACH

8.1 INTRODUCTION TO MACH

8.1.1 History of Mach

8.1.2 Goals of Mach

8.1.3 The Mach Microkernel

8.1.4 The Mach BSD UNIX Server

8.2.1 Processes

8.2 PROCESS MANAGEMENT IN MACH

8.2.2 Threads

8.2.3 Scheduling

8.3 MEMORY MANAGEMENT IN MACH

8.3.1 Virtual Memory

8.3.2 Memory Sharing

8.3.3 External Memory Managers

8.3.4 Distributed Shared Memory in Mach

8.4.1 Ports

8.4 COMMUNICATION IN MACH

8.4.2 Sending and Receiving Messages

8.4.3 The Network Message Server

8.5 UNIX EMULATION IN MACH

8.6 SUMMARY

9 CASE STUDY 3:CHORUS

9.1 INTRODUCTION TO CHORUS

9.1.1 History of Chorus

9.1.2 Goals of Chorus

9.1.3 System Structure

9.1.4 Kernel Abstractions

9.1.5 Kernel Structure

9.1.6 The UNIX Subsystem

9.1.7 The Object-Oriented Subsystem

9.2 PROCESS MANAGEMENT IN CHORUS

9.2.1 Processes

9.2.2 Threads

9.2.3 Scheduling

9.2.4 Traps,Exceptions,and Interrupts

9.2.5 Kernel Calls for Process Management

9.3 MEMORY MANAGEMENT IN CHORUS

9.3.1 Regions and Segments

9.3.2 Mappers

9.3.3 Distributed Shared Memory

9.3.4 Kernel Calls for Memory Management

9.4 COMMUNICATON IN CHORUS

9.4.1 Messages

9.4.2 Ports

9.4.3 Communication Operations

9.4.4 Kernel Calls for Communication

9.5 UNIX EMULATION IN CHORUS

9.5.1 Structure of a UNIX Process

9.5.2 Extensions to UNIX

9.5.3 Implementation of UNIX on Chorus

9.6 COOL:AN OBJECT-ORIENTED SUBSYSTEM

9.6.1 The COOL Architecture

9.6.2 The COOL Base Layer

9.6.3 The COOL Generic Runtime System

9.6.4 The Language Runtime System

9.7 COMPARISON OF AMOEBA,MACH,AND CHORUS

9.6.5 Implementation of COOL

9.7.1 Philosophy

9.7.2 Obiects

9.7.3 Processes

9.7.4 Memory Model

9.7.5 Communication

9.7.6 Servers

9.8 SUMMARY

10.1.1 History of DCE

10 CASE STUDY 4:DCE

10.1 INTRODUCTION TO DCE

10.1.2 Goals of DCE

10.1.3 DCE Components

10.1.4 Cells

10.2 THREADS

10.2.1 Introduction to DCE Threads

10.2.2 Scheduling

10.2.3 Synchronization

10.2.4 Thread Calls

10.3 REMOTE PROCEDURE CALL

10.3.1 Goals of DCE RPC

10.3.2 Writing a Client and a Server

10.3.3 Binding a Client to a Server

10.3.4 Performing an RPC

10.4 TIME SERVICE

10.4.1 DTS Time Model

10.4.2 DTS Implementation

10.5 DIRECTORY SERVICE

10.5.1 Names

10.5.2 The Cell Directory Service

10.5.3 The Global Directory Service

10.6 SECURITY SERVICE

10.6.1 Security Model

10.6.2 Security Components

10.6.3 Tickets and Authenticators

10.6.4 Authenticated RPC

10.6.5 ACLs

10.7 DISTRIBUTED FILE SYSTEM

10.7.1 DFS Interface

10.7.2 DFS Components in the Server Kernel

10.7.3 DFS Components in the Client Kernel

10.7.4 DFS Components in User Space

10.8 SUMMARY

11 BIBLIOGRAPHY AND SUGGESTED READINGS

11.1 SUGGESTED READINGS

11.2 ALPHABETICAL BIBLIOGRAPHY

INDEX