Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
Recentemente si e' rinnovato l'interesse per il broadcast (distribuire un messaggio da una sorgente a tutti gli altri nodi) su reti radio multi-hop, grazie alla scoperta di nuovi protocolli distribuiti e deterministici. La comunicazione su reti radio deve sottostare ad alcuni vincoli speciali. Ad esempio, se due nodi tentano di trasmettere contemporaneamente allo stesso nodo questo puo' non essere in grado di recuperare i messaggi inviategli. Tali vincoli rendono il problema della progettazione di protocolli efficienti per il broadcast, in generale, non banale. In questo seminario si prendera' in considerazione il modello piu' "prudente": i nodi non conoscono nulla della topologia della rete se non il loro identificativo. Tale modello e' stato studiato a partire dalla fine degli anni '80. Si discuteranno i principali risultati noti: protocolli distribuiti sia deterministici che randomizzati e limiti inferiori sul tempo necessario a completare un'operazione di broadcast. In particolare, verranno presentati nuovi protocolli deterministici e limiti inferiori che a differenza di quelli del passato sono sensibili a caratteristiche della rete come il diametro ed il massimo numero di nodi che possono trasmettere ad un nodo. Si mostrera' come molti di questi risultati siano basati sulla scoperta di una nuova e molto promettente connessione con la costruzione ottimale di vari oggetti combinatorici. Basato su un lavoro con Andrea Clementi ed Angelo Monti.