Realistic Distributed Algorithms Reading Group
Time: Fridays 1pm-2:30pm, Spring Semester 2017 (first Meeting 2/17)
Location: Stata Center (Bulding 32), G631
Contact: Hsin-Hao Su (hsinhao at mit dot edu), Merav Parter (parter at mit dot edu)
(please contact to be added to email list)
(please contact to be added to email list)
Distributed computing is everywhere. In a wired or wireless communication network, the computation proceeds in a distributed manner. In fact, nature is distributed by design. We will study how distributed computing is happening in neuron networks, insect colonies, and dynamic graphs.
Past/Upcoming Meetings
(2/17) Computing with Spiking Neural Networks, Merav Parter.
- Computing with spiking neurons. Wolfgang Maass.
- Networks of spiking neurons: the third generation of neural network models. Wolfgang Maass.
- See discussion of universal approximation theorem for sigmoid nets here and universal computation by perceptron networks with a single hidden layer in Section 3.3 here.
(2/24) VC Dimension in (Neural) Circuit Complexity, Cameron Musco. See notes here.
- VC dimension in circuit complexity. Pascal Koiran.
- What Size Net Gives Valid Generalization? Eric B. Baum and David Haussler.
- Also see bounds on VC dimension for recurrent networks and for networks with sigmoidal and polynomial gates.
(3/10) Models of Cortical Computation, Quanquan Liu.
- Cortical Learning via Prediction. Christos Papadimitrou, Santosh Vempala. COLT 2015.
- For related recent work see Cortical Computation via Iterative Constructions. Papadimitrou, Petti, Vempala. COLT 2016.
(3/17) Models of Cortical Computation (continued), Kishori Konwar.
(4/7) Data Aggregation in Population Protocols, Hsin-Hao Su.
- Gossip-Based Computation of Aggregate Information. David Kempe, Alin Dobra, and Johannes Gehrke. FOCS 2003.
(4/14) Distributed House-Hunting in Ant Colonies, Nicholas Schiefer.
- Based off Chapter 3 of Mira Radeva's 2017 Ph.D. thesis.
(4/21) Community Detection in Population Protocols, Cameron Musco.
- Mostly focused on: Friend or Foe? Population Protocols can perform Community Detection. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan. arXiv 2017.
- This work is a follow up to the closely related: Find your place: Simple distributed algorithms for community detection. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan. SODA 2017.
(4/28) Johnson-Lindenstrauss Compression with Neuroscience-based Constraints, Rati Gelashvili.
- Based off work in Sparse sign-consistent Johnson–Lindenstrauss matrices: Compression with neuroscience-based constraints. Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali, and Nir Shavit. PNAS.
(5/12) Simple Consensus Protocols, Frederik Mallmann-Trenn.
Future Reading List
Neural Networks
- Neural Dynamics as Sampling: A Model for Stochastic Computation in Recurrent Networks of Spiking Neurons. Lars Buesing, Johannes Bill, Bernhard Nessler, Wolfgang Maass. PLoS Comput Biol. 2011 Nov;7(11).
- Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. Nancy Lynch, Cameron Musco, and Merav Parter. ITCS 2017.
- Bootstrap percolation with inhibition. Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou, Frank Mousset, Angelika Steger. arXiv:1410.3291.
Insect Colonies
- The ANTS Problem. Feinerman O; Korman A. Distributed Computing, 2016.
- Stone Age distributed computing. Yuval Emek, Roger Wattenhofer. PODC 2013: 137-146.
- Ant-Inspired Density Estimation via Random Walks. Cameron Musco, Hsin-Hao Su, Nancy A. Lynch. PODC 2016: 469-478.
- A locally-blazed ant trail achieves efficient collective navigation despite limited information. E. Fonio, Y. Heyman, L. Boczkowski, A. Gelblum, A. Kosowski, A. Korman, and O. Feinerman. eLife, 2016.
Dynamic Graphs
- Tight Fault Locality. Shay Kutten, David Peleg. SIAM J. Comput. 30(1): 247-268 (2000).
- Optimal maintenance of a spanning tree. Baruch Awerbuch, Israel Cidon, Shay Kutten. J. ACM 55(4): 18:1-18:45 (2008).
- Local-on-Average Distributed Tasks. Merav Parter, David Peleg, Shay Solomon. SODA 2016: 220-239.
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks. Leonid Barenboim. J. ACM 63(5): 47:1-47:22 (2016).