Speculating Seriously in Distributed Computing

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.

Disciplines : Algorithmes,Recursive functions
Mots-clés : algorithmique,complexité,systèmes distribués
Type de document : image en mouvement
Type de ressource : lecture
Niveau : master,doctorat
Auteurs ou éditeurs : INRIA (Institut national de recherche en informatique et automatique),UNS,CNRS - Centre National de la Recherche Scientifique,Région PACA,INRIA (Institut national de recherche en informatique et automatique),Rachid GUERRAOUI