Ricerc@Sapienza

When observed under the "Computational Lens" [K11], many natural systems exhibit
simple algorithmic motifs at a microscopic level, often
much simpler than artificially designed counterparts.
A first goal of this proposal is the application of the Computational-Lens (specifically, the
algorithmic lens) to the study of basic Information Processing tasks
observed at various levels in complex natural systems.
A related goal is the design and analysis of extremely simple, possibly nature-inspired,
fully decentralized algorithms to perform fundamental tasks of interest
in distributed computing. Despite preliminary steps, this is a formidable
task. For this reason, we intend to take a bottom-up approach, introducing and/or extending non-standard,
algorithmic and probabilistic techniques to model and analyze a
restricted pool of basic, yet crucial Information-Processing primitives,
concerning Information Spreading, Consensus, network formation and
clustering. A number of reasons motivate our choice: i) these tasks are
relatively simple, yet pervasive across complex natural systems at different levels; ii) they are key
building blocks for more complex tasks in Distributed Computing, such as Coordination and
Decision Making; iii) algorithmic characterizations of these tasks have
been proposed in restricted settings, but research in the area is
mostly in its embryonic state. A deeper theoretical understanding of these aspects can be
beneficial in several ways: i) it can advance our overall understanding
of fundamental processes; ii) the dynamic and complex nature
of the problems we address is likely to foster the development and/or
extension of novel techniques of analysis; iii) this effort can result
in novel paradigms for the design of effective and robust strategies for
complex coordination tasks.

NOTE: bibliography at the end of section "Descrizione obiettivi
progetto, conoscenza dello stato dell'arte nel tema specifico e impianto metodologico"