Apr. 4, 2013
If we are ever to understand what computers can collectively do, we need a new theory of complexity. Recent evolutions, including the cloud and the multicore, are turning computing ubiquitously distributed, rendering the classical complexity theory of centralized computing at best insufficient. A complexity theory for distributed computing has emerged in the last decades, measuring complexity for each specific model of the networked environment, represented by an adversary that may provoke asynchrony, failures, contention, etc.
This one adversary – one result approach led to an exponential proliferation of seemingly unrelated results, none of which captures current practices in the development of distributed applications. Instead, applications rely on speculative algorithms that perform well when the environment behaves nicely and gracefully degrades if the environment is more hostile, considering thereby several adversaries at the same time.
With no underlying theory, the proposed speculative algorithms lack however rigor and there is anecdotal evidence of their fragility. It is moreover usually impossible to predict their behavior or determine whether their limitations are related to fundamental impossibilities or artifacts of specific infrastructures.
The goal of this talk is to discuss a glimmer of a theory of speculative distributed computing.
BIO: Rachid Guerraoui is Professor in Computer Science at EPFL where he directs the Institute of Theoretical Computer Science. He has worked in the past with HP Labs in Palo Alto and MIT. He is interested in distributed computing on which he wrote few books and papers (http://lpdwww.epfl.ch/rachid/).
