This improvised workshop uses the happy occasion of having around Sergio Rajsbaum and Nayuta Yanagisawa to have a series of discussions on the use of combinatorial topology in distributed computing.

Program

Abstracts

Sergio Rajsbaum: Tasks vs objects

I will describe some of the work I have done with Armando Castaneda and Michel Raynal on interval-linearizability, a notion we introduced in DISC 2015 and extended in NETYS 2016 to specify objects more general than the usual sequentially specified objects. While tasks explicitly state what might happen when a set of processes run concurrently, objects only specify what happens when processes access the object sequentially. Remarkably, these are two approaches that have largely remained independent since the early days of the theory of distributed computing. I will describe the bridges we establish between these two paradigms, and our discussions about what is a distributed object, and what it means to solve it.

Nayuta Yanagisawa: t-Resilient Computability in Anonymous Shared-Memory Model

We investigate the fault-tolerant capability of distributed systems in the anonymous and t-resilient setting. In the anonymous model, a distributed system consists of a fixed number of processes with no identifiers executing an identical program. We assume that processes are prone to crash failures and communicate via multi-writer/muti-reader shared registers. We propose an anonymous t-resilient protocol for (t+1)-set agreement problem. We also give a topological characterization of colorless tasks that are t-resilient solvable in the anonymous model. The characterization implies that the anonymity does not reduce the computational power of the asynchronous shared-memory model as long as colorless tasks are concerned.

Thibault Rieutord: Affine tasks for distributed computing models

We show how (complex and non-compact) models of distributed computing can be expressed as iterations of (simple and compact) affine tasks, combinatorial structures defined as sub-complexes of the standard chromatic subdivision. We consider generic adversarial shared-memory models, including k-obstruction freedom, k-concurrency, t-resilience, etc.