Kniha An%20Introduction%20to%20Distributed%20Processing

An Introduction
to Distributed Algorithms
Barbosa C. Valmir
The MIT Press
Cambridge, Massachusetts
London, England
Copyright 1996 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means
(including photocopying, recording, or information storage and retrieval) without permission in writing from the
publisher.
Library of Congress Cataloging-in-Publication Data
Valmir C. Barbosa
An introduction to distributed algorithms / Valmir C. Barbosa.
p. cm.
Includes bibliographical references and index.
ISBN 0-262-02412-8 (hc: alk. paper)
1. Electronic data processing-Distributed processing.2. Computer algorithms.I. Title.
QA76.9.D5B36 1996
005.2-dc20 96-13747
CIP

Dedication
To my children, my wife, and my parents
Table of Contents
Preface
Part 1 - Fundamentals
Chapter 1 - Message-Passing Systems
Chapter 2 - Intrinsic Constraints
Chapter 3 - Models of Computation
Chapter 4 - Basic Algorithms
Chapter 5 - Basic Techniques
Part 2 - Advances and Applications
Chapter 6 - Stable Properties
Chapter 7 - Graph Algorithms
Chapter 8 - Resource Sharing
Chapter 9 - Program Debugging
Chapter 10 - Simulation
Bibliography
Author Index
Subject Index
List of Figures
List of Listings

Preface
This book presents an introduction to some of the main problems, techniques, and
algorithms underlying the programming of distributed-memory systems, such as computer
networks, networks of workstations, and multiprocessors. It is intended mainly as a textbook
for advanced undergraduates or first-year graduate students in computer science and
requires no specific background beyond some familiarity with basic graph theory, although
prior exposure to the main issues in concurrent programming and computer networks may
also be helpful. In addition, researchers and practitioners working on distributed computing
will also find it useful as a general reference on some of the most important issues in the
field.
The material is organized into ten chapters covering a variety of topics, such as models of
distributed computation, information propagation, leader election, distributed snapshots,
network synchronization, self-stability, termination detection, deadlock detection, graph
algorithms, mutual exclusion, program debugging, and simulation. Because I have chosen to
write the book from the broader perspective of distributed-memory systems in general, the
topics that I treat fail to coincide exactly with those normally taught in a more orthodox
course on distributed algorithms. What this amounts to is that I have included topics that
normally would not be touched (as algorithms for maximum flow, program debugging, and
simulation) and, on the other hand, have left some topics out (as agreement in the presence
of faults).
All the algorithms that I discuss in the book are given for a "target" system that is
represented by a connected graph, whose nodes are message-driven entities and whose
edges indicate the possibilities of point-to-point communication. This allows the algorithms to
be presented in a very simple format by specifying, for each node, the actions to be taken to
initiate participating in the algorithm and upon the receipt of a message from one of the
nodes connected to it in the graph. In describing the main ideas and algorithms, I have
sought a balance between intuition and formal rigor, so that most are preceded by a general
intuitive discussion and followed by formal statements regarding correctness, complexity, or
other properties.
The book's ten chapters are grouped into two parts. Part 1 is devoted to the basics in the
field of distributed algorithms, while Part 2 contains more advanced techniques or
applications that build on top of techniques discussed previously.
Part 1 comprises Chapters 1 through 5. Chapters 1 and 2 are introductory chapters,
although in two different ways. While Chapter 1 contains a discussion of various issues
related to message-passing systems that in the end lead to the adoption of the generic
message-driven system I mentioned earlier, Chapter 2 is devoted to a discussion of
constraints that are inherent to distributed-memory systems, chiefly those related to a
system's asynchronism or synchronism, and the anonymity of its constituents. The
remaining three chapters of Part 1 are each dedicated to a group of fundamental ideas and
techniques, as follows. Chapter 3 contains models of computation and complexity measures,
while Chapter 4 contains some fundamental algorithms (for information propagation and
some simple graph problems) and Chapter 5 is devoted to fundamental techniques (as
leader election, distributed snapshots, and network synchronization).
The chapters that constitute Part 2 are Chapters 6 through 10. Chapter 6 brings forth the
subject of stable properties, both from the perspective of selfstability and of stability
detection (for termination and deadlock detection). Chapter 7 contains graph algorithms for
minimum spanning trees and maximum flows. Chapter 8 contains algorithms for resource
sharing under the requirement of mutual exclusion in a variety of circumstances, including
generalizations of the paradigmatic dining philosophers problem. Chapters 9 and 10 are,
respectively, dedicated to the topics of program debugging and simulation. Chapter 9
includes techniques for program re-execution and for breakpoint detection. Chapter 10 deals
with time-stepped simulation, conservative event-driven simulation, and optimistic event-
driven simulation.
Every chapter is complemented by a section with exercises for the reader and another with
bibliographic notes. Of the exercises, many are intended to bring the reader one step further
in the treatment of some topic discussed in the chapter. When this is the case, an indication
is given, during the discussion of the topic, of the exercise that may be pursued to expand
the treatment of that particular topic. I have attempted to collect a fairly comprehensive set of
bibliographic references, and the sections with bibliographic notes are intended to provide
the reader with the source references for the main issues treated in the chapters, as well as
to indicate how to proceed further.
I believe the book is sized reasonably for a one-term course on distributed algorithms.
Shorter syllabi are also possible, though, for example by omitting Chapters 1 and 2 (except
for Sections 1.4 and 2.1), then covering Chapters 3 through 6 completely, and then selecting
as many chapters as one sees fit from Chapters 7 through 10 (the only interdependence that
exists among these chapters is of Section 10.2 upon some of Section 8.3).

