Introduction to Distributed Algorithms
Gerard Tel
@ Cambridge University Press 1994, 2000
ref:
Distributed Algorithms for Message-Passing Systems
1 Introduction: Distributed Systems
1.1 What is a Distributed System?
1.1.1 Motivation
The characteristics of a distributed system
(1) Information exchange.
(2) Resource sharing.
(3) Increased reliability through replication.
(4) Increased performance through parallelization
(5) Simplification of design through specialization.
1.1.2 Computer Networks
the focus:
(1) Reliability parameters.
(2) Communication time.
(3) Homogeneity.
(4) Mutual trust.
1.1.3 Wide-area Networks
algorithmical problems
(1) The reliability of point-to-point data exchange (Chapter 3).
(2) Selection of communication paths (Chapter 4).
(3) Congestion control.
(4) Deadlock prevention (Chapter 5).
(5) Security.
1.1.4 Local-area Networks
Algorithmical problems.
(1) Broadcasting and synchronization (Chapter 6).
(2) Election (Chapter 7).
(3) Termination detection (Chapter 8).
(4) Resource allocation.
(5) Mutual exclusion.
(6) Deadlock detection and resolution.
(7) Distributed file maintenance.
1.1.5 Multiprocessor Computers
problems:
(1) Implementation of a message-passing system.
(2) Implementation of a virtual shared memory.
(3) Load balancing
(4) Robustness against undetectable failures (Part Three).
1.1.6 Cooperating Processes
model:
(1) Atomicity of memory operations.
(2) The producer-consumer problem.
(3) Garbage collection.
solutions in operating systems:
(1) Semaphores.
(2) Monitors.
(3) Pipes.
(4) Message passing
1.2 Architecture and Languages
1.2.1 Architecture
The modules are called layers or levels in the context of network implementation; see Figure 1.4
1.2.2 The OSI Reference Model
1.2.3 The OSI Model in Local-area Networks: IEEE Standards
1.2.4 Language Support
Parallelism.
Communication.
Non-determinism.
1.3 Distributed Algorithms
1.3.1 Distributed versus Centralized Algorithms
three essential respects
(1) Lack of knowledge of global state.
(2) Lack of a global time-frame.
(3) Non-determinism.
1.3.2 An Example: Single-message Communication
1.3.3 Research Field
1.4 . Outline of the Book
three objectives in mind.
Part One Protocols
2 The Model
2.1 Transition Systems and Algorithms
transition system
communicate style: shared variables or by message passing
-- Messages style: synchronous or asynchronous
2.1.1 Transition Systems
configurations -- global states
2.1.2 Systems with Asynchronous Message Passing
transition and "configuration --- global
event and state -- are used for attributes of processes
M be a set of possible messages
: correspond to state transitions related with internal, send, and receive events, respectively.
2.1.3 Systems with Synchronous Message Passing
2.1.4 Fairness
2.2 Proving Properties of Transition Systems
safety requirements and liveness requirements
-- A safety requirement: a certain property must hold for each execution of the system in
every
configuration reached in that execution.
-- A liveness requirement: a certain property must hold for each execution of the system in
some
configuration reached in that execution.
assertional verification methods
--
An assertion
: a unary relation on the set of configurations, that is, a predicate that is true for a subset of the configurations and false for others.
2.2.1 Safety Properties
A safety property of an algorithm: a property of the form "Assertion P is true in each configuration of each exeCution of the algorithm".
2.2.2 Liveness Properties
A liveness property of an algorithm: a property of the form "Assertion P is true in some configuration of each execution of the algorithm".
Let S be a transition system and P a predicate.
-- Define
term
as the predicate that is true in all terminal configurations and false in all non-terminal
configurations.
2.3 Causal Order of Events and Logical Clocks
2.3.1 Independence and Dependence of Events
2.3.2 Equivalence of Executions: Computations
Chapter 3 Communication Protocol
3.1 The balanced sliding-window protocol
滑动窗口协议:
滑动窗口的重要特性
只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于 1时，就是双工的停止等待协议。
滑动窗口协议（Sliding Window Protocol）工作原理：
- 发送的信息帧都有一个序号，从0到某个最大值，0 ~ 2n - 1，一般用n个二进制位表示；
- 发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小 = 上界 - 下界，大小可变；
- 发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1；
- 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧；
- 接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。
Alternating-bit protocol: 交替位协议
