Asynchronous Computability Theorems for t-Resilient Systems

A task is a distributed coordination problem where processes start with private inputs, communicate with one another, and then halt with private outputs. A protocol that solves a task is t-resilient if it tolerates halting failures by t or fewer processes. The t-resilient asynchronous computability theorem stated here characterizes the tasks that have t-resilient protocols in a shared-memory model. This result generalizes the prior (wait-free) asynchronous computability theorem of Herlihy and Shavit to a broader class of failure models, and requires introducing several novel concepts.