Un algoritmo in Field Calculus per il problema del flusso massimo

The maximum flow problem is a classic optimization problem in graph theory that involves finding the maximum amount of flow that can be sent from a source to a sink through a network of pipes, channels, or other pathways, subject to capacity constraints. We discuss the problem in a spatially distributed perspective: each node in the network is a single computing device that communicates only with other devices that are close to it. Our contributions are: - to provide a distributed algorithm written in $Field\ Calculus$ that addresses the problem in a distributed context; - to analyze this algorithm finding sufficient conditions for its correctness; This calculus is studied to be resilient to network topology changes. A distributed algorithm written in Field Calculus continues its computation even if some nodes shut down, move, or turn on. In general, the correctness of an algorithm for immutable networks doesn't imply its correctness for networks with perturbations. Under some hypotheses, our distributed algorithm solves the maximum flow problem if the network is immutable and we manage to inject a fairly small amount of global knowledge via a parameter. Future works should investigate the correctness of our algorithm when perturbations on the network are allowed, i.e. if it exploits the crucial properties of Field Calculus.

Il problema del flusso massimo è un problema di ottimizzazione nella teoria dei grafi che consiste nel trovare la quantità massima di flusso che può essere inviata da una sorgente ad un pozzo attraverso una rete di tubi, canali o altri percorsi, soggetti a vincoli di capacità. Nella formulazione classica, c'è un dispositivo di calcolo cui diamo in input una (rappresentazione di una) rete. Invece noi consideriamo il problema in una riformulazione spazio-temporale: ogni nodo della rete è un singolo dispositivo di calcolo che comunica solo con gli altri dispositivi vicini. Quindi, l'algoritmo è inteso come implementato su ogni dispositivo e può utilizzare solo le informazioni localmente disponibili per il dispositivo durante l'esecuzione. I nostri contributi sono: - fornire un algoritmo distribuito scritto in Field Calculus che punti a risolvere il problema in un contesto distribuito; - analizzare questo algoritmo trovando condizioni sufficienti per la sua correttezza. Nel Field Calculus ogni dispositivo esegue turni di calcolo ad un ritmo regolare: il dispositivo si sveglia, raccoglie i messaggi ricevuti dalla fine del turno precedente, esegue l'algoritmo, invia un messaggio ai dispositivi vicini, e va di nuovo a dormire. Questo calcolo è studiato per essere resiliente ai cambiamenti della topologia di rete. Un algoritmo distribuito scritto in Field Calculus continua la sua esecuzione anche se alcuni dispositivi si spengono, si muovono o si accendono. In generale, la correttezza di un algoritmo per reti immutabili non implica la sua correttezza per reti soggette a perturbazioni. Noi dimostriamo la correttezza del nostro algoritmo su reti immutabili di dispositivi (se viene soddisfatta anche un'altra ipotesi). I futuri sviluppi dovrebbero innanzitutto indagare la correttezza del nostro algoritmo quando sono consentite perturbazioni sulla rete, cioè se sfrutta le proprietà cruciali del Field Calculus.