Santoro N. Design and Analysis of Distributed Algorithms

John Wiley, 2007. — 604.The computational universe surrounding us is clearly quite different from that envisioned by the designers of the large mainframes of half a century ago. Even the subsequent most futuristic visions of supercomputing and of parallel machines, which have guided the research drive and absorbed the research funding for so many years, are far from today’s computational realities.
These realities are characterized by the presence of communities of networked entities communicating with each other, cooperating toward common tasks or the solution of a shared problem, and acting autonomously and spontaneously. They are distributed computing environments.
It has been from the field of network and of communication engineering that the seeds of what we now experience have germinated. The growth in understanding has occurred when computer scientists (initially very few) started to become aware of and study the computational issues connected with these new network-centric realities. The internet, the web, and the grids are just examples of these environments. Whether over wired or wireless media, whether by static or nomadic code, computing in such environments is inherently decentralized and distributed. To compute in distributed environments one must understand the basic principles, the fundamental properties, the available tools, and the inherent limitations.
This book focuses on the algorithmics of distributed computing; that is, on how to solve problems and perform tasks efficiently in a distributed computing environment. Because of the multiplicity and variety of distributed systems and networked environments and their widespread differences, this book does not focus on any single one of them. Rather it describes and employs a distributed computing universe that captures the nature and basic structure of those systems (e.g., distributed operating systems, data communication networks, distributed databases, transaction processing systems, etc.), allowing us to discard or ignore the system-specific details while identifying the general principles and techniques.
This universe consists of a finite collection of computational entities communicating by means of messages in order to achieve a common goal; for example, to perform a given task, to compute the solution to a problem, to satisfy a request either from the user (i.e., outside the environment) or from other entities. Although each entity is capable of performing computations, it is the collection of all these entities that together will solve the problem or ensure that the task is performed.
In this universe, to solve a problem, we must discover and design a distributed algorithm or protocol for those entities: A set of rules that specify what each entity has to do. The collective but autonomous execution of those rules, possibly without any supervision or synchronization, must enable the entities to perform the desired task to solve the problem.
In the design process, we must ensure both correctness (i.e., the protocol we design indeed solves the problem) and efficiency (i.e., the protocol we design has a “small” cost).
As the title says, this book is on the Design and Analysis of Distributed Algorithms. Its goal is to enable the reader to learn how to design protocols to solve problems in a distributed computing environment, not by listing the results but rather by teaching how they can be obtained. In addition to the “how” and “why” (necessary for problem solution, from basic building blocks to complex protocol design), it focuses on providing the analytical tools and skills necessary for complexity evaluation of designs.
There are several levels of use of the book. The book is primarily a senior under graduate and graduate textbook; it contains the material for two one-term courses or alternatively a full-year course on Distributed Algorithms and Protocols, Distributed Computing, Network Computing, or Special Topics in Algorithms. It covers the “distributed part” of a graduate course on Parallel and Distributed Computing (the chapters on Distributed Data, Routing, and Synchronous Computing, in particular), and it is the theoretical companion book for a course in Distributed Systems, Advanced Operating Systems, or Distributed Data Processing.
The book is written for the students from the students’ point of view, and it follows closely a well define teaching path and method (the “course”) developed over the years; both the path and the method become apparent while reading and using the book. It also provides a self-contained, self-directed guide for system-protocol designers and for communication software and engineers and developers, as well as for researchers wanting to enter or just interested in the area; it enables hands-on, head-on, and in-depth acquisition of the material. In addition, it is a serious sourcebook and reference book for investigators in distributed computing and related areas. Unlike the other available textbooks on these subjects, the book is based on a very simple fully reactive computational model. From a learning point of view, this makes the explanations clearer and readers’ comprehension easier. From a teaching point of view, this approach provides the instructor with a natural way to present otherwise difficult material and to guide the students through, step by step. The instructors themselves, if not already familiar-with the material or with the approach, can achieve proficiency quickly and easily.
All protocols in the textbook as well as those designed by the students as part of the exercises are immediately programmable. Hence, the subtleties of actual implementation can be employed to enhance the understanding of the theoretical design principles; furthermore, experimental analysis (e.g., performance evaluation and comparison) can be easily and usefully integrated in the coursework expanding the analytical tools.
The book is written so to require no prerequisites other than standard undergraduate knowledge of operating systems and of algorithms. Clearly, concurrent or prior knowledge of communication networks, distributed operating systems or distributed transaction systems would help the reader to ground the material of this course into some practical application context; however, none is necessary.Distributed Computing Environments
Basic Problems And Protocols
Election
Message Routing and Shortest Paths
Distributed Set Operations
Synchronous Computations
Computing in Presence of Faults
Detecting Stable Properties
Continuous Computations