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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International