Locality and checkability in wait-free computing

Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers

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

New Challenges and Algebraic Topology

Maurice Herlihy

Maurice Herlihy discusses his view on the challenges distributed computing faces in the future, describes some of his work on programming abstractions and how he uses algebraic topology as a tool to reason about distributed protocols.

Guest: Maurice Herlihy
Host: Zvi Lotker and Yvonne-Anne Pignolet