Abstracts

An Introduction to Amorphous Computing


The study of amorphous computing aims to identify useful programming
methodologies that will enable us to engineer the emergent behaviour of a
myriad, locally interacting computing elements (agents).  We anticipate that in
order to keep such massively distributed systems cheap, the elements must be
bulk manufactured.  Therefore, we use a conservative model in which the agents
run asynchronously, are interconnected in unknown and possibly time-varying
ways, communicate only locally, and are identically programmed.  I present a
description of this model, and some of the results that have been obtained with
it, particularly in the areas of pattern formation and the development of
programming languages that are specifically suited to our model.  Finally, I
present some of the interesting and important problems that still remain open in
amorphous computing.

Order From Disorder: How to program an Amorphous Computer

Predicting the emergent behaviour of a large number of locally-interacting
computing elements, starting from a given initial condition, is a notoriously
difficult problem.  In fact, even if we assume that we know exactly how each
element behaves, how many neighbours it has, and how it interacts with its
neighbours (e.g. in a cellular automaton), the problem still remains difficult.
It is therefore natural to expect that the converse problem -- given a desired
emergent behaviour, produce the individual behaviour that will give rise to it
-- would be even harder.  An amorphous computing environment is an example of
such a system, and we show that such systems can be programmed with a reasonable
degree of control within a limited scope of application.  Our approach has
largely centred around the development of programming languages that capture
important metaphors which are implemented by carefully crafted individual-level
activities.  These languages permit us to combine those metaphors in useful
ways, without losing the ability to reason about their emergent outcomes.  In
this talk, I will illustrate their expressive power and their limitations, and
discuss how those limitations might be overcome.

Programmation de machine amorphe

Je présenterai l'implémentation d'un langage de programmation d'ordinateurs
amorphes utilisant les Blobs. Je commencerai par exposer mon langage orienté
composants et aspects permettant de programmer les éléments de l'ordinateur
amorphe. Puis je m'attarderai sur la réalisation de trois primitives Blob: la
création d'un Blob à partir d'un ensemble d'éléments de calcul, la liaison entre
deux Blobs et la division d'un Blob. Je conclurai en exposant des perspectives
pour la construction d'une machine Blob fonctionnelle.

Répartition uniforme de particules sur automates cellulaires par diagramme de Voronoï

Les architectures parallèles utilisent aujourd'hui un nombre de plus en plus
important d'éléments de calculs mais leur programmation reste quelque chose de
difficile. Le Blob Computing apporte une abstraction par rapport à ces
architectures permettant d'en faciliter la programmation sans en dénaturer la
puissance.  L'implémentation de cette abstraction met en oeuvre des placements
automatiques de tâches sur les éléments de calculs, en prenant en compte leurs
positions et des contraintes de performances. Dans ce cadre, nous proposons un
algorithme permettant de placer des particules sur un modèle d'architecture
classique : les automates cellulaires. Cet algorithme permet, à l'aide de
diagramme de Voronoï, de répartir uniformément des particules sur un espace
cellulaire de façon auto-stabilisante. Il peut donc être utilisé pour réaliser
un équilibrage de charges, et s'intègre en tant que premier résultat dans notre
étude de l'implémentation des primitives abstraites du projet Blob Computing.

L'étude des automates celullaires probabilistes comme prolégomènes au calcul spatial

Le modèle des automates cellulaires repose sur la présence d'unités de calcul
simples disposées sur uen grilel régulière et évoluant de manière synchrone. Que
se passe-t-il si l'on pertubre ce mode de fonctionnement ? 
Je présenterai différentes expériences montrant l'effet du passage d'une mise à
jour synchrone à une mise à jour asynchrone, ainsi que l'effet de perturbation
de la topologie (trous dans la grille, introduction d'obstacles). J'examinerai
plus particulièrement un modèle simple utilisant la réaction-diffusion pour
réaliser une aggrégation de particules "sans chef". Dans le cadre du calcul
spatial, ces problèmes de robustesse d'automates cellulaires peuvent consituer
de bons exercices avant de réaliser des calculs par auto-organisation.

Phéromones digitales: résolution de problèmes multi-agents situés par marquage de l'environnement

Les phéromones déposées par les insectes sociaux pour communiquer indirectement
à travers l'environnement ont inspiré ces dernières années des algorithmes
décentralisés pour la résolution de problème (le plus connu étant ACO Ant Colony
Optimization de Dorigo 92 pour le TSP). Plus récemment, les processus de
diffusion, d'évaporation et d'agrégation ont été repris pour traiter des
problèmes plus spatialisés et dynamiques (poursuite, path-planning, etc.) Cet
exposé présentera brièvement cet existant, puis donnera des éléments de
modélisation et de complexité sur les processus mis en jeux, et enfin présentera
en détail l'exploitation du processus d'évaporation pour le traitement de la
patrouille multi-agent en environnement inconnu.

A multi-cellular approach to artificial embryogeny

We present a continuous model for Multi-cellular Developmental Design. The cells
are fixed on a 2D grid and exchange "chemicals" with their neighbors during the
growth process. The quantity of chemicals that a cell produces, as well as the
differentiation value of the cell in the phenotype, are controlled by a Neural
Network (the genotype) that takes as inputs the chemicals produced by the
neighboring cells at the previous time step.

Topological rewriting, autonomous systems and the geometrization of programming

Technological advances brought new computing media that provide unbounded
computing resources. At the same time, applications become incremental and
massively distributed. They can be characterized as being dynamical systems with
a dynamical structure. In this talk, we propose to rely on the dynamical spatial
structures exhibited by those applications and computing media to structure
programs in a declarative framework. This leads to develop topological rewriting
where a rule specifies the local evolution of some interacting parts in the
system.