分布式处理入门：基础与应用

2星需积分: 10 149 浏览量更新于2024-07-28 收藏 3.43MB PDF 举报

"分布式处理入门教程，涵盖消息传递系统、内在约束、计算模型、基础算法与基本技术" 在《分布式处理入门》这本书中，作者Barbosa深入浅出地介绍了分布式计算的关键概念和技术。这本书分为两大部分，即基础理论和进阶应用，旨在帮助读者理解和掌握分布式算法的设计与实现。 **Part 1 - 基础理论** 1. **Chapter 1 - 消息传递系统** 分布式系统中的核心通信机制是消息传递，它涉及节点间的通信协议和数据交换。这一章可能涵盖了同步与异步消息传递模型、错误检测与恢复机制、以及消息传递协议如MPI（Message Passing Interface）等。 2. **Chapter 2 - 内在约束** 这一章探讨了分布式系统面临的各种限制，如网络延迟、资源有限性、节点故障等。理解这些约束对于设计健壮的分布式算法至关重要。 3. **Chapter 3 - 计算模型** 包括了不同的分布式计算模型，如MapReduce、Actor模型和Paxos一致性算法等，这些都是理解分布式系统行为的基础。 4. **Chapter 4 - 基本算法** 这部分可能涵盖了分布式环境下的经典算法，如选举算法、分布式一致性算法（如Gossip协议、Paxos或Raft）、分布式排序和分布式搜索等。 5. **Chapter 5 - 基本技术** 提到了分布式系统中的关键技术，如分布式数据库、负载均衡、容错机制、并行计算策略等，这些都是构建高效分布式系统的基础。 **Part 2 - 进阶与应用** 6. **Chapter 6 - 稳定属性** 在这一章中，可能会讨论分布式系统中的稳定性概念，包括状态的一致性、系统在面临变化时的稳定性和如何保证服务的可用性。 7. **Chapter 7 - 图算法** 分布式图算法在解决分布式问题中扮演着重要角色，如最短路径计算、分布式社交网络分析等，这部分可能包含这些算法的分布式实现。 8. **Chapter 8 - 资源调度** 介绍了如何在分布式环境中有效地分配和管理资源，如CPU、内存和网络带宽，以优化系统性能。通过阅读这本书，读者可以系统地学习分布式计算的原理，理解分布式算法的设计思路，并掌握在实际应用中解决问题的技巧。这本书对于软件开发者、系统架构师和对分布式计算感兴趣的学者来说是一份宝贵的参考资料。

been completely received (all that is saved is then the wait time on outgoing packet queues).

It is possible, however, to pipeline the transmission of the message so that only very small

portions have to be stored at the intermediate processors, as in the third flow-control

strategy we describe next.

The last strategy we describe for flow control employs packet blocking (as opposed to

packet buffering or link reservation) as one of its basic paradigms. The resulting mechanism

is known as wormhole routing (a misleading denomination, because it really is a flow-control

strategy), and contrasting with the previous two strategies, the basic unit on which flow

control is performed is not a packet but a flit (flow-control digit). A flit contains no routing

information, so every flit in a packet must follow the leading flit, where the routing information

is kept when the packet is subdivided. With wormhole routing, the inherent latency of store-

and-forward flow control due to the constraint that a packet can only be sent forward after it

has been received in its entirety is eliminated. All that needs to be stored is a flit, significantly

smaller than a packet, so the transmission of the packet is pipelined, as portions of it may be

flowing on different links and portions may be stored. When the leading flit needs access to a

resource (memory space or link) that it cannot have immediately, the entire packet is

blocked and only proceeds when that flit can advance. As with the previous two

mechanisms, deadlock can also arise in wormhole routing. The strategy for dealing with this

is to break the directed cycles in the routing function (thereby possibly making pairs of

processors inaccessible to each other), then add virtual links to the already existing links in

the network, and then finally fix the routing function by the use of the virtual links. Directed

cycles in the routing function then become "spirals", and deadlocks can no longer occur.

(Virtual links are in the literature referred to as virtual channels, but channels will have in this

book a different connotation—cf.

Section 1.4.)

In the case of multiprocessors, the use of communication processors employing wormhole

routing for flow control tends to be such that the time to transport a message between nodes

directly connected by a link in G

