I took part to the writing of one chapter of the book Systèmes répartis en action, edited by Fabrice Kordon, Laurent Pautet and Laure Petrucci. This book, in French, is a survey of current technologies in distributed computing, that is computations using from a few processors up to very large scale computing grids. The goal was to make this survey through the study of several examples, linking real applications to a larger view of the field of distributed computing, including the formal methods and algorithms typical of the domain.

The Desktop Grid offers solutions to overcome several challenges and to answer increasingly needs of scientific computing. This technology consists mainly in exploiting PC resources, geographically dispersed, to treat time consuming applications and/or important storage capacity requiring applications. However, as resources number increases, the need for scalability, self-organisation, dynamic reconfiguration, decentralization and performance becomes more and more essential. Since such properties are exhibited by P2P systems, the convergence of grid computing and P2P computing seems natural. In this context, this paper evaluates the scalability and performance of P2P tools for registering and discovering services (Publish/Subscribe systems). Three protocols are used in this purpose: Bonjour, Avahi and Pastry. We have studied the behaviour of these protocols related to two criteria: the elapsed time for registrations services and the needed time to discover new services. Our aim is to analyse these results in order to choose the most adequate protocol for creating a decentralized middleware for Desktop Grid.

The problem of compact tables is to maximise the overlap when building a word that is to include permutations of every given words (all the words being the same length). This problem is shown to be NP-complete in the general case, and some specific restrictions are studied.

Summary: The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a partitioning step. For uniformly related processors (processors speeds are related by a constant factor), we ...

In this article, co-written with Véronique Terrier for the Latin 2002 conference, we investigate how increasing the dimension of the array can help to draw signals on cellular automata. We show the existence of a gap of constructible signals in any dimension. We exhibit two cellular automata in dimension 2 to show that increasing the dimension allows to reduce the number of states required for some constructions.

Kolmogorov complexity theory gives a definition of randomness for words on a finite alphabet. The notions involved led to the description of a subclass of computable machines: the prefix computable machines, whose domain is a prefix code (no word in the domain is prefix of another one).