Distributed Systems

by Tanenbaum, Andrew S.; van Steen, Maarten

• ISBN13: 9780130888938
• ISBN10: 0130888931
• Format: Hardcover
• Copyright: 2007-01-01
• Publisher: PRENTICE HALL

Summary

Virtually every computing system today is part of a distributed system. Programmers, developers, and engineers need to understand the underlying principles and paradigms as well as the real-world application of those principles. Now, internationally renowned expert Andrew S. Tanenbaum - with colleague Martin van Steen - presents a complete introduction that identifies the seven key principles of distributed systems, with extensive examples of each. Adds a completely new chapter on architecture to address the principle of organizing distributed systems. Provides extensive new material on peer-to-peer systems, grid computing and Web services, virtualization, and application-level multicasting. Updates material on clock synchronization, data-centric consistency, object-based distributed systems, and file systems and Web systems coordination. For all developers, software engineers, and architects who need an in-depth understanding of distributed systems.

Table of Contents

Preface	xvii
Introduction	1	(56)
Definition of a Distributed System	2	(2)
Goals	4	(12)
Connecting Users and Resources	4	(1)
Transparency	5	(3)
Openness	8	(2)
Scalability	10	(6)
Hardware Concepts	16	(6)
Multiprocessors	17	(2)
Homogeneous Multicomputer Systems	19	(2)
Heterogeneous Multicomputer Systems	21	(1)
Software Concepts	22	(20)
Distributed Operating Systems	22	(11)
Network Operating Systems	33	(3)
Middleware	36	(6)
The Client-Server Model	42	(11)
Clients and Servers	42	(4)
Application Layering	46	(4)
Client-Server Architectures	50	(3)
Summary	53	(4)
Communication	57	(78)
Layered Protocols	58	(10)
Lower-Level Protocols	61	(2)
Transport Protocols	63	(3)
Higher-Level Protocols	66	(2)
Remote Procedure Call	68	(17)
Basic RPC Operation	69	(4)
Parameter Passing	73	(4)
Extended RPC Models	77	(3)
Example: DCE RPC	80	(5)
Remote Object Invocation	85	(14)
Distributed Objects	86	(2)
Binding a Client to an Object	88	(2)
Static versus Dynamic Remote Method Invocations	90	(1)
Parameter Passing	91	(2)
Example 1: DCE Remote Objects	93	(2)
Example 2: Java RMI	95	(4)
Message-Oriented Communication	99	(20)
Persistence and Synchronicity in Communication	99	(5)
Message-Oriented Transient Communication	104	(4)
Message-Oriented Persistent Communication	108	(7)
Example: IBM MQSeries	115	(4)
Stream-Oriented Communication	119	(11)
Support for Continous Media	120	(3)
Streams and Quality of Service	123	(4)
Streams Synchronization	127	(3)
Summary	130	(5)
Processes	135	(48)
Threads	136	(9)
Introduction to Threads	136	(5)
Threads in Distributed Systems	141	(4)
Clients	145	(4)
User Interfaces	145	(2)
Client-Side Software for Distribution Transparency	147	(2)
Servers	149	(9)
General Design Issues	149	(3)
Object Servers	152	(6)
Code Migration	158	(15)
Approaches to Code Migration	158	(5)
Migration and Local Resources	163	(2)
Migration in Heterogeneous Systems	165	(3)
Example: D'Agents	168	(5)
Software Agents	173	(5)
Software Agents in Distributed Systems	173	(2)
Agent Technology	175	(3)
Summary	178	(5)
Naming	183	(58)
Naming Entities	184	(26)
Names, Identifiers, and Addresses	184	(5)
Name Resolution	189	(5)
The Implementation of a Name Space	194	(7)
Example: The Domain Name System	201	(5)
Example: X.500	206	(4)
Locating Mobile Entities	210	(15)
Naming versus Locating Entities	210	(2)
Simple Solutions	212	(4)
Home-Based Approaches	216	(1)
Hierarchical Approaches	217	(8)
Removing Unreferenced Entities	225	(13)
The Problem of Unreferenced Objects	225	(2)
Reference Counting	227	(4)
Reference Listing	231	(1)
Identifying Unreachable Entities	232	(6)
Summary	238	(3)
Synchronization	241	(50)
Clock Synchronization	242	(10)
Physical Clocks	243	(3)
Clock Synchronization Algorithms	246	(5)
Use of Synchronized Clocks	251	(1)
Logical Clocks	252	(6)
Lamport timestamps	252	(4)
Vector timestamps	256	(2)
Global State	258	(4)
Election Algorithms	262	(3)
The Bully Algorithm	262	(1)
A Ring Algorithm	263	(2)
Mutual Exclusion	265	(6)
A Centralized Algorithm	265	(1)
A Distributed Algorithm	266	(3)
A Token Ring Algorithm	269	(1)
A Comparison of the Three Algorithms	270	(1)
Distributed Transactions	271	(17)
The Transaction Model	272	(3)
Classification of Transactions	275	(3)
Implementations	278	(2)
Concurrency Control	280	(8)
Summary	288	(3)
Consistency and Replication	291	(70)
Introduction	292	(5)
Reasons for Republication	292	(1)
Object Replication	293	(3)
Replication as Scaling Technique	296	(1)
Data-Centric Consistency Models	297	(19)
Strict Consistency	298	(2)
Linerizability and Sequential Consistency	300	(5)
Causal Consistency	305	(1)
FIFO Consistency	306	(2)
Weak Consistency	308	(2)
Release Consistency	310	(3)
Entry Consistency	313	(2)
Summary of Consistency Models	315	(1)
Client-Centric Consistency Models	316	(10)
Eventual Consistency	317	(2)
Monotonic Reads	319	(1)
Monotonic Writes	320	(2)
Read Your Writes	322	(1)
Writes Follow Reads	323	(1)
Implementation	324	(2)
Distribution Protocols	326	(11)
Replica Placement	326	(4)
Update Propagation	330	(4)
Epidemic Protocols	334	(3)
Consistency Protocols	337	(9)
Primary-Based Protocols	337	(4)
Replicated-Write Protocols	341	(4)
Cache-Coherence Protocols	345	(1)
Examples	346	(11)
Orca	347	(5)
Causally-Consistent Lazy Replication	352	(5)
Summary	357	(4)
Fault Tolerance	361	(52)
Introduction to Fault Tolerance	362	(6)
Basic Concepts	362	(2)
Failure Models	364	(2)
Failure Masking by Redundancy	366	(2)
Process Resilience	368	(7)
Design Issues	368	(2)
Failure Masking and Replication	370	(1)
Agreement in Faulty Systems	371	(4)
Reliable Client-Server Communication	375	(6)
Point-to-Point Communication	375	(1)
RPC Semantics in the Presence of Failures	375	(6)
Reliable Group Communication	381	(12)
Basic Reliable-Multicasting Schemes	381	(2)
Scalability in Reliable Multicasting	383	(3)
Atomic Multicast	386	(7)
Distributed Commit	393	(8)
Two-Phase Commit	393	(6)
Three-Phase Commit	399	(2)
Recovery	401	(9)
Introduction	401	(3)
Checkpointing	404	(3)
Message Logging	407	(3)
Summary	410	(3)
Security	413	(80)
Introduction to Security	414	(18)
Security Threats, Policies, and Mechanisms	414	(6)
Design Issues	420	(5)
Cryptography	425	(7)
Secure Channels	432	(15)
Authentication	433	(8)
Message Integrity and Confidentiality	441	(3)
Secure Group Communication	444	(3)
Access Control	447	(13)
General Issues in Access Control	447	(4)
Firewalls	451	(2)
Secure Mobile Code	453	(7)
Security Management	460	(12)
Key Management	461	(4)
Secure Group Management	465	(1)
Authorization Management	466	(6)
Example: Kerberos	472	(1)
Example: Sesame	473	(5)
SESAME Components	474	(3)
Privilege Attribute Certificates (PACs)	477	(1)
Example: Electronic Payment Systems	478	(10)
Electronic Payment Systems	478	(2)
Security in Electronic Payment Systems	480	(4)
Example Protocols	484	(4)
Summary	488	(5)
Distributed Object-Based Systems	493	(82)
Corba	494	(31)
Overview of CORBA	495	(6)
Communication	501	(7)
Processes	508	(6)
Naming	514	(4)
Synchronization	518	(1)
Caching and Replication	518	(2)
Fault Tolerance	520	(2)
Security	522	(3)
Distributed Com	525	(20)
Overview of DCOM	526	(5)
Communication	531	(3)
Processes	534	(3)
Naming	537	(4)
Synchronization	541	(1)
Replication	541	(1)
Fault Tolerance	541	(1)
Security	542	(3)
Globe	545	(20)
Overview of Globe	545	(8)
Communication	553	(1)
Processes	554	(3)
Naming	557	(2)
Synchronization	559	(1)
Replication	560	(3)
Fault Tolerance	563	(1)
Security	563	(2)
Comparison of Corba, Dcom, and Globe	565	(7)
Philosophy	566	(1)
Communication	567	(1)
Processes	567	(1)
Naming	568	(1)
Synchronization	569	(1)
Caching and Replication	569	(1)
Fault Tolerance	570	(1)
Security	570	(2)
Summary	572	(3)
Distributed File Systems	575	(72)
Sun Network File System	576	(28)
Overview of NFS	576	(5)
Communication	581	(1)
Processes	582	(1)
Naming	583	(7)
Synchronization	590	(4)
Caching and Replication	594	(3)
Fault Tolerance	597	(3)
Security	600	(4)
The Coda File System	604	(19)
Overview of Coda	604	(2)
Communication	606	(2)
Processes	608	(1)
Naming	609	(1)
Synchronization	610	(5)
Caching and Replication	615	(3)
Fault Tolerance	618	(2)
Security	620	(3)
Other Distributed File Systems	623	(15)
Plan 9: Resources Unified to Files	623	(6)
XFS: Serverless File System	629	(6)
SFS: Scalable Security	635	(3)
Comparison of Distributed File Systems	638	(5)
Philosophy	638	(1)
Communication	639	(1)
Processes	639	(1)
Naming	640	(1)
Synchronization	641	(1)
Caching and Replication	641	(1)
Fault Tolerance	642	(1)
Security	642	(1)
Summary	643	(4)
Distributed Document-Based Systems	647	(52)
The World Wide Web	648	(30)
Overview of WWW	648	(9)
Communication	657	(5)
Processes	662	(6)
Naming	668	(3)
Synchronization	671	(1)
Caching and Replication	672	(4)
Fault Tolerance	676	(1)
Security	676	(2)
Lotus Notes	678	(13)
Overview of Lotus Notes	678	(2)
Communication	680	(1)
Processes	681	(2)
Naming	683	(2)
Synchronization	685	(1)
Replication	685	(3)
Fault Tolerance	688	(1)
Security	688	(3)
Comparison of WWW and Lotus Notes	691	(4)
Summary	695	(4)
Distributed Coordination-Based Systems	699	(38)
Introduction to Coordination Models	700	(2)
Tib/Rendezvous	702	(14)
Overview of TIB/Rendezvous	702	(2)
Communication	704	(4)
Processes	708	(1)
Naming	709	(1)
Synchronization	710	(2)
Caching and Replication	712	(1)
Fault Tolerance	713	(2)
Security	715	(1)
Jini	716	(14)
Overview of Jini	717	(2)
Communication	719	(2)
Processes	721	(3)
Naming	724	(3)
Synchronization	727	(1)
Caching and Replication	728	(1)
Fault Tolerance	728	(1)
Security	729	(1)
Comparison of TIB/Rendezvous and Jini	730	(3)
Summary	733	(4)
Reading List and Bibliography	737	(48)
Suggestions for Further Reading	737	(12)
Introduction and General Works	737	(2)
Communication	739	(1)
Processes	739	(1)
Naming	740	(1)
Synchronization	741	(1)
Consistency and Replication	742	(1)
Fault Tolerance	743	(1)
Security	744	(1)
Distributed Object-Based Systems	745	(1)
Distributed File Systems	746	(1)
Distributed Document-Based Systems	747	(1)
Distributed Coordination-Based Systems	748	(1)
Alphabetical Bibliography	749	(36)
Index	785