is only marginally smaller than the time spent when no

direct connection exists. In such circumstances, G

can often be regarded as being a

complete graph (cf.

Section 2.1, where we discuss details of the example given in Section

1.6.2).

To finalize this section, we mention that yet another flow-control strategy has been proposed

that can be regarded as a hybrid strategy combining store-and-forward flow control and

wormhole routing. It is called virtual cut-through, and is characterized by pipelining the

transmission of packets as in wormhole routing, and by requiring entire packets to be stored

when an outgoing link cannot be immediately used, as in store-and-forward. Virtual cut-

through can then be regarded as a variation of wormhole routing in which the pipelining in

packet transmission is retained but packet blocking is replaced with packet buffering.

1.4 Reactive message-passing programs

So far in this chapter we have discussed how message-passing systems relate to

distributed-memory systems, and have outlined some important characteristics at the

processor level that allow tasks to communicate with one another by message passing over

point-to-point communication channels. Our goal in this section is to introduce, in the form of

a template algorithm, our understanding of what a distributed algorithm is and of how it

should be described. This template and some of the notation associated with it will in

Section

2.1 evolve into the more compact notation that we use throughout the book.

We represent a distributed algorithm by the connected directed graph G

= (N

), where

the node set N

is a set of tasks and the set of directed edges D

is a set of unidirectional

communication channels. (A connected directed graph is a directed graph whose underlying

undirected graph is connected.) For a task t, we let In

⊆ D

denote the set of edges directed

towards t and Out

⊆ D

the set of edges directed away from t. Channels in In

are those on

which t receives messages and channels in Out

are those on which t sends messages. We

also let n

= |In

|, that is, n

denotes the number of channels on which t may receive

messages.

A task t is a reactive (or message-driven) entity, in the sense that normally it only performs

computation (including the sending of messages to other tasks) as a response to the receipt

of a message from another task. An exception to this rule is that at least one task must be

allowed to send messages out "spontaneously" (i.e., not as a response to a message

receipt) to other tasks at the beginning of its execution, inasmuch as otherwise the assumed

message-driven character of the tasks would imply that every task would idle indefinitely and

no computation would take place at all. Also, a task may initially perform computation for

initialization purposes.

Algorithm Task_t, given next, describes the overall behavior of a generic task t. Although in

this algorithm we (for ease of notation) let tasks compute and then send messages out, no

such precedence is in fact needed, as computing and sending messages out may constitute

intermingled portions of a task's actions.

Algorithm Task_t:

Do some computation;

send one message on each channel of a (possibly empty) subset of

Out

;

repeat

receive message on c

∈ In

and B

→

Do some computation;

send one message on each channel of a (possibly empty)

subset of Out

or…

receive message on c

∈ In

and B

→

Do some computation;

send one message on each channel of a (possibly empty)

subset of Out

until global termination is known to t.

There are many important observations to be made in connection with Algorithm Task_t. The

first important observation is in connection with how the computation begins and ends for

task t. As we remarked earlier, task t begins by doing some computation and by sending

messages to none or more of the tasks to which it is connected in G

by an edge directed

away from it (messages are sent by means of the operation send). Then t iterates until a

global termination condition is known to it, at which time its computation ends. At each

iteration, t does some computation and may send messages. The issue of global termination

will be thoroughly discussed in

Section 6.2 in a generic setting, and before that in various

other chapters it will come up in more particular contexts. For now it suffices to notice that t

acquires the information that it may terminate its local computation by means of messages

received during its iterations. If designed correctly, what this information signals to t is that

no message will ever reach it again, and then it may exit the repeat…until loop.

The second important observation is on the construction of the repeat…until loop and on

the semantics associated with it. Each iteration of this loop contains n

guarded commands

grouped together by or connectives. A guarded command is usually denoted by

guard → command,

where, in our present context, guard is a condition of the form

receive message on c

∈ In

and B

for some Boolean condition B

, where 1 ≤ k ≤ n

. The receive appearing in the description

of the guard is an operation for a task to receive messages. The guard is said to be ready

when there is a message available for immediate reception on channel c

and furthermore

the condition B

is true. This condition may depend on the message that is available for

reception, so that a guard may be ready or not, for the same channel, depending on what is

at the channel to be received. The overall semantics of the repeat…until loop is then the

