Trabajo de tesis maestria

Rachid Guerraoui, Lu´ Rodrigues ıs

Introduction to Distributed Algorithms
(Preliminary Draft)
November 22, 2004

Springer-Verlag
Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona Budapest

To whom it might concern.

*DRAFT*

V

(22/11/2004)

Preface

This manuscript aims at offering an introductory description of distributed programming abstractions and ofthe algorithms that are used to implement them in different distributed environments. The reader is provided with an insight on important problems in distributed computing, knowledge about the main algorithmic techniques that can be used to solve these problems, and examples of how to apply these techniques when building distributed applications.

Content
In modern computing, a program usuallyexecutes on several processes: in this context, a process is an abstraction that may represent a computer, a processor within a computer, or simply a specific thread of execution within a processor. The fundamental problem in devising such distributed programs usually consists in having the processes cooperate on some common task. Of course, traditional centralized algorithmic issues, on each processindividually, still need to be dealt with. The added difficulty here is about achieving a robust form of cooperation, despite failures or disconnections of some of the processes, inherent to most distributed environments. Had no notion of cooperation been required, a distributed program would simply consist of a set of detached centralized programs, each running on a specific process, and littlebenefit could be obtained from the availability of several machines in a distributed environment. It was the need for cooperation that revealed many of the fascinating problems addressed by this manuscript, problems that would have otherwise remained undiscovered. The manuscript, not only exposes the reader to these problems but also presents ways to solve them in different contexts. Not surprisingly,distributed programming can be significantly simplified if the difficulty of robust cooperation is encapsulated within specific abstractions. By encapsulating all the tricky algorithmic issues, such distributed programming abstractions bridge the gap between network communication layers, usually frugal in terms of reliability guarantees, and distributed application layers, usually demanding in terms ofreliability.

Preface

Preface

The manuscript presents various distributed programming abstractions and describes algorithms that implement these abstractions. In a sense, we give the distributed application programmer a library of abstraction interface specifications, and the distributed system builder a library of algorithms that implement the specifications. A significant amount of thepreparation time of this manuscript was devoted to preparing the exercises and working out their solutions. We strongly encourage the reader to work out the exercises. We believe that no reasonable understanding can be achieved in a passive way. This is especially true in the field of distributed computing where the underlying anthropomorphism may provide fast but wrong intuitions. Many exercises arerather easy and can be discussed within an undergraduate teaching classroom. Some exercises are more difficult and need more time. These can be given as homeworks. The manuscript comes with a companion set of running examples implemented in the Java programming language, using the Appia protocol composition framework. These examples can be used by students to get a better understanding of theimplementation details not covered in the high-level description of the algorithms. Instructors can use these protocol layers as a basis for practical exercises, by suggesting students to perform optimizations on the code provided, to implement variations of the algorithms for different system models, or to design applications that make use of these abstractions.

Presentation
The manuscript is...