**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.

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.

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