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 (définition), Avahi (définition) and Pastry (définition). 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.
Archives : January 2008
Tuesday 15 January 2008
Friday 11 January 2008
Ce 30 novembre, j’ai été témoin (et j’ai immortalisé) une conjonction rare : les trois Christophe du laboratoire mangeaient ensemble côte à côte.
Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters
Thursday 10 January 2008
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 develop a constant time technique for mastering processor load and execution time in an heterogeneous environment and also a technique to deal with unknown cost functions. For non uniformly related processors, we use a technique based on dynamic programming. Most of the time, the solutions are in (p is the number of processors), independent of the problem size n. Consequently, there is a small overhead regarding the problem we deal with but it is inherently limited by the knowing of time complexity of the portion of code following the partitioning.
Wednesday 9 January 2008
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.
Tuesday 8 January 2008
Suite à un fort gel, suivi de la remise en marche du chauffage au restaurant administratif (pourtant superbement remis à neuf), une canalisation a explosé le 20 décembre...
Tuesday 8 January 2008
My PhD (French thèse de doctorat) was received on the 9th of October, 2000, at École normale supérieure de Lyon. The topic of the PhD was the "notion of prefix in Kolmogorov complexity and computational models", under the direction of Jacques Mazoyer and Bruno Durand.
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).
Beyond the matter of defining randomness for infinite words, this subclass has remarkable properties regarding computability theory. Three different definitions are given and compared. The case of comma free codes is also examined, but it doesn't yield anymore an additively optimal machine.
The notion of prefix also interacts with the computational models. An examination of machines with no blank characters or of finite models with an infinite calculus space (such as the Turing machine, which uses an infinite tape) reveals a strong influence of the prefix notion on computational processes.
Monday 7 January 2008
In this article, written jointly with Enrico Formenti and Bruno Durand, we present a new approach to cellular automata (CA) classification based on algorithmic complexity. We construct a parameter κ which is based only on the transition table of CA and measures the "randomness" of evolutions; κ is better, in a certain sense, than any other parameter recursively definable on CA tables. We investigate the relations between the classical topological approach and ours one. Our parameter is compared with Langton's λ parameter: κ turns out to be theoretically better and also agrees with some practical evidences reported in literature. Finally, we propose a protocol to approximate κ and make experiments on CA dynamical behavior.
Sunday 6 January 2008
We explain the basics of the theory of the Kolmogorov complexity, also known as algorithmic information theory, and underline the main differences between the Kolmogorov complexity and Kolmogorov prefix complexity. Then, we introduce the definition of randomness for either finite or infinite words according to Per Martin-Löf and show that it is equivalent to the notion of uncompressibility defined via Kolmogorov complexity.
Saturday 5 January 2008
Abstract of the article
The issue of testing invertibility of cellular automata has been often discussed. The computation universality of cellular automata has long been positively resolved, and by showing that any cellular automaton could be simulated by an invertible one having a superior dimension, Toffoli proved that invertible cellular automaton of dimension d ≥2 were computation-universal. Kenichi Morita proved that any invertible Turing Machine could be simulated by a one-dimensional invertible cellular automaton, which proved computation-universality of invertible cellular automata. This article shows how to simulate any Turing Machine by an invertible cellular automaton with no loss of time and gives, as a corollary, an easier proof of this result.
Friday 4 January 2008
Cellular automata have very different properties whether their dimension being 1 or 2 from the point of view of computability theory. After having defined a notion of signal, we analyse the intrinsic computational power of the cellular automata in dimension 1 or 2 according to the shape of the signals that can be generated with them.
Thursday 3 January 2008
Tuesday 1 January 2008
- distributed algorithms on heterogeneous computational grids;
- fault tolerance and computation in potentially hostile grids (e.g. desktop grids);
- pervasive computing;
- centralised system administration of heterogeneous machines with similar software (in the range of 50-250 machines).
Tuesday 1 January 2008
As a teacher (about 200 hours of presence in front of the students per year, plus all the extras), I teach in the "Computer science" department of the Technological Institute of Villetaneuse (IUT, an institute dedicated to the professional