Advertisement
Published in:
2013 | OriginalPaper | Chapter
6. Nature of Distributed Computations and the Concept of a Global State
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
A sequential execution can be represented by the sequence (trace) of consecutive local states it has produced, or, given its initial state, by the sequence of statements that have been executed. Hence, a question that comes naturally to mind is the following one: How do we model a distributed execution?
This chapter answers first this question. To that end, it gives basic definitions, and presents three ways to model a distributed execution, namely, a partial order on a set of events, a partial order on a set of local states, and a lattice of global states. While these three types of models are equivalent, it appears that each one is more appropriate than the others to analyze and understand specific features of distributed executions.
The chapter then focuses on a fundamental notion of distributed computing, namely, the notion of a global state. The chapter analyzes global states and presents several distributed algorithms, which compute on the fly global states of a distributed application. These algorithms are observation algorithms (they have to observe an execution without modifying its behavior). It is shown that the best that can be done is the computation of a global state in which a distributed execution has passed or could have passed. This means that no process can know if the distributed execution has passed or has not passed through the global state which is returned as a result. This noteworthy feature illustrates the relativistic nature of the observation of distributed computations. Despite this relativistic feature, the computation of such global states allows distributed computing problems to be solved (such as the detection of stable properties).
Both the terms “global state” and “snapshot” are used with the same meaning in the literature. They have to be considered as synonyms. This chapter uses the term global state.