**Abstract:**

This paper studies notions of locality that are inherent to the specification of a

distributed task and independent of the computing environment, in a shared

memory wait-free system.

A task T =(I,O,D) is checkable if there exists a wait-free distributed algorithm that, given s in I and t in O, determines whether t in D(s), i.e., if t is a valid output for s according to

the specification D of T. Determining whether a projection-closed task is

wait-free solvable remains undecidable, demonstrating the richness of this

class. A locality property called projection-closed is identified, that completely characterizes tasks that are wait-free checkable.

A stronger notion of locality considers tasks where the outputs look identically to the inputs at every vertex (input value of a process). A task T =(I,O,D) is said to be locality-preserving} if O is a covering complex of I. 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. A classification of locality-preserving

tasks in term of their relative computational power is provided.

A correspondence between locality-preserving tasks and subgroups of the edgepath

group of an input complex shows the existence of hierarchies of locality-preserving tasks, each one containing at the top the universal task (induced by the universal covering complex), and at the bottom the trivial identity task.

Guest: Pierre Fraigniaud

Host: Merav Parter

Podcast: Play in new window
| Download