Distributed computing power : from local function to global computing - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2003

Distributed computing power : from local function to global computing

Résumé

We show here a natural extension of finite graph automata, by allowing each node of a network to store in its memory some pieces of information that are only bounded by the size of the underlying network (like a unique address). Depending of the power of the new local transition function, we show results about the power of the global function computed by the graph automata. The main result is that the global power is always less than the local computing power and even with very powerful local function (non recursive) we can not compute all global functions (even some primitive recursive ones) : Distributed computing is limited by its own structure.
Fichier principal
Vignette du fichier
RR2003-15.pdf (178.56 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101834 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101834 , version 1

Citer

Laurent Bienvenu, Christophe Papazian. Distributed computing power : from local function to global computing. [Research Report] LIP RR-2003-15, Laboratoire de l'informatique du parallélisme. 2003, 2+10p. ⟨hal-02101834⟩
27 Consultations
45 Téléchargements

Partager

More