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"
P1. We plan to address novel aspects, that to some extent are
orthogonal to all process classes we consider. One is the design and
analysis of elementary dynamics for broadcast and convergecast [BCNPT16],
with a focus on underlying topologies where a hidden, reliable
subgraph is available. Another aspect is their convergence and
(probabilistic) self-stabilization (see also P2), in particular their dependence
on stability and expansion properties of the hidden subgraph. Moreover,
since any hidden community structure of a complex system can play a crucial role in
its ability to perform information-processing tasks [R+15,S10], we further plan to characterize the
interplay between community structure and metastable phases in which
different components of the global system temporarily and locally "stabilize''.
To address this challenge, we shall rely on extended notions of
conductance and community in dynamic graphs, which are effective to
capture the real factors behind information spreading even across
sequences of sparse and disconnected snapshots of an underlying network.
P2. We consider two challenging scenarios and, eventually, a
combination of them.
(i) Self-Stabilizing Consensus.
We plan to analyze Plurality Consensus in novel scenarios aspects
discussed above for P1. We remark that
preserving any initial plurality in randomly evolving, dynamic
scenarios is a more challenging goal than achieving information
spreading (as in P1). While [FN16] is a first step in this direction, the
proposed protocols and models fail to capture important traits of the
biological system that inspired them. We instead focus on simple epidemic
dynamics, with input from the foundational work in WPI (see next section).
(ii) Other forms of consensus, simpler heuristics
As mentioned earlier, consensus appears in different
flavors in a number of complex systems. A pervasive, natural form of consensus is density
estimation/quorum sensing. While its role is crucial in many natural
complex system, a convincing computational characterization is still lacking. A first
attempt to account for the effectiveness of strategies adopted by some
ant species was proposed in [MSL17], yet their proposal still involves
relatively sophisticated and sometimes unrealistic local,
decision-making strategies. Closing this gap seems to require novel
approaches and techniques of analysis. A first goal we pursue is
providing an algorithmic characterization of quorum sensing that is
more consistent with realistic scenarios, e.g., replacing the ability
of agents to count with their ability to sense when a threshold is
reached or close. Another goal is investigating the complex interplay
between local density estimation and global consensus.
P3. Research will address the following main directions:
(i) Simple dynamics for network formation.
As mentioned earlier, network formation protocols are in place in a
number of P2P systems. In important cases however, not much is known
about key properties of the resulting topologies. In Bitcoin for
example, each node in a communication network is aware of the existence
of a certain subset of the other nodes and it tries to establish a minimum
number of connections to other nodes (or to special server nodes). It does so by selecting them
at random from a local list of known nodes (or known servers). Nodes also
have a maximum number of connections they are going to accept, rejecting
further connections once this limit is reached. While the resulting
network is approximately regular by construction, much less is known about
other key topological properties. Our goal is investigating
connectivity and expansion properties of networks resulting from this
or similar network formation processes, using or adapting probability
and spectral tools of analysis.
(ii) Identifying community structure.
Our plan here is extending the work of [B+17] along two directions.
First, their results hold for two communities under mild
almost-regularity assumptions. A first question is extending their
approach to multiple communities while preserving the original
simplicity of the approach. A second goal is investigating clustering
properties of simple consensus dynamics. While preliminary work in this
direction exists for belief propagation algorithms [C+18], previous
work suggests this might also be the case for consensus dynamics, though
their lack of linearity seems extremely challenging even in simple settings [CDGNS13].