1 INTRODUCTION TO DISTRIBUTED SYSTEMS 1.1 WHAT IS A DISTRIBUTED SYSTEM? 1.2 GOALS 1.2.1 Advantages of Diributed Systems over Centralized Systems 1.2.2 Advantages of Dirtributed Systems over Independent PC 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 1.4.2 True Distributed Systems 1.4.3 Multiprocessor Timesharing Systems 1.5 DESIGN ISSUES 1.5.1 Transparency 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.1 The physical Layer 2.1.2 The Data Link 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 Laurie 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 Unbuttered 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 GROUP COMMUNICATION 2.5.1 Introduction to 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 ATOMIC TRANSACTIONS 3.4.1 Introduction to 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 RECESSES AND PROCESSORS IN DISTRIBUTED SYSTEM 4.1 THREADS 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 A hybrid Model 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 SYSTEM 4.5 FAULT TOLERANCE 4.5.1 Component Faults 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.4 Mobile Users 5.3.5 Fault Tolerance 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 NUMB 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 Minion 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 Microkernel 7.2 OBJECTS AND CAPABILITIES IN AMOEBA 7.2.1 Capabilities 7.2.2 Object Protection 7.2.3 Standard Operations 7.3 PROCEEDS 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 Croup 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.5 The Boot Server 7.6.6 The TCP/IP 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 PROCESS MANAGEMENT TN MACH 8.2.1 Processes 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 COMMUNICATION IN MACH 8.4.1 Ports 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.4 Regions and Segments 9.3.2 Mappers 9.3.3 Distributed Shared Memory 9.3.4 Kernel Calls for Memory Management 9.4 COMMUNICATION 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.6.5 Implementation of COOL 9.7 COMPARISON OF AMOEBA,MACH ,AND CHORUS 9.7.1 Philosophy 9.7.2 Objects 9.7.3 Processes 9.7.4 memory Model 9.7.5 Communication 9.7.6 Servers 9.8 SUMMARY 10 CASE STUDY 4:DCE 10.1 INTRODUCTION TO DCE 10.1.1 History of 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 SERVE 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