Notation
The notation log
k
n is used to indicate (log n)
k
. All of the remaining notation in the book is
standard.

Acknowledgments
This book is based on material I have used to teach at the Federal University of Rio de
Janeiro for a number of years and was prepared during my stay as a visiting scientist at the
International Computer Science Institute in Berkeley. Many people at these two institutions,
including colleagues and students, have been most helpful in a variety of ways, such as
improving my understanding of some of the topics I treat in the book, participating in
research related to some of those topics, reviewing some of the book's chapters, and
helping in the preparation of the manuscript. I am especially thankful to Cláudio Amorim,
Maria Cristina Boeres, Eliseu Chaves, Felipe Cucker, Raul Donangelo, Lúcia Drummond,
Jerry Feldman, Edil Fernandes, Felipe França, Lélio Freitas, Astrid Hellmuth, Hung Huang,
Priscila Lima, Nahri Moreano, Luiz Felipe Perrone, Claudia Portella, Stella Porto, Luis Carlos
Quintela, and Roseli Wedemann.
Finally, I acknowledge the support that I have received along the years from CNPq and
CAPES, Brazil's agencies for research funding.
V.C.B.
Berkeley, California
December 1995

Part 1: Fundamentals
Message-Passing Systems
Intrinsic Constraints
Models of Computation
Basic Algorithms
Basic Techniques
Part Overview
This first part of the book is dedicated to some of the fundamentals in the field of distributed
algorithms. It comprises five chapters, in which motivation, some limitations, models, basic
algorithms, and basic techniques are discussed.
Chapter 1 opens with a discussion of the distributed-memory systems that provide the
motivation for the study of distributed algorithms. These include computer networks,
networks of workstations, and multiprocessors. In this context, we discuss some of the
issues that relate to the study of those systems, such as routing and flow control, message
buffering, and processor allocation. The chapter also contains the description of a generic
template to write distributed algorithms, to be used throughout the book.
Chapter 2 begins with a discussion of full asynchronism and full synchronism in the context
of distributed algorithms. This discussion includes the introduction of the asynchronous and
synchronous models of distributed computation to be used in the remainder of the book, and
the presentation of details on how the template introduced in Chapter 1 unfolds in each of
the two models. We then turn to a discussion of intrinsic limitations in the context of
anonymous systems, followed by a brief discussion of the notions of knowledge in
distributed computations.
The computation models introduced in Chapter 2 (especially the asynchronous model) are in
Chapter 3 expanded to provide a detailed view in terms of events, orders, and global states.
This view is necessary for the proper treatment of timing issues in distributed computations,
and also allows the introduction of the complexity measures to be employed throughout. The
chapter closes with a first discussion (to be resumed later in Chapter 5) of how the
asynchronous and synchronous models relate to each other.
Chapters 4 and 5 open the systematic presentation of distributed algorithms, and of their
properties, that constitutes the remainder of the book. Both chapters are devoted to basic
material. Chapter 4, in particular, contains basic algorithms in the context of information
propagation and of some simple graph problems.
In Chapter 5, three fundamental techniques for the development of distributed algorithms are
introduced. These are the techniques of leader election (presented only for some types of
systems, as the topic is considered again in Part 2, Chapter 7), distributed snapshots, and
network synchronization. The latter two techniques draw heavily on material introduced
earlier in Chapter 3, and constitute some of the essential building blocks to be occasionally
used in later chapters.

