Distributed computing power : from local function to global computing

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101834
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:34 AM
Last modification on : Sunday, May 19, 2019 - 1:20:45 AM

File

RR2003-15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101834, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

11

Files downloads

7