Publications
The list of all my publications is grouped here by topic (one, sometimes two articles on the very same topic). You will find these publications here, from the most recent to the oldest. If you are looking for a ranking by value, look for the list of book publications, journal publications, the proceedings of various conferences and the research reports (there may be other publications, such as my PhD dissertation). And if you just would like to quote me, I maintain an up-to-date BiBTeX file.
Distributed Computing by example : Security in Computational Grids
Friday 12 December 2008
Study of the NP-completeness of the Compact Table
Saturday 26 April 2008
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.
To show this on a small example (beyond what is in the article), imagine that in a game (like checkers) if blue takes red, on a result of 1, both are eliminated, on 2 or 3, red remains and blue remains in the other cases. If red takes blue, results 1 to 4 make red win and on 5 to 6, blue wins. The compact table in this case would be to keep the table as is in the blue versus red, add +2 if red versus blue, with results 7 and 8 letting red win.
Performance Analysis of Publish/Subscribe Systems
Tuesday 15 January 2008
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.
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.
Signals for Cellular Automata in Dimension 2 or Higher
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.
The prefix notion in Kolmogorov complexity and computational models
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.
Kolmogorov complexity and cellular automata classification
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.
Introduction to the theory of algorithmic information
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.
How to simulate Turing Machines by invertible cellular automata
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.
Quick signals in higher dimensions
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.
Internship reports
Thursday 3 January 2008
While studying at École normale supérieure de Lyon, I did two internships in labs in my undergraduate years (one in 1993, one in 1994), the first one in the LIPlab and the second in the IIT Madras (when Chennai / சென்னை was still Madras).