Chapter 1: Message-Passing Systems
Overview
The purpose of this chapter is twofold. First we intend to provide an overall picture of various
real-world sources of motivation to study message-passing systems, and in doing so to
provide the reader with a feeling for the several characteristics that most of those systems
share. This is the topic of Section 1.1, in which we seek to bring under a same framework
seemingly disparate systems as multiprocessors, networks of workstations, and computer
networks in the broader sense.
Our second main purpose in this chapter is to provide the reader with a fairly rigorous, if not
always realizable, methodology to approach the development of message-passing
programs. Providing this methodology is a means of demonstrating that the characteristics of
real-world computing systems and the main assumptions of the abstract model we will use
throughout the remainder of the book can be reconciled. This model, to be described timely,
is graph-theoretic in nature and encompasses such apparently unrealistic assumptions as
the existence of infinitely many buffers to hold the messages that flow on the system's
communication channels (thence the reason why reconciling the two extremes must at all be
considered).
This methodology is presented as a collection of interrelated aspects in Sections 1.2 through
1.7. It can also be viewed as a means to abstract our thinking about message-passing
systems from various of the peculiarities of such systems in the real world by concentrating
on the few aspects that they all share and which constitute the source of the core difficulties
in the design and analysis of distributed algorithms.
Sections 1.2 and 1.3 are mutually complementary, and address respectively the topics of
communication processors and of routing and flow control in message-passing systems.
Section 1.4 is devoted to the presentation of a template to be used for the development of
message-passing programs. Among other things, it is here that the assumption of infinite-
capacity channels appears. Handling such an assumption in realistic situations is the topic of
Section 1.5. Section 1.6 contains a treatment of various aspects surrounding the question of
processor allocation, and completes the chapter's presentation of methodological issues.
Some remarks on some of the material presented in previous sections comes in Section 1.7.
Exercises and bibliographic notes follow respectively in Sections 1.8 and 1.9.

