分布式算法：直观解析第一版

需积分: 9 16 浏览量更新于2024-07-18 收藏 1.92MB PDF 举报

"分布式算法：直观方法" 是一本由 Wan Fokkink 所著的教材，专注于通过实例和练习来介绍分布式算法，适合学生和研究人员学习，避免了过于复杂的数学模型。分布式算法是计算机科学中的核心领域，特别是在大规模、高并发的系统设计中至关重要。本书"分布式算法：直观方法"旨在提供一种易于理解的途径，让读者能够掌握这一领域的基本概念和关键算法。作者 Wan Fokkink 的目标是使读者通过实际示例和丰富的练习，而不是深入的数学推导，来理解和应用分布式算法。分布式算法处理的是多台计算机在网络环境下的协作问题，这些计算机通过通信网络相互连接，共同完成一项任务。书中可能涵盖了诸如一致性算法（如 Paxos 和 Raft）、分布式计算模型（如同步与异步模型）、分布式数据管理和一致性（例如，读写一致性、ACID 属性和 CAP 定理）、故障检测与恢复机制、领导者选举、负载均衡算法以及分布式调度策略等内容。例如，Paxos 算法是一种解决分布式系统中一致性问题的经典算法，它确保在存在网络延迟、消息丢失或重复的情况下，节点间能就单一决策达成一致。Raft 算法则是在 Paxos 基础上设计的，更加简单易懂，适用于教学和实践。而分布式数据管理中的读写一致性问题，比如强一致性、最终一致性等，是分布式数据库和缓存系统中的重要议题。书中可能会通过实际场景，如分布式文件系统、云计算平台或分布式数据库，来展示这些算法的应用。读者会学习如何设计和分析算法性能，以及如何在面对网络延迟、节点故障和动态网络拓扑变化时，保持系统的稳定和高效。此外，书中很可能包含大量习题和案例研究，帮助读者巩固所学，并提升解决实际问题的能力。这些习题可能涉及设计简单的分布式算法，或者对已有的算法进行分析和改进。通过这些实践性的环节，读者能够逐步建立对分布式算法的深入理解和实践经验。 "分布式算法：直观方法"是一本面向初学者和专业人士的优秀教材，它将复杂的分布式算法概念转化为易于理解的示例，是深入学习和掌握分布式计算领域不可或缺的参考资料。

Message Passing

Preliminaries

In a message-passing framework, a distributed system consists of a ﬁnite network (or

graph) of N processes (or nodes). Each process in the network carries a unique ID.

The processes in the network are connected by channels (or edges), through which

they can send messages to each other. There is at most one channel from one process

to another, and a process does not have a channel to itself. Sometimes a process may

want to communicate a message to itself, but for this clearly no channel is needed.

We use E and D to denote the number of channels and the diameter of the network,

respectively.

A process can record its own state and the messages it sends and receives; pro-

cesses do not share memory or a global clock. Each process knows only its (direct)

neighbors in the network. The topology of the network is assumed to be strongly

connected, meaning that there is a path from each process to every other process.

Communication in the network is asynchronous, meaning that sending and re-

ceiving a message are distinct events at the sending and receiving process, respec-

tively. The delay of a message in a channel is arbitrary but ﬁnite. We assume that

communication protocols are being used to avoid that messages are garbled, dupli-

cated or lost. Channels need not be FIFO, meaning that messages can overtake each

other.

In a directed network, messages can travel only in one direction through a chan-

nel, while in an undirected network, messages can travel either way. Undirected

channels are required for distributed algorithms that use an acknowledgment scheme.

Acyclic networks will always be undirected, since otherwise the network would not

be strongly connected. A network topology is called complete if there is an undi-

rected channel between each pair of different processes.

A spanning tree of an undirected network is a connected, acyclic graph that con-

sists of all the nodes and a subset of the edges in the network. The edges of the

spanning tree are called tree edges, and all other edges are called frond edges. Often

the edges in a spanning tree are given a direction to obtain a sink tree, in which all

paths lead to the same node, called the root; each directed edge leads from a child to

its parent.

8 2 Preliminaries

At some places we will deviate from the assumptions mentioned so far and move

to, for instance, synchronous communication in which sending and receiving of the

same message form one atomic event, or unreliable processes or channels, or FIFO

channels, or processes without a unique ID, or processes with a probabilistic instead

of a deterministic speciﬁcation. This will then be stated explicitly.

Transition systems

A distributed algorithm, which runs on a distributed system, provides (usually deter-

ministic) speciﬁcations for the individual processes. The global state of a distributed

