分布式算法导论（英文版） (2008 年度畅销榜NO.3614 )

分布式算法20多年来一直是倍受关注的主流方向。本书第二版不仅给出了算法的最新进展，还深入探讨了与之相关的理论知识。这本教材适合本科高年级和研究生使用，同时，本书所覆盖的广度和深度也十分适合从事实际工作的工程师和研究人员参考。书中重点讨论了点对点消息传递模型上的算法，也包括计算机通信网络的实现算法。其他重点讨论的内容包括分布式应用的控制算法(如波算法、广播算法、选举算法、终止检测算法、匿名网络的随机算法、快照算法、死锁检测算法、同步系统算法等)，还涉及了利用分布式算法实现容错计算。第二版新增的关于方向感和故障检测器的内容都代表了当今最新技术发展水平，为在这些方向上从事研究的人员提供了很好的帮助。\r\n
\r\n

1 Introduction: Distributed Systems \r\n\r\n 1.1 What is a Distributed System? \r\n\r\n 1.2 Architecture and Languages \r\n\r\n 1.3 Distributed Algorithms \r\n\r\n 1.4 Outline of the Book \r\n\r\n Part One: Protocols \r\n\r\n 2 The Model \r\n\r\n 2.1 Transition Systems and Algorithms \r\n\r\n 2.2 Proving Properties of Transition Systems \r\n\r\n 2.3 Causal Order of Events and Logical Clocks \r\n\r\n 2.4 Additional Assumptions, Complexity \r\n\r\n Exercises to Chapter 2 \r\n\r\n 3 Communication Protocols \r\n\r\n 3.1 The Balanced Sliding-window Protocol \r\n\r\n 3.2 A Timer-based Protocol \r\n\r\n Exercises to Chapter 3 \r\n\r\n 4 Routing Algorithms \r\n\r\n 4.1 Destination-based Routing \r\n\r\n 4.2 The AU-pairs Shortest-path Problem \r\n\r\n 4.3 The Netchange Algorithm \r\n\r\n 4.4 Routing with Compact Routing Tables \r\n\r\n 4.5 Hierarchical Routing \r\n\r\n Exercises to Chapter 4 \r\n\r\n 5 Deadlock-free Packet Switching \r\n\r\n 5.1 Introduction \r\n\r\n 5.2 Structured Solutions \r\n\r\n 5.3 Unstructured Solutions \r\n\r\n 5.4 Further Issues \r\n\r\n Exercises to Chapter 5 \r\n\r\n Part Two: Fundamental Algorithms \r\n\r\n 6 Wave and Traversed Algorithms \r\n\r\n 6.1 Definition and Use of Wave Algorithms \r\n\r\n 6.2 A Collection of Wave Algorithms \r\n\r\n 6.3 Traversal Algorithms \r\n\r\n 6.4 Time Complexity: Depth-first Search \r\n\r\n 6.5 Remaining Issues \r\n\r\n Exercises to Chapter 6 \r\n\r\n 7 Election Algorithms \r\n\r\n 7.1 Introduction \r\n\r\n 7.2 Ring Networks \r\n\r\n 7.3 Arbitrary Networks \r\n\r\n 7.4 The Korach-Kutten-Moran Algorithm \r\n\r\n Exercises to Chapter 7 \r\n\r\n 8 Termination Detection \r\n\r\n 8.1 Preliminaries \r\n\r\n 8.2 Computation Trees and Forests \r\n\r\n 8.3 Wave-based Solutions \r\n\r\n 8.4 Other Solutions \r\n\r\n Exercises to Chapter 8 \r\n\r\n 9 Anonymous Networks \r\n\r\n 9.1 Preliminaries \r\n\r\n 9.2 Deterministic Algorithms \r\n\r\n 9.3 A Probabilistic Election,Algorithm \r\n\r\n 9.4 Computing the Network Size \r\n\r\n Exercises to Chapter 9 \r\n\r\n 10 Snapshots \r\n\r\n 10.1 Preliminaries \r\n\r\n 10.2 Two Snapshot Algorithms \r\n\r\n 10.3 Using Snapshot Algorithms \r\n\r\n 10.4 Application: Deadlock Detection \r\n\r\n Exercises to Chapter 10 \r\n\r\n 11 Sense of Direction and Orientation \r\n\r\n 11.1 Introduction and Definitions. \r\n\r\n 11.2 Election in Rings and Chordal Rings \r\n\r\n 11.3 Computing in Hypercubes \r\n\r\n 11.4 Complexity-related Issues \r\n\r\n 11.5 Conclusions and Open Questions \r\n\r\n Exercises to Chapter 11 \r\n\r\n 12 Synchrony in Networks \r\n\r\n 12.1 Preliminaries \r\n\r\n 12.2 Election in Synchronous Networks \r\n\r\n 12.3 Synchronizer Algorithms \r\n\r\n 12.4 Application: Breadth-first Search \r\n\r\n 12.5 The Archimedean Assumption \r\n\r\n Exercises to Chapter 12 \r\n\r\n Part Three: Fault Tolerance \r\n\r\n 13 Fault Tolerance in Distributed Systems \r\n\r\n 13.1 Reasons for Using Fault-tolerant Algorithms \r\n\r\n 13.2 Robust Algorithms \r\n\r\n 13.3 Stabilizing Algorithms \r\n\r\n 14 Fault Tolerance in Asynchronous Systems \r\n\r\n 14.1 Impossibility of Consensus \r\n\r\n 14.2 Initially Dead Processes \r\n\r\n 14.3 Deterministically Achievable Cases \r\n\r\n 14.4 Probabilistic Consensus Algorithms \r\n\r\n 14.5 Weak Termination \r\n\r\n Exercises to Chapter 14 \r\n\r\n 15 Fault Tolerance in Synchronous Systems \r\n\r\n 15.1 Synchronous Decision Protocols \r\n\r\n 15.2 Authenticating Protocols \r\n\r\n 15.3 Clock Synchronization \r\n\r\n Exercises to Chapter 15 \r\n\r\n 16 Failure Detection \r\n\r\n 16.1 Model and Definitions \r\n\r\n 16.2 Solving Consensus with a Weakly Accurate Detector \r\n\r\n 16.3 Eventually Weakly Accurate Detectors \r\n\r\n 16.4 Implementation of Failure Detectors \r\n\r\n Exercises to Chapter 16 \r\n\r\n 17 Stabilization \r\n\r\n 17.1 Introduction \r\n\r\n 17.2 Graph Algorithms \r\n\r\n 17.3 Methodology for Stabilization \r\n\r\n Exercises to Chapter 17 \r\n\r\n Part Four: Appendices \r\n\r\n A Pseudocode Conventions \r\n\r\n B Graphs and Networks \r\n\r\n References \r\n\r\n Index \r\n
\r\n

