• consenso booleano

In questo lavoro consideriamo il problema del consenso logico in sistemi multi-agente distribuiti, cioè studiamo come un insieme di nodi possano raggiungere un accordo sul valore booleano di una quantità di interesse attraverso lo scambio di messaggi.

In primo luogo, ripercorriamo alcuni risultati noti in letteratura e dovuti ad autori come R. Murray e S.Zampieri che sono validi in un ambito continuo, cioè quando la quantità scambiata e sulla quale si desidera raggiungere un accordo assume valori sull'insieme dei numeri reali. Peraltro, noi consideriamo problemi di natura completamente diversa, come la sincronizzazione degli orologi di un insieme di processori (si veda ad esempio il lavoro di K. Marzullo), la cui trattazione risulta essere di fondamentale importanza nell'ambito di applicazioni basate su algoritmi distribuiti (si veda N. Lynch).

Per risolvere il nostro problema, intendiamo adottare lo stesso approccio sistematico usato per i sistemi continui di Murray, che consiste nel considerare il meccanismo di consenso come un sistema
dinamico a variabili e tempo continui. Tale approccio consente di ricavare proprietà importanti come la velocità asintotica di convergenza del meccanismo di consenso, etc. Tuttavia, nel nostro
caso, il fatto che le quantità scambiate e la regola stessa con cui ogni nodo aggiorna la propri stima locale siano booleane o insiemistiche fa perdere linearità al problema e quindi lo rende di
non facile trattazione.

In questo contesto, noi proponiamo una soluzione al problema di sintetizzare una mappa logica distribuita e ne studiamo le proprietà di convergenza finita, sfruttando alcuni risultati legati al lavoro di
F. Robert sugli automi cellulari. Proponiamo delle condizioni necessarie e sufficienti sotto le quali il problema della sintesi distribuita risolubile. Presentiamo inoltre due algoritmi per la verifica di tali condizioni e per la sintesi stessa e ne studiamo la complessità computazionale. Affrontiamo infine il problema della sintesi robusta che consiste nel realizzare una mappa distribuita che possa tollerare guasti di un certo numero di sensori.

Dal punto di vista applicativo, consideriamo un problema di ``rilevamento di intrusione'', che consiste di un ambiente in cui è richiesto che una stanza venga monitorata per mezzo di sensori e preservata da possibili ingressi di intrusi. Analizziamo il comportamento del meccanismo di consenso nei casi in cui esso sia descritto da una legge distribuita di tipo booleano lineare e non.