Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2011-09-14
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
We motivate and propose a new way of thinking about failure detectors which allows us to define, quite surprisingly, what it means to solve a distributed task \emph{wait-free} \emph{using a failure detector}. In our model, the system is composed of \emph{computation} processes that obtain inputs and are supposed to output in a finite number of steps and \emph{synchronization} processes that are subject to failures and can query a failure detector. We assume that, under the condition that \emph{correct} synchronization processes take sufficiently many steps, they provide the computation processes with enough \emph{advice} to solve the given task wait-free: every computation process outputs in a finite number of its own steps, regardless of the behavior of other computation processes. Every task can thus be characterized by the \emph{weakest} failure detector that allows for solving it, and we show that every such failure detector captures a form of set agreement. We then obtain a complete classification of tasks, including ones that evaded comprehensible characterization so far, such as renaming or weak symmetry breaking.
Delporte-Gallet Carole
Fauconnier Hugues
Gafni Eli
Kuznetsov Petr
No associations
LandOfFree
Wait-Freedom with Advice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Wait-Freedom with Advice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wait-Freedom with Advice will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-569537