Excerpts

This book started out as a revision ofDistributed Operating Systems,but it was soon apparent that so much had changed since 1995, that a mere revision would not do the job. A whole new book was needed. Accordingly, this new book has a new title:Distributed Systems: Principles and Paradigms.This change reflects a shift in emphasis. While we still look at some operating systems issues, the book now addresses distributed systems in a broader sense as well. For example, the World Wide Web, which is arguably the biggest distributed system ever built, was not even mentioned in the original book because it is not an operating system. In this book it rates almost an entire chapter. The book is structured in two parts: principles and paradigms. The first chapter is a general introduction to the subject. Then come seven chapters on individual principles we consider most important: communication, processes, naming, synchronization, consistency and replication, fault tolerance, and security. Actual distributed systems are usually organized around some paradigm, such as "everything is a file." The next four chapters each deal with a different paradigm and describe several key systems that use that paradigm. The paradigms covered are object-based systems, distributed file systems, document-based systems, and coordination-based systems. The last chapter contains an annotated bibliography, which can be used as a starting point for additional study of this subject, and the list of works cited in this book. The book is intended for a senior-level or a graduate course in computer science. Consequently, it has a website with PowerPoint sheets and the figures used in the book in various formats. The website can be located starting from www.prenhall.com/tanenbaum and clicking on the title of this book. A manual with solutions to the exercises is available to professors using the book in a course. They should contact their Prentice Hall representative for a copy. Of course, the book is also well-suited for individuals outside of a university setting wishing to learn more about this important topic. A number of people have contributed to this book in various ways. We would especially like to thank Arno Bakker, Gerco Ballintijn, Brent Callaghan, Scott Cannon, Sandra Cornelissen, Mike Dahlin, Mark Derbyshire, Guy Eddory, Amr el Abbadi, Vincent Freely Chandana Gamage, Ben Gras, Bob Gray, Michael van Hartskamp, Philip Homburg, Jeroen Ketema, Andrew Kitchen, Ladislav Kohout, Bob Kutter, Jussipekka Leiwo, Leah McTaggert, Eli Messenger, Donald Miller, Shivakant Mishra, Jim Mooney, Matt Mutka, Rob Pike, Krithi Ramamritham, Shmuel Rotenstreich, Sol Shatz, Gurdip Singly Aditya Shivram, Vladimir Sukonnik, Boleslaw Szymanski, Laurent Therond, and Leendert van Doom for reading parts of the manuscript and offering useful comments. Finally, we would like to thank our families. Suzanne has been through this process an even dozen times now. Not once has she said: "Enough is enough" although surely the thought has occurred to her. Thank you. Barbara and Marvin now have a much better idea of what professors do for a living and know the difference between a good textbook and a bad one. They are now an inspiration to me to try to produce more good ones than bad ones (AST). Marielle knew what she was in for when I told her I was in the book-writing business again. She has been supportive from the start, noticing also that there was more fun and less frustration for me than the last time ("Are you writing chapters only once this time?"). Having Elke on your lap at 6 o'clock in the morning while writing is not such a good idea, but it kept me focused on correctly setting priorities. In that respect, Max did a wonderful job as well, but being older than Elke, he also knew when it was better to play with someone else. They are great kids (MvS).