caa a22 4500 445355085 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00446-011-0146-4 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0146-4 The minimum information about failures for solving non-local tasks in message-passing systems [Elektronische Daten] [Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg] 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. Springer-Verlag, 2011 Distributed tasks nationallicence Local tasks nationallicence Failure detectors nationallicence Set agreement nationallicence Fault-tolerance nationallicence Delporte-Gallet Carole Université Paris-Diderot, Paris, France aut Fauconnier Hugues Université Paris-Diderot, Paris, France aut Toueg Sam University of Toronto, Toronto, ON, Canada aut Distributed Computing Springer-Verlag 24/5(2011-12-01), 255-269 0178-2770 24:5<255 2011 24 446 https://doi.org/10.1007/s00446-011-0146-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0146-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Delporte-Gallet Carole Université Paris-Diderot, Paris, France aut NATIONALLICENCE 700 1- Fauconnier Hugues Université Paris-Diderot, Paris, France aut NATIONALLICENCE 700 1- Toueg Sam University of Toronto, Toronto, ON, Canada aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/5(2011-12-01), 255-269 0178-2770 24:5<255 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer