Distributed computing power : from local function to global computing

Laurent Bienvenu (1) , Christophe Papazian (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Distributed Algorithms; Computability; Graph Automata

Domaines: Informatique [cs]

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⟩