Informatique amorphe

L'informatique amorphe désigne les systèmes informatiques qui utilisent un très grand nombre de processeurs identiques et parallèles, chacun ayant une capacité de calcul et des interactions locales limitées. Le terme informatique amorphe a été inventé au MIT en 1996 dans un article intitulé « Amorphous Computing Manifesto » par Abelson, Knight, Sussman et al.

Des exemples de calculs amorphes naturels peuvent être trouvés dans de nombreux domaines, tels que la biologie du développement (le développement d'organismes multicellulaires à partir d'une seule cellule), la biologie moléculaire (l'organisation des compartiments sous-cellulaires et la signalisation intracellulaire), les réseaux neuronaux et le génie chimique (systèmes hors équilibre). L'étude du calcul amorphe est indépendante du matériel informatique : elle ne s'intéresse pas au substrat physique (biologique, électronique, nanotechnologique, etc.) mais plutôt à la caractérisation d'algorithmes amorphes en tant qu'abstractions dans le but de comprendre les exemples naturels existants et de concevoir de nouveaux systèmes.

Les ordinateurs amorphes ont tendance à avoir bon nombre des propriétés suivantes :

• Mis en œuvre par des périphériques redondants, potentiellement défectueux et massivement parallèles .
• Appareils dotés d'une mémoire et de capacités de calcul limitées.
• Appareils asynchrones.
• Appareils n'ayant aucune connaissance a priori de leur emplacement.
• Appareils communiquant uniquement localement.
• Présenter un comportement émergent ou auto-organisé (modèles ou états plus grands qu’un dispositif individuel).
• Tolérant aux pannes, en particulier aux appareils malformés ou aux perturbations d'état occasionnelles.

(Certains de ces algorithmes n’ont pas de nom connu. Lorsqu’un nom n’est pas connu, un nom descriptif est donné.)

• « Communication fickienne » . Les appareils communiquent en générant des messages qui se diffusent à travers le milieu dans lequel ils se trouvent. La force du message suivra la loi du carré inverse telle que décrite par la loi de diffusion de Fick . Des exemples de ce type de communication sont courants dans les systèmes biologiques et chimiques.
• « Communication par diffusion de liens » . Les appareils communiquent en propageant des messages via des liaisons câblées d'un appareil à l'autre. Contrairement à la « communication fickienne », il n'existe pas nécessairement de support diffusif dans lequel les appareils se trouvent et la dimension spatiale n'est donc pas pertinente et la loi de Fick n'est pas applicable. On trouve des exemples dans les algorithmes de routage Internet tels que l' algorithme de mise à jour par diffusion . La plupart des algorithmes décrits dans la littérature sur l'informatique amorphe supposent ce type de communication.
• « Propagation d'onde » . (Réf 1) Un appareil émet un message avec un nombre de sauts codé. Les appareils qui n'ont pas vu le message auparavant incrémentent le nombre de sauts et le rediffusent. Une onde se propage à travers le support et le nombre de sauts à travers le support codera effectivement un gradient de distance à partir de la source.
• « Identifiant aléatoire » . Chaque appareil se donne un identifiant aléatoire, l'espace aléatoire étant suffisamment grand pour éviter les doublons.
• « Programme de points de croissance » (Coore). Processus qui se déplacent entre les dispositifs selon le « tropisme » (mouvement d'un organisme dû à des stimuli externes).
• « Coordonnées des vagues » . Diapositives PPT de la DARPA. À rédiger.
• « Requête de voisinage » . (Nagpal) Un appareil échantillonne l'état de ses voisins par un mécanisme push ou pull.
• « Pression des pairs » . Chaque appareil conserve un état et communique cet état à ses voisins. Chaque appareil utilise un schéma de vote pour déterminer s'il doit ou non changer d'état pour celui de son voisin. L'algorithme partitionne l'espace en fonction des distributions initiales et constitue un exemple d'algorithme de clustering.
• « Ligne auto-entretenue » (Lauren Lauren, Clément). Un gradient est créé à partir d'un point d'extrémité sur un plan couvert d'appareils via la communication par diffusion de liens. Chaque appareil est conscient de sa valeur dans le gradient et de l'identifiant de son voisin qui est plus proche de l'origine du gradient. Le point d'extrémité opposé détecte le gradient et informe son voisin le plus proche qu'il fait partie d'une ligne. Cela se propage le long du gradient en formant une ligne qui résiste aux perturbations du champ. (Illustration nécessaire).
• « Formation de club » (Coore, Coore, Nagpal, Weiss). Des groupes locaux de transformateurs élisent un leader qui sert de centre de communication local.
• « Formation de coordonnées » (Nagpal). Plusieurs gradients sont formés et utilisés pour former un système de coordonnées via la triangulation.

• Hal Abelson , MIT
• Jacob Beal, étudiant diplômé du MIT (langages de haut niveau pour le calcul amorphe)
• Daniel Coore, Université des Antilles (langage des points de croissance, tropisme, série d'onduleurs cultivés)
• Nikolaus Correll , Université du Colorado ( matériaux robotiques )
• Tom Knight , MIT (calcul avec biologie synthétique)
• Radhika Nagpal, Harvard (systèmes auto-organisés)
• Zack Booth Simpson, Ellington Lab, Univ. of Texas à Austin. (Détecteur de bord bactérien)
• Gerry Sussman , Laboratoire d'intelligence artificielle du MIT
• Ron Weiss, MIT (déclenchement de règles, langage des colonies microbiennes, formation de modèles de coli)