Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
1. Basic Definitions and Network Traversal Algorithms
verfasst von : Michel Raynal
Erschienen in: Distributed Algorithms for Message-Passing Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This chapter first introduces basic definitions related to distributed algorithms. Then, considering a distributed system as a graph whose vertices are the processes and whose edges are the communication channels, it presents distributed algorithms for graph traversals, namely, parallel traversal, breadth-first traversal, and depth-first traversal. It also shows how spanning trees or rings can be constructed from these distributed graph traversal algorithms. These trees and rings can, in turn, be used to easily implement broadcast and convergecast algorithms.
As the reader will see, the distributed graph traversal techniques are different from their sequential counterparts in their underlying principles, behaviors, and complexities. This come from the fact that, in a distributed context, the same type of traversal can usually be realized in distinct ways, each with its own tradeoff between its time complexity and message complexity.