Peleg D. Distributed Computing. A Locality-Sensitive Approach

Society for Industrial and Applied Mathematics, 2001, -360 p.Distributed computing concerns environments in which many processors, located at different sites, must operate in a noninterfering and cooperative manner. Each of the processors enjoys a certain degree of autonomy: it executes its own protocol on its own private hardware and often has its own independent task to complete. Nevertheless, the processors must still share certain common resources and information, and a certain degree of coordination is necessary in order to ensure the successful completion of their individual tasks.
In the last two decades, we have experienced an unprecedented growth in the area of distributed systems and networks, and distributed computing now encompasses many of the activities occurring in today's computer and telecommunications world. Virtually any large computerized system currently in use is distributed to some extent. The applications of distributed computing range from computer and telecommunication networks to distributed database systems and from large financial and economic systems to industrial control mechanisms. In all of those applications, the need to ensure the smooth, coordinated and noninterfering operation of many remote processors is one of the most challenging tasks faced by the application's designers and operators.
One of the main themes of recent research in distributed network algorithms concerns better understanding of and coping with the issue of locality. Most traditional network algorithms do not take locality into consideration and do not exploit locality in any nontrivial way. Due to the increasing complexity and cost as networks become larger, it becomes significantly harder to use many of those traditional protocols for performing various network control and management tasks. On the other hand, such global knowledge is not always essential, and many seemingly global control tasks can be efficiently achieved while allowing processors to know more about their immediate neighborhood and less about the rest of the world. Moreover, whenever considering a local subtask that only involves vertices located in a small region in the network, one would like the execution of the subtask to involve only sites in or around that region, at a cost proportional to its locality level.
In order to be able to achieve this type of dependency on locality in distributed network algorithms, it is necessary to develop a robust and general methodology for addressing locality in distributed algorithms. The purpose of this book is to provide an overview of such a methodology, termed locality-sensitive distributed computing, whose basic idea is to utilize locality in order to both simplify control structures and algorithms and reduce their costs. This book presents a systematic development of a theory of locality-sensitive distributed network algorithms and describes some of the recent developments in this area.Part I Basics of distributed network algorithms
The distributed network model
Broadcast and convergecast
Downcasts and upcasts
Tree constructions
Synchronizers
Vertex coloring
Maximal independent sets (MIS)
Message routing
Local queries and local resource finding
Part II Locality-preserving representations
Clustered representations: Clusters, covers and partitions
Sparse covers
Sparse partitions
Related graph representations
Skeletal representations: Spanning trees, tree covers and spanners
Sparse spanners for unweighted graphs
Light-weight spanners
Spanners with low average stretch
Proximity-preserving labeling systems
Part III Distributed constructions and applications of LP-representations
A basic algorithm for constructing network partitions
Efficient algorithms for constructing covers
Efficient algorithms for constructing network decompositions
Exploiting topological knowledge: Broadcast revisited
How local are global tasks? MST revisited
Local coordination: Synchronizers and MIS revisited
Hierarchical cluster-based routing
Regional directories: Resource finding revisited
Additional applications in other settings