Advertisement
Published in:
2013 | OriginalPaper | Chapter
3. An Algorithmic Framework to Compute Global Functions on a Process Graph
Author : Michel Raynal
Published in: Distributed Algorithms for Message-Passing Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
This chapter is devoted to distributed graph algorithms that compute a function or a predicate whose inputs are disseminated at the processes of a network. The function (or the predicate) is global because the output at each process depends on the inputs at all the processes. It follows that the processes have to communicate in order to compute their results.
A general algorithmic framework is presented which allows global functions to be computed. This distributed framework is (a) symmetric in the sense that all processes obey the same rules of behavior, and (b) does not require the processes to exchange more information than needed. The computation of shortest distances and the determination of a cut vertex in a graph are used to illustrate the framework. The framework is then improved to allow for a reduction of the size and the number of messages that are exchanged. Finally, the chapter analyzes the particular case of regular networks (networks in which all the processes have the same number of neighbors).