Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: The Topology of Shared-memory Adversaries
event speaker icon
Maurice Herlihy, Brown University
event date icon
Wednesday, 24.11.2010, 12:20
event location icon
Room 337-8 Taub Bld.
Failure patterns in modern parallel and distributed system 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.

Joint with Sergio Rajsbaum
[Back to the index of events]