Events

Campus de l’Ecole polytechnique, Palaiseau
Bld Alan Turing, Salle Grace HopperAsynchrony from Synchrony
Eli Gafni, UCLA CSIn the past adversaries that reduce the computational power of a system as they become more powerful, were investigated in the context of asynchronous shared-memory. The adversary’s power was characterized by the set of processors it can crash. Here we investigate more refined adversaries: Adversaries that purge messages in a synchronous message-passing system. In particular, we consider a synchronous message passing system over a complete network where in each round all processors send to all. The computation power is modulated by an adversary that in each round, independently of previous rounds, can delete a subset of the messages. Deleting a message on a link in one direction does not necessarily imply the removal of the message in the other direction. The weakest adversary has no power, it may delete no message, while an adversary that can remove any set of messages is the strongest. Clearly the model power to solve tasks is inverse proportional to the adversary power. In the former model all tasks are solvable, while in the latter no none-trivial task is solvable.We characterize the set of adversaries that are weak enough allowing the model to solve all read-write wait-free solvable tasks, and at the same time strong enough to preclude solution of any task which is not read-write wait-free solvable. A remarkable side-benefit of this characterization is a simple, as simple as can be, derivation of the Herlihy Shavit condition that equates wait-free solvability with a subdivided-simplex. We show how each step in the computation inductively takes a subdivided-simplex and further subdivides it in the simplest way possible, making the characterization of read-write wait-free widely accessible.