分布式算法导论（英文版）

　　21世纪初的5至10年是我国国民经济和社会发展的重要时期，也是信息产业快速发展的关键时期。在我国加入WTO后的今天，培养一支适应国际化竞争的一流IT人才队伍是我国高等教育的重要任务之一。信息科学和技术方面人才的优劣与多寡，是我国面对国际竞争时成败的关键因素。分布式算法20多年来一直是倍受关注的主流方向。本书第二版不仅给出了算法的最新进展，还深入探讨了与之相关的理论知识。这本教材适合本科高年级和研究生使用，同时，本书所覆盖的广？群蜕疃纫彩质屎洗邮率导使ぷ鞯墓こ淌脱芯咳嗽辈慰肌Ｊ橹兄氐闾致哿说愣缘阆⒋菽Ｐ蜕系乃惴ǎ舶扑慊ㄐ磐绲氖迪炙惴āＦ渌氐闾致鄣哪谌莅ǚ植际接τ玫目刂扑惴ǎㄈ绮ㄋ惴ā⒐悴ニ惴ā⒀【偎惴ā⒅罩辜觳馑惴ā⒛涿绲乃婊惴ā⒖煺账惴ā⑺浪觳馑惴ā⑼较低乘惴ǖ龋股婕傲死梅植际剿惴ㄊ迪秩荽砑扑恪５诙嫘略龅墓赜诜较蚋泻凸收霞觳馄鞯哪谌荻即砹说苯褡钚录际醴⒄顾剑谡庑┓较蛏洗邮卵芯康娜嗽碧峁┝撕芎玫陌镏？

　　Gerard Tel，在荷兰Utrecht大学获得博士学位，现任Utrecht大学计算与信息科学学院助理教授，主要研究方向是与C有关的计算，包括复杂性、压缩、密码学、通信以及编码等。出版过多本得到业界广泛认可的著作。

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