algorithm, called a conﬁguration, evolves by means of transitions. The overall be-

havior of a distributed system is captured by a transition system, which consists of:

• a set C of conﬁgurations,

• a binary transition relation → on C, and

• a set I⊆Cof initial conﬁgurations.

A conﬁguration γ is terminal if it has no outgoing transition: γ → δ for no δ ∈C.

An execution of the distributed system is a sequence γ

··· of conﬁgurations

that is either inﬁnite or ends in a terminal conﬁguration γ

, such that:

• γ

∈I, and

• γ

→ γ

i+1

for all i ≥ 0 (and in case of a ﬁnite execution, i<k).

A conﬁguration δ is reachable if there is a γ

∈Iand a sequence γ

···γ

with

→ γ

i+1

for all 0 ≤ i<kand γ

= δ.

States and events

The conﬁguration of a distributed system is composed from the local states of its

processes and the messages in transit. A transition between conﬁgurations of a dis-

tributed system is associated to an event (or, in case of synchronous communication,

two events) at one (or two) of its processes. A process can perform internal, send and

receive events. An internal event inﬂuences only the state at the process where the

event is performed. Typical internal events are reading or writing to a local variable.

Assignment of a new value to a variable is written as ←; for example, n ← n +1

means that the value of variable n, representing a natural number, is increased by

one. A send event in principle gives rise to a corresponding receive event of the same

message at another process. It is assumed that two different events never happen at

the same moment in real time (with the exception of synchronous communication).

A process is an initiator if its ﬁrst event is an internal or send event; that is, an

initiator can start performing events without input from another process. An algo-

rithm is centralized if there is exactly one initiator. A decentralized algorithm can

have multiple initiators.

2 Preliminaries 9

Assertions

An assertion is a predicate on the conﬁgurations of an algorithm. That is, in each

conﬁguration the assertion is either true or false.

An assertion is a safety property if it is true in each reachable conﬁguration of

the algorithm. A safety property typically expresses that something bad will never

happen. Examples of safety properties are:

– You can always count on me.

– The cost of living never decreases.

– If an interrupt occurs, a message will be printed within one second.

In particular, the last example states that never no message gets printed within one

second after an interrupt.

In general, it is undecidable whether a given conﬁguration is reachable. An as-

sertion P is an invariant if:

• P (γ) for all γ ∈I, and

• if γ → δ and P(γ), then P (δ).

In other words, an invariant is true in all initial conﬁgurations and is preserved by all

transitions. Clearly, each invariant is a safety property. Note that checking whether

an assertion is an invariant does not involve reachability.

An assertion is a liveness property if executions, from some point on, contain a

conﬁguration in which the assertion holds. A liveness property typically expresses

that something good will eventually happen. Examples of liveness properties are:

– What goes up, must come down.

– The program always eventually terminates.

– If an interrupt occurs, a message will be printed.

A liveness property sometimes holds only with respect to the so-called fair ex-

ecutions of an algorithm. For example, consider a simple algorithm that consists of

ﬂipping a coin until the result is tails. Since there is an inﬁnite execution in which the

outcome of every coin ﬂip is heads, the liveness property that eventually the outcome

will be tails does not hold. However, if the coin is fair, this inﬁnite execution has zero

chance of happening; inﬁnitely often we ﬂip the coin with the possible outcome tails,

but never is the outcome tails. We say that an execution is fair if every event that can

happen in inﬁnitely many conﬁgurations in the execution is performed inﬁnitely of-

ten during the execution. The inﬁnite execution in which the outcome of every coin

ﬂip is heads is not fair. Note that any ﬁnite execution is by default fair.

Causal order

In each conﬁguration of an asynchronous distributed system, events that can occur

at different processes are independent, meaning that they can happen in any order.

The causal order ≺ is a binary relation on events in an execution such that a ≺ b

if and only if a must happen before b. That is, the events in the execution cannot be

reordered in such a way that a happens after b. The causal order for an execution is

the smallest relation such that:

剩余241页未读，继续阅读

ystweid

粉丝: 1
资源: 2

分布式算法：直观解析第一版

Distributed Algorithms

Introduce to Algorithms, A Creative Approach

Introduction to Distributed Algorithms

ModuleNotFoundError: No module named 'torch.distributed.algorithms.join

No module named 'torch.distributed.algorithms'

ModuleNotFoundError: No module named 'torch.distributed.algorithms.join'

引用Distributed adaptive coverage control algorithm for mobile sensor networks

TimeDistributed is not defined

torch.distributed.

多智能体强化学习推荐书籍

最新资源