Distributed Computing in Sparse Networks,
ready for submission
descrizione: Si consideri un sistema distribuito ossia una rete dove i nodi rappresentano processori e gli archi rappresentano collegamenti tra processori. La rete é chiamata a computare una funzione della propria stessa topologia, come ad esempio: un insieme massimale indipendente, una colorazione degli archi in al piú
colori,
una colorazione dei nodi in al piú 
colori.
Vogliamo che ció avvenga in un numero di passi
polilogaritmico nel numero di nodi della rete
e tramite un protocollo deterministico.
Questa é una problematica che ha lungamente resistito
agli attacchi di esperti ed affermati ricercatori.
Noi si é aggirata la difficoltá considerando
il caso di reti sparse.
Infatti da un lato questo é il caso che
si presenta nelle applicazioni
e dall'altro qualora la rete fosse sufficientemente densa
i problemi di cui sopra ammetterebbero una soluzione
banale in pratica non distribuita.
Sotto questa ipotesi semplificatrice abbiamo mostrato
come si possano ottenere dei risultati positivi
per i problemi di cui sopra.
