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.
Domaines
Informatique [cs]Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...