Abstract:

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 more papers (http://lpdwww.epfl.ch/rachid/).

Date: 2012-Sep-06     Time: 16:00:00     Room: 020

For more information:

• romanop@gsd.inesc-id.pt
• 916793531