Distributed systems and distributed information processing have received considerable attention in the past few years, and almost every university offers at least one course on the design of distributed algorithms. There exist a large number of books about principles of distributed systems; see for example Tanenbaum [Tan96] or Sloman and Kramer [SK87], but these concentrate on architectural aspects rather than on algorithms. Since the first edition of this book, other texts on distributed algorithms have been published by Sarbosa [Bar96], Lynch [Lyn96], and Attiya and Welch [AW98].

It has been remarked that algorithms are the backbone of every computer application; therefore a text devoted solely to distributed algorithms seems to be justified. The aim of this book is to present a large body of theory about distributed algorithms, which has been developed over the past twenty years or so. This book can be used as a textbook for a one- or two-semester

course on distributed algorithms; the teacher of a one.semester course may select topics to his own liking.

The book will also provide useful background and reference information for professional engineers and researchers working with distributed systems. Exercises. Each chapter (with the exception of Chapters i and 13) ends with a list of exercises and small projects. The projects usually require the reader to develop a small but non-trivial extension or application of the

material treated in the chapter, and in most cases I do not have a "solution". If the reader succeeds in working out one of these small projects, I would be pleased to have a copy of the result.

A list of answers (sometimes partial) to most of the exercises is avallable for teachers; it can be obtained from the author or by anonymous ftp. Corrections and suggestions. If the reader finds errors or omissions ir this book, please inform the author (preferably by electronic mall). Al: constructive criticism, including suggestions for more exercises, is most wel.come.

Acknowledgements. Draft versions of this book were proofread carefully by the following: Erwin Bakker, Hans Bodlaender, Stefan Dobrev, Petra van Haaften, Ted Herman, Jan van Leeuwen, Patrick Lentfert, Friedemann Mattern, Pascale van der Put, Peter Ruzicka, Martin Rudalics, Anneke

Schoone, and Kaisa Sere. Their comments were very helpful in improving the quality of the manuscript. Also, some students of the fall courses on "Gedistribueerde Algoritmen" at Utrecht University provided me with helpful suggestions. The Department of Computer Science provided the technical support necessary for text processing and printing. Linguistic editing was performed by Susan Parkinson.

Gerard Tel, April 1994/February 2000.

无封面