Web Site: https://wendy.paris/
Date: October, 10-11, 2018
The research question central to the workshop is the design of simple random processes on a network to achieve specified emergent behavior, i.e. "programming" local interactions to obtain desirable global effects. In a simple setting, network sites may hold one of a finite number of states. A protocol operating on a static network may be described by a transition rule applied to a pair of adjacent sites, e.g., of the form A+B -> C+D (sites in states "A" and "B" transition to states "C" and D"), whose activation probability depends only on conditions in the local neighborhood. This formalism is common to studies of population protocols, chemical reaction networks (CRN-s), opinion propagation mechanisms, epidemic-type processes, some local distributed algorithms, and some local dynamics in spin gases or spin glasses. A protocol on a network may be viewed as a dynamical system, whose dimension depends on the underlying network topology and whose limit behavior depends on the type of protocol. Current challenges include:
• designing mechanisms of coordination on a network: obtaining a periodic signal (controling global phase clocks and other oscillators), adapting to the state of a distinguished site (leader election, broadcasting, etc.), eliminating noise from a system, etc.
• extending the theory of protocols from some intensively studied topologies (complete graphs, grids) to topologies known to appear in real-world considerations or to be an effective way of organizing a synthetic network (low-degree expanders such as random regular graphs, power law graphs).
• designing local protocols which involve network reorganization (e.g., optimization of diameter, expansion, node centrality measures, and other structural properties), as well as protocols for self-assembly of structures.
• bridging the gap between the understanding of information-spreading protocols in synthetic (biological) network theory and elements of the theory of recurrent neural networks.