Locality and Checkability in Wait-free ComputingReportar como inadecuado

Locality and Checkability in Wait-free Computing - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications 2 Instituto de Matematicas México 3 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : This paper studies several notions of locality that are inherent to the specification of distributed tasks and independent of the computing environment, and investigates the ability of a shared memory wait-free system to solve tasks satisfying various forms of locality. First, we define a task to be projection-closed if every partial output πt for a full input s is also a valid output for the partial input πs and prove that projection-closed tasks are precisely those tasks that are wait-free checkable. Our second main contribution is dealing with a stronger notion of lo- cality of topological nature. A task T = I, O, ∆ is said to be locality- preserving if and only if O is a covering complex of I, that is, each simplex s of I is mapped by ∆ to a set of simplexes of O each isomorphic to s. This topological property yields obstacles for wait-free solvability different in nature from the classical agreement impossibility results. On the other hand, locality-preserving tasks are projection-closed and therefore always wait-free checkable. We provide a classification of locality-preserving tasks in term of their computational power, by establishing a correspondence between locality-preserving tasks and subgroups of the edgepath group of a complex. Using this correspondence, we prove the existence of hierarchies of locality-preserving tasks, each one containing a universal task induced by the universal covering complex, and at the bottom the trivial identity task.

Keywords : distributed verification local computing wait-free decision task

Autor: Pierre Fraigniaud - Sergio Rajsbaum - Corentin Travers -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados