Distributed Systems

Revised and updated throughout to take into account significant new developments in distributed computing. Reflects on latest technology and includes new case studies, including real-time distributed systems.

This book collects the lecture notes used at the Advanced Courseon Distributed Systems which has now been held five times--Artic'88 in Tromso, Norway, Fingerlakes '89 in Ithaca, NY, Bologna '90in Italy, Karuizawa '91 in Japan and Lisboa '92 in Portugal. Itsinauguration will be at the sixth advanced course, Seattle '93 inSeattle, WA.

The first edition was based on the lecture notes used at Artic'88 and Fingerlakes '89. Since then, the course has evolved andsteadily improved: coordination between the lecturers haseliminated duplication of material; it has produced agreement onterminology; and the course now reflects a more balanced view ofboth 'theoretical' and 'practical' aspects of research indistributed systems.

As a consequence, the material in this second edition is almostentirely new. Only one chapter, in fact, has survived unscathedfrom the first edition. This book, I believe, has now become acoherent treatment of an increasingly important research area.

DISTRIBUTED SYSTEMS is intended for people in universities andindustry interested in distributed systems. Teachers can usethis book torefresh their knowledge of distributed systems. Graduate students can use it to get acquainted with the field andas a reference to other work. Distributed systems designers andbuilders can use it as a source book when trying to solveproblems they encounter in their work. It can be (and is, bysome of the authors) used in post-graduate distributed systemscourses. It is aimed at graduate students in computer science: the reader should have a good general knowledge of computerorganization, computer networks, and operating systems.

The book can be roughly partitioned into seven parts--anintroduction (Chapters 1-3), a part on theoretical foundations(Chapters 4-8), a part on Communication (Chapters 9-11), a parton file systems and database systems (Chapters 12-14), a singlechapter on kernel support (Chapter 15), a part on real-timesystems (Chapters 16-19), and a part on security (Chapters20-21).

In Chapter 1, Schroeder explains what distinguishesd distributedsystems from other systems, and he discusses properties ofdistributed systems and techniques for achieving them. Then, inChapter 2, Schneider discusses the importance of making modelsofthe behaviour of distributed systems and the failures that needto be masked by them. Chapter 3, by Weihl, introduces aspecification method for concurrent systems and then derivesspecifications for the alternat-bit protocol, mutexes andcondition variables, remote procedure call, and a name service.

The second group of chapters covers theoretical foundations ofdistributed and fault-tolerant algorithms. Chapter 4, byBabaoglu and Marzullo, describes how one can deduce, through theexchange of messages, what the state is of a distributed system. It introduces consistent cuts and snapshots, causality, logicaland vector clocks, and characterizes stable and unstablepredicates. Chapter 5, by Hadzilacos and Toueg, introducesvarious broadcast mechanisms. Using broadcasts, it is possibleto provide to a set of cooperating processes a consistent view ofa distributed computation. Broadcast protocols play an importantrole in the following three chapters. Chapter 6, by Babaoglu andToueg, gives protocols for non-blocking atomic commitment,Chapter 7, by Schneider, describes one well-known technique forturning a deterministic program running on a single computer intoa distributed one running on a set of computers so that itbecomes fault tolerant, and Chapter 8, by Budhiraja, Marzullo,Schneider and Toueg, shows another technique for transforming aprogram into a fault-tolerant one.

In Chapter 9, Mullender discusses practical aspects of protocoldesign for interprocess communication in distributed systems. Attention is given to achieving at-most-once behaviour ofremote-invocation protocols in unreliable networks. Remoteprocedure call is also described in Chapter 9. Lampson appliesthe specification of methods of Chapter 2 to the derivationof aprotocol for connection establishment in Chapter 10. In Chapter11 Rodeheffer and Schroeder examine a particular distributedapplication--building up the routing tables for a high-speedswitch-based local-area network.

Needham discusses issues associated with naming in Chapter 12 andshows that building naming databases for very large systems is afar from trivial. Weihl describes the protocols used forimplementing atomic transactions in distrubed systems subject toprocessor and network failures in Chapter 13. AndSatyanarayanan, in Chapter 14, shows how empirical data about howfile systems are used can be used to advantage in theimplementation of distributed file systems. One file system,Coda, is also described there in detail.

In Chapter 15, Mullender uses the design of the Amoebadistributed system to discuss issues of distributed system kerneldesign and discuss techniques for memory management and processmanagement.

In Chapters 16-19, Kopetz and Verissimo cover the subject ofreal-time systems. Chapter 16 introduces real time and theconcept of dependability. Chapter 17 then covers communicationin real-time systems, while Chapter 18 discusses scheduling ofreal-time processes. Two case studies, MARS and DELTA-4, are thesubject of Chapter 19.

The final part of the book is about security and cryptography. Needham explains how cryptography is used to build secureauthenticated communication channels in Chapter 20. In Chapter21, Lampson unfolds a security architecture for distributedsystems, in which he covers security aspects ranging from securebootstrapping to authenticating a party on the other side of theplanet. 0201624273P04062001