following. At each iteration, execute the command of exactly one guarded command whose

guard is ready. If no guard is ready, then the task is suspended until one is. If more than one

guard is ready, then one of them is selected arbitrarily. As the reader will verify by our many

distributed algorithm examples along the book, this possibility of nondeterministically

selecting guarded commands for execution provides great design flexibility.

Our final important remark in connection with Algorithm Task_t is on the semantics

associated with the receive and send operations. Although as we have remarked the use of

a receive in a guard is to be interpreted as an indication that a message is available for

immediate receipt by the task on the channel specified, when used in other contexts this

operation in general has a blocking nature. A blocking receive has the effect of suspending

the task until a message arrives on the channel specified, unless a message is already there

to be received, in which case the reception takes place and the task resumes its execution

immediately.

The send operation too has a semantics of its own, and in general may be blocking or

nonblocking. If it is blocking, then the task is suspended until the message can be delivered

directly to the receiving task, unless the receiving task happens to be already suspended for

message reception on the corresponding channel when the send is executed. A blocking

send and a blocking receive constitute what is known as task rendez-vous, which is a

mechanism for task synchronization. If the send operation has a nonblocking nature, then

the task transmits the message and immediately resumes its execution. This nonblocking

version of send requires buffering for the messages that have been sent but not yet

received, that is, messages that are in transit on the channel. Blocking and nonblocking

send operations are also sometimes referred to as synchronous and asynchronous,

respectively, to emphasize the synchronizing effect they have in the former case. We refrain

from using this terminology, however, because in this book the words synchronous and

asynchronous will have other meanings throughout (cf.

Section 2.1). When used, as in

Algorithm Task-t, to transmit messages to more than one task, the send operation is

assumed to be able to do all such transmissions in parallel.

The relation of blocking and nonblocking send operations with message buffering

requirements raises important questions related to the design of distributed algorithms. If, on

the one hand, a blocking send requires no message buffering (as the message is passed

directly between the synchronized tasks), on the other hand a nonblocking send requires the

ability of a channel to buffer an unbounded number of messages. The former scenario poses

great difficulties to the program designer, as communication deadlocks occur with great ease

when the programming is done with the use of blocking operations only. For this reason,

however unreal the requirement of infinitely many buffers may seem, it is customary to start

the design of a distributed algorithm by assuming nonblocking operations, and then at a later

stage performing changes to yield a program that makes use of the operations provided by

the language at hand, possibly of a blocking nature or of a nature that lies somewhere in

between the two extremes of blocking and nonblocking send operations.

The use of nonblocking send operations does in general allow the correctness of distributed

algorithms to be shown more easily, as well as their properties. We then henceforth assume

that, in Algorithm Task_t, send operations have a nonblocking nature. Because Algorithm

Task_t is a template for all the algorithms appearing in the book, the assumption of

nonblocking send operations holds throughout. Another important aspect affecting the

design of distributed algorithms is whether the channels in D

deliver messages in the FIFO

order or not. Although as we remarked in

Section 1.3 this property may at times be essential,

we make no assumptions now, and leave its treatment to be done on a case-by-case basis.

We do make the point, however, that in the guards of Algorithm Task_t at most one

message can be available for immediate reception on a FIFO channel, even if other

messages have already arrived on that same channel (the available message is the one to

have arrived first and not yet received). If the channel is not FIFO, then any message that

has arrived can be regarded as being available for immediate reception.

1.5 Handling infinite-capacity channels

As we saw in Section 1.4, the blocking or nonblocking nature of the send operations is

closely related to the channels ability to buffer messages. Specifically, blocking operations

require no buffering at all, while nonblocking operations may require an infinite amount of

buffers. Between the two extremes, we say that a channel has capacity k ≥ 0 if the number

of messages it can buffer before either a message is received by the receiving task or the

sending task is suspended upon attempting a transmission is k. The case of k = 0

corresponds to a blocking send, and the case in which k → ∞ corresponds to a nonblocking

send.

Although Algorithm Task_t of

Section 1.4 is written under the assumption of infinite-capacity

channels, such an assumption is unreasonable, and must be dealt with somewhere along

the programming process. This is in general achieved along two main steps. First, for each

channel c a nonnegative integer b(c) must be determined that reflects the number of buffers

