A very simple randomised distributed algorithm imposing an acyclic orientation on any arbitrary anonymous asynchronous network is presented in this paper. The problem is faced under the noinfo assumption: no network attribute is available and when the algorithm starts each processor only knows the number of its input/output ports (i.e. the number of its immediate neighbours). The presented algorithm terminates explicitly (process termination) in O(logn)-time on a non complete graph only exchanging messages of constant size among immediate neighbours (i.e. nodes connected through a direct link).
Distributed Acyclic Orientation of Asynchronous Anonymous Networks
A Calabrese
1997
Abstract
A very simple randomised distributed algorithm imposing an acyclic orientation on any arbitrary anonymous asynchronous network is presented in this paper. The problem is faced under the noinfo assumption: no network attribute is available and when the algorithm starts each processor only knows the number of its input/output ports (i.e. the number of its immediate neighbours). The presented algorithm terminates explicitly (process termination) in O(logn)-time on a non complete graph only exchanging messages of constant size among immediate neighbours (i.e. nodes connected through a direct link).File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
