Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 (Research report)
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:07:34 AM
Last modification on : Wednesday, October 26, 2022 - 8:15:53 AM


Files produced by the author(s)


  • HAL Id : hal-02101834, version 1



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⟩



Record views


Files downloads