actually needed by channel c. This number must be selected carefully, as an improper

choice may introduce communication deadlocks in the program. Such a deadlock is

represented by a directed cycle of tasks, all of which are suspended to send a message on

the channel on the cycle, which cannot be done because all channels have been assigned

insufficient storage space. Secondly, once the b(c)'s have been determined, Algorithm

Task_t must be changed so that it now employs send operations that can deal with the new

channel capacities. Depending on the programming language at hand, this can be achieved

rather easily. For example, if the programming language offers channels with zero capacity,

then each channel c may be replaced with a serial arrangement of b(c) relay tasks

alternating with b(c) + 1 zero-capacity channels. Each relay task has one input channel and

one output channel, and has the sole function of sending on its output channel whatever it

receives on its input channel. It has, in addition, a storage capacity of exactly one message,

so the entire arrangement can be viewed as a b(c)-capacity channel.

The real problem is of course to determine values for the b(c)'s in such a way that no new

deadlock is introduced in the distributed algorithm (put more optimistically, the task is to

ensure the deadlock-freedom of an originally deadlock-free program). In the remainder of

this section, we describe solutions to this problem which are based on the availability of a

bound r(c), provided for each channel c, on the number of messages that may require

buffering in c when c has infinite capacity. This number r(c) is the largest number of

messages that will ever be in transit on c when the receiving task of c is itself attempting a

message transmission, so the messages in transit have to be buffered.

Although determining the r(c)'s can be very simple for some distributed algorithms (cf.

Sections 5.4 and 8.5), for many others such bounds are either unknown, or known

imprecisely, or simply do not exist. In such cases, the value of r(c) should be set to a "large"

positive integer M for all channels c whose bounds cannot be determined precisely. Just how

large this M has to be, and what the limitations of this approach are, we discuss later in this

section.

If the value of r(c) is known precisely for all c ∈ D

, then obviously the strategy of assigning

b(c) = r(c) buffers to every channel c guarantees the introduction of no additional deadlock,

as every message ever to be in transit when its destination is engaged in a message

transmission will be buffered (there may be more messages in transit, but only when their

destination is not engaged in a message transmission, and will therefore be ready for

reception within a finite amount of time). The interesting question here is, however, whether

it can still be guaranteed that no new deadlock will be introduced if b(c) < r(c) for some

channels c. This would be an important strategy to deal with the cases in which r(c) = M for

some c ∈ D

, and to allow (potentially) substantial space savings in the process of buffer

assignment.

Theorem 1.1 given next concerns this issue.

Theorem 1.1

Suppose that the distributed algorithm given by Algorithm Task_t for all t

∈

is deadlock-

free. Suppose in addition that G

contains no directed cycle on which every channel c is

such that either b(c) < r(c) or r(c) = M. Then the distributed algorithm obtained by replacing

each infinite-capacity channel c with a b(c)-capacity channel is deadlock-free.

Proof: A necessary condition for a deadlock to arise is that a directed cycle exists in G

whose tasks are all suspended on an attempt to send messages on the channels on that

cycle. By the hypotheses, however, every directed cycle in G

has at least one channel c for

which b(c) = r(c) < M, so at least the tasks t that have such channels in Out

are never

indefinitely suspended upon attempting to send messages on them.

The converse of

Theorem 1.1 is also often true, but not in general. Specifically, there may be

cases in which r(c) = M for all the channels c of a directed cycle, and yet the resulting

剩余317页未读，继续阅读

springworm

粉丝: 0
资源: 4

分布式处理入门：基础与应用

An Introduction to Neural Networks - Patrick van der Smagt.pdf

Introduction to Deep Learning: From Logical Calculus to Artificial Intelligence

A Concise Introduction to Languages and Machines.pdf

.A.Concise.And.Practical.Introduction.To.Programming.Algorithms.In.Java

Distributed.Computing.with.Python.178588969

Distributed.Source.Coding.Theory.and.Practice.epub

An Introduction to YOLOv8: The Evolutionary Journey of Convolutional Neural Networks

Introduction to Common Data Science Tools in Jupyter Notebook

Introduction to Frequency Domain Analysis: Concepts and Basic Principles

MATLAB Paths and Big Data Processing: Managing Big Data ...and Saying Goodbye to Slow Data Processing

最新资源