We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The minimum information about failures for solving non-local tasks in message-passing systems.
- Authors
Delporte-Gallet, Carole; Fauconnier, Hugues; Toueg, Sam
- Abstract
We first define the basic notions of local and non-local tasks for distributed systems. Intuitively, a task is local if, in a system with no failures, each process can compute its output value locally by applying some local function on its own input value (so the output value of each process depends only on the process' own input value, not on the input values of the other processes); a task is nonlocal otherwise. All the interesting distributed tasks, including all those that have been investigated in the literature (e.g., consensus, set agreement, renaming, atomic commit, etc.) are non-local. In this paper we consider non-local tasks and determine the minimum information about failures that is necessary to solve such tasks in message-passing distributed systems. As part of this work, we also introduces weak set agreement-a natural weakening of set agreement-and show that, in some precise sense, it is the weakest nonlocal task in message-passing systems.
- Subjects
FAULT-tolerant computing; COMPUTER system failures; DISTRIBUTED algorithms; DISTRIBUTED computing; FAILURE analysis
- Publication
Distributed Computing, 2011, Vol 24, Issue 5, p255
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-011-0146-4