Wait-Free Computability for General Tasks
Abstract
Although many tasks of interest are colorless, there are “inherently colored” tasks that cannot be defined without taking process names into account. Some have wait-free read-write protocols, and some do not. This chapter gives a characterization of wait-free read-write solvability for general tasks. We will see that general tasks are harder to analyze than colorless tasks. Allowing tasks to depend on process names seems like a minor change, but it will have sweeping consequences.
Keywords
Cauchy sequence; Lebesgue number; Chromatic subdivision; Deformation retraction; Hourglass task; Hyperplane; Link-connected; Mesh; Open cover; Safe agreement
Although many tasks of interest are colorless, ...
Get Distributed Computing Through Combinatorial Topology now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