1.1 Distributed-memory systems
Message passing and distributed memory are two concepts intimately related to each other.
In this section, our aim is to go on a brief tour of various distributed-memory systems and to
demonstrate that in such systems message passing plays a chief role at various levels of
abstraction, necessarily at the processor level but often at higher levels as well.
Distributed-memory systems comprise a collection of processors interconnected in some
fashion by a network of communication links. Depending on the system one is considering,
such a network may consist of point-to-point connections, in which case each
communication link handles the communication traffic between two processors exclusively,
or it may comprise broadcast channels that accommodate the traffic among the processors
in a larger cluster. Processors do not physically share any memory, and then the exchange
of information among them must necessarily be accomplished by message passing over the
network of communication links.
The other relevant abstraction level in this overall panorama is the level of the programs that
run on the distributed-memory systems. One such program can be thought of as comprising
a collection of sequential-code entities, each running on a processor, maybe more than one
per processor. Depending on peculiarities well beyond the intended scope of this book, such
entities have been called tasks, processes, or threads, to name some of the denominations
they have received. Because the latter two forms often acquire context-dependent meanings
(e.g., within a specific operating system or a specific programming language), in this book
we choose to refer to each of those entities as a task, although this denomination too may at
times have controversial connotations.
While at the processor level in a distributed-memory system there is no choice but to rely on
message passing for communication, at the task level there are plenty of options. For
example, tasks that run on the same processor may communicate with each other either
through the explicit use of that processor's memory or by means of message passing in a
very natural way. Tasks that run on different processors also have essentially these two
possibilities. They may communicate by message passing by relying on the message-
passing mechanisms that provide interprocessor communication, or they may employ those
mechanisms to emulate the sharing of memory across processor boundaries. In addition, a
myriad of hybrid approaches can be devised, including for example the use of memory for
communication by tasks that run on the same processor and the use of message passing
among tasks that do not.
Some of the earliest distributed-memory systems to be realized in practice were long-haul
computer networks, i.e., networks interconnecting processors geographically separated by
considerable distances. Although originally employed for remote terminal access and
somewhat later for electronic-mail purposes, such networks progressively grew to
encompass an immense variety of data-communication services, including facilities for
remote file transfer and for maintaining work sessions on remote processors. A complex
hierarchy of protocols is used to provide this variety of services, employing at its various
levels message passing on point-to-point connections. Recent advances in the technology of
these protocols are rapidly leading to fundamental improvements that promise to allow the
coexistence of several different types of traffic in addition to data, as for example voice,
image, and video. The protocols underlying these advances are generally known as
Asynchronous Transfer Mode (ATM) protocols, in a way underlining the aim of providing
satisfactory service for various different traffic demands. ATM connections, although
frequently of the point-to-point type, can for many applications benefit from efficient
broadcast capabilities, as for example in the case of teleconferencing.
Another notorious example of distributed-memory systems comes from the field of parallel
processing, in which an ensemble of interconnected processors (a multiprocessor) is
employed in the solution of a single problem. Application areas in need of such
computational potential are rather abundant, and come from various of the scientific and
engineering fields. The early approaches to the construction of parallel processing systems
concentrated on the design of shared-memory systems, that is, systems in which the
processors share all the memory banks as well as the entire address space. Although this
approach had some success for a limited number of processors, clearly it could not support
any significant growth in that number, because the physical mechanisms used to provide the
sharing of memory cells would soon saturate during the attempt at scaling.
The interest in providing massive parallelism for some applications (i.e., the parallelism of
very large, and scalable, numbers of processors) quickly led to the introduction of
distributed-memory systems built with point-to-point interprocessor connections. These
systems have dominated the scene completely ever since. Multiprocessors of this type were
for many years used with a great variety of programming languages endowed with the
capability of performing message passing as explicitly directed by the programmer. One
problem with this approach to parallel programming is that in many application areas it
appears to be more natural to provide a unique address space to the programmer, so that, in
essence, the parallelization of preexisting sequential programs can be carried out in a more
straightforward fashion. With this aim, distributed-memory multiprocessors have recently
appeared whose message-passing hardware is capable of providing the task level with a
single address space, so that at this level message passing can be done away with. The
message-passing character of the hardware is fundamental, though, as it seems that this is
one of the key issues in providing good scalability properties along with a shared-memory
programming model. To provide this programming model on top of a message-passing
hardware, such multiprocessors have relied on sophisticated cache techniques.
The latest trend in multiprocessor design emerged from a re-consideration of the importance
of message passing at the task level, which appears to provide the most natural
programming model in various situations. Current multiprocessor designers are then
attempting to build, on top of the message-passing hardware, facilities for both message-
passing and scalable shared-memory programming.
As our last example of important classes of distributed-memory systems, we comment on
networks of workstations. These networks share a lot of characteristics with the long-haul
networks we discussed earlier, but unlike those they tend to be concentrated within a much
narrower geographic region, and so frequently employ broadcast connections as their chief
medium for interprocessor communication (point-to-point connections dominate at the task
level, though). Also because of the circumstances that come from the more limited
geographic dispersal, networks of workstations are capable of supporting many services
other than those already available in the long-haul case, as for example the sharing of file
systems. In fact, networks of workstations provide unprecedented computational and storage
power in the form, respectively, of idling processors and unused storage capacity, and
because of the facilitated sharing of resources that they provide they are already beginning
to be looked at as a potential source of inexpensive, massive parallelism.
As it appears from the examples we described in the three classes of distributed- memory
systems we have been discussing (computer networks, multiprocessors, and networks of
workstations), message-passing computations over point-to-point connections constitute
some sort of a pervasive paradigm. Frequently, however, it comes in the company of various
other approaches