Realistic Distributed Algorithms Reading Group

  Time: Fridays 11am-12:30pm, Spring Semester 2017 (first Meeting 2/17)
  Location: Stata Center (Bulding 32), G575
  Contact: Hsin-Hao Su (hsinhao at mit dot edu), Merav Parter (parter at mit dot edu)
(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.
my photo

Past/Upcoming Meetings

(2/17) Computing with Spiking Neural Networks, Merav Parter.

(2/24) VC Dimension in (Neural) Circuit Complexity, Cameron Musco. See notes here.

(3/10) Models of Cortical Computation, Quanquan Liu.

Future Reading List (Tentative)

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.
  • Find your place: Simple distributed algorithms for community detection. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan. SODA 2017.
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).