The topology of shared-memory adversaries
Reading group: Guillermo Toyos Marfurt presented "The topology of shared-memory adversaries" (PODC '10) at Amphi 4 the 13/10/2023 at 10h30.
Abstract
Failure patterns in modern parallel and distributed systems are not necessarily uniform. The notion of an adversary scheduler is a natural way to extend the classical wait-free and t-faulty models of computation. A well-established way to characterize an adversary is by its set of cores, where a core is any minimal set of processes that cannot all fail in any execution. We show that the protocol complex associated with an adversary is (c − 2)-connected, where c is the size of the adversary’s smallest core. This implies, among other results, that such an adversary can solve c-set agreement, but not (c − 1)-set agreement. The proofs are combinatorial, relying on a novel application of the Nerve Theorem of modern combinatorial topology
