Una soluzione al problema del massimo insieme indipendente

Per sistema distribuito si intende un insieme di computer autonomi che comunicano in una rete per ottenere un obiettivo comune. Quindi il massimo insieme indipendente (Maximal Independent Set, MIS) è un soggetto all'interno di un sistema distribuito. D'altra parte cosa si intende per MIS?

Nella teoria dei grafi, un massimo insieme indipendente o il massimo insieme stabile (maximal stable set) è un insieme indipendente che non è sottoinsieme di un altro insieme indipendente.

Degli esempi sono meglio delle parole, ed eccoli tratti da Commons (pubblico dominio) sul grafo di un cubo:

Come si può vedere ogni MIS è costituito da punti che non sono adiacenti (conserviamo l'informazione).
L'obiettivo del problema del massimo insieme indipendente è trovare la dimensione massima del MIS in un dato grafo o rete. In altre parole il problema è cercare i leader in una rete locale di provessori connessi, dove per leader possiamo intendere un nodo attivo connesso con un nodo inattivo, come nell'esempio.
Un problema di questo genere è di tipo NP (giusto per avere un'idea della complessità della questione).

Secondo Afek, Alon, Barad, Hornstein, Barkai and Bar-Joseph,

nessun metodo è in grado di ridurre efficientemente la complessità di un messaggio senza assumente della conoscenza sul numero dei vicini.

Una rete simile a quella di cui si sta parlando, però, si ritrova anche nei precursori delle setole sensoriali della mosca, così l'idea dei ricercatori è di utilizzare i dati provenienti da questa rete biologica per risolvere il problema computazionale da cui siamo partiti.

Un tale sistema da ora in poi sarà indicato come SOP, sensory organ precursors, i precursori degli organi sensoriali.

Ci sono molte similitudini tra MIS e SOP:

1. la selezione di una cellula particolare come SOP è un evento casuale governato da un sottostante processo stocastico^{(3, 5)};
2. come per il caso computazionale, la selezione di una SOP è probabilmente limitata nel tempo poiché la situazione usuale di tutte le cellule della rete è diventare una SOP a meno di non essere inibita⁽⁴⁾;
3. negli algoritmi computazionali^{(1, 2)} i processori mandano segnali solo quando propongono la loro candidatura a diventare leader, riducendo così la complessità della comunicazione.

In particolare queste proprietà sono sviluppate nelle reti biologiche studiate usando le proteine Delta e Notch: in questo modo una cellula selezionata come SOP inibisce i suoi vicini ottenendo una situazione simile a quella in figura, dove le cellule in blu sono leader:

I ricercatori così provano a descrivere la rete biologica:

Abbiamo assunto una serie di processori identici posti sui nodi di una rete con comunicazione sincrona arbitraria. I nodi possono solo trasmettere un messaggi da un bit. Un messaggio trasmesso da un nodo raggiunge tutti i suoi vicini che sono ancora attivi nell'algoritmo. Ad ogni giro, un processore può solo dire se gli è stato inviato un messaggio o meno. Quando un processore riceve un messaggio, non si può dire quale dei suoi processori vicini lo ha inviato, e non si può contare il numero di messaggi ricevuti in un giro.

Tutto questo diventa il seguente algoritmo:

dove $n$ è il numero di nodi, $D$ un limite superiore al numero di vicini che ogni nodo può avere, $M$ un parametro settato a 34, mentre ogni nodo ha una probabilità $p_i$ di inviare un messaggio si suoi vicini.
Per selezionare il modello definitivo, Yehuda Afek e colleghi hanno confrontato i dati sperimentali collezionati da 10 pupe:

con i risultati delle simulazioni:

E alla fine i nostri possono concludere che:

l'unico modo in cui l'algoritmo può sbagliare è terminare mentre sta lasciando alcuni nodi che non sono in A e che sono anche non connessi con nodi in A. Successivamente, mostriamo che quando un algoritmo termina tutti i nodi presenti, con alta probabilità, o in A o connessi a un nodo in A, ha risolto il problema MIS.

(1) M. Luby, SIAM J. Comput. 15, 1036 (1986)
(2) N. Alon, L. Babai, A. Itai, J. Algorithms 7, 567 (1986)
(3) P. Simpson, Curr. Opin. Genet. Dev. 7, 537 (1997)
(4) B. Castro et al., Development 132, 3333 (2005)
(5) M. E. Fortini, Dev. Cell. 16, 633 (2009)

Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., & Bar-Joseph, Z. (2011). A Biological Solution to a Fundamental Distributed Computing Problem Science, 331 (6014), 183-185 DOI: 10.1126/science.1193210