דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: The Topology of Shared-memory Adversaries
event speaker icon
פרופ' מוריס הרלי (אוניברסיטת בראון)
event date icon
יום רביעי, 24.11.2010, 12:20
event location icon
חדר 337, בניין טאוב למדעי המחשב
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
[בחזרה לאינדקס האירועים]