BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Concurrency as an Iterated Affine Task Kuznetsov, Petr


We consider models of computations expressed via sets of runs bounding the concurrency level: the number of processes that can be concurrently active. The model of k-concurrency is equivalent to the read-write shared-memory systems equipped with k-set-agreement objects. We show that every such model can be characterized by an affine task: a simple combinatorial structure (a simplicial complex), defined as a subset of simplices in the second degree of the standard chromatic subdivision. Our result implies the first combinatorial representation of models equipped with abstractions other than read-write registers.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International