Topics for Class Projects in Distributed Computing 2017:

  1. The projects are done in pairs or triplets.
  2. We will schedule with each project during July 16 – July 28 to meet and go over the presentation.
  3. The idea is to take a topic (which would typically cover two or three tightly related papers), and try to suggest an improvement, or a variation, or to suggest a problem with the papers etc.
  4. Each project should submit two to three pages that summarize the research done, and a 15 minutes presentation.

Here are some suggestions for topics for the class project. Better yet would be if you can come up with your own idea/suggestion, please talk to me. The deadline for the projects is July 16.

To find good topics you can go over the papers presented in (use google search …) different years for the following conferences: PODC-2017/2016/2015, or DISC, or SIGCOMM, or SPAA, Infocom, SODA, etc. Find them on the internet and find the pdf's of the relevant papers. To find relevant papers use scholar.google. https://scholar.google.co.il/ to find papers that had referenced a particular paper, or papers on different topics. Here are some possible topics in a random order. These are just example!:

*New papers*

  1. Gossip in a Smartphone Peer-to-Peer Network, Calvin Newport (Georgetown University)
  2. Symmetry Breaking with Noisy Processes, Seth Gilbert (National University of Singapore) and Calvin Newport (Georgetown University)
  3. Ignore or Comply? On Breaking Symmetry in Consensus, Petra Berenbrink (University of Hamburg), Andrea Clementi (Università di Roma Tor Vergata), Robert Elsässer (University of Salzburg), Peter Kling (University of Hamburg), Frederik Mallmann-Trenn (École normale supérieure) and Emanuele Natale (Max-Planck-Institut)
  4. Life Beyond Set Agreement, David Yu Cheng Chan (University of Toronto), Vassos Hadzilacos (University of Toronto) and Sam Toueg (University of Toronto)
  5. Distributed MST and Routing in Almost Mixing Time, Mohsen Ghaffari (ETH Zurich), Fabian Kuhn (University of Freiburg) and Hsin-Hao Su (MIT)
  6. Analyzing Contention and Backoff in Asynchronous Shared Memory, Naama Ben-David (Carnegie Mellon University) and Guy Blelloch (Carnegie Mellon University)
  7. A Template For Implementing Fast Lock-free Trees Using HTM, Trevor Brown (University of Toronto)
  8. Deterministic Objects: Life beyond Consensus Yehuda Afek, Faith Ellen and Eli Gafni send me email if you want the pdf.
  1. Biological Distributed Algorithms
    1. ANTS problem (foraging) http://arxiv.org/abs/1205.2170 and the references in there, and papers that had referenced it (use scholar.google. https://scholar.google.co.il/)
    2. Read about Ants Task Allocation, and other, and think of a new one.
    3. Can you do Neural Distributed Algorithms? Mimic network of neurons by a distributed network of cells?
    4. +Game theory between ant colonies, Competition or cooperation between ant colonies - in foraging, task allocation, and other problems?
    5. Consider other social insects (Bees, Bats, Rats, you name it).

  2. Multi-core programming:
    1. On the Complexity of Reader-Writer Locks, by Danny Hendler
    2. Analysing Snapshot Isolation" by Andrea Cerone_ Alexey Gotsman
    3. Try Hardware Lock Elision (HLE) on an existing lock based application, improve the performances (see e.g., http://dl.acm.org/citation.cfm?id=2611482 ).
    4. Practical concurrent programming issues you faced at work.
    5. A. Matveev, N. Shavit, P. Felber, P. Marlier Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming. SOSP 2015, Monterey, California, USA
    6. D. Alistarh, W. M. Leiserson, A. Matveev, N. Shavit ThreadScan Automatic and Scalable Memory Reclamation SPAA 2015
    7. A. Matveev, N. Shavit Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory. ASPLOS 2015, Istanbul, Turkey

  3. Game theory and distributed computing (see e.g. http://dl.acm.org/citation.cfm?id=2611481 ):
    1. Spanning tree or MIS with rational agents (or MST) (like the homework question about the senators).
    2. Variations on coloring problems (blinking, 2- neighbors coloring, etc)?
    3. Byzantine? Read the paper "Rational Consensus" Halpern Vilaca

  4. Models of Read/write – message passing,
    1. A Complexity-Based Hierarchy for Multiprocessor Synchronization Faith Ellen, Rati Gelashvili, Nir Shavit and Leqi Zhu

  5. Population protocols
    1. Noisy Rumor Spreading and Plurality Consensus Pierre Fraigniaud and Emanuele Natale
    2. How Asynchrony Affects Rumor Spreading Time George Giakkoupis, Yasamin Nazari and Philipp Woelfel

  6. Networking look at this if you find an interesting topic here Here is the 2017: at this if you find an interesting topic I have a copy of the papers (2017).
    1. Software Defined Networks: It's About Time Tal Mizrahi and Yoram Moses (Technion, Israel)
    2. SDN for Security & Management Chair: Jinyuan (Stella) Sun (University of Tennessee, USA)
    3. Contextual, Flow-Based Access Control with Scalable Host-based SDN Techniques Curtis Taylor, Douglas MacFarland, Doran Smestad and Craig A. Shue (Worcester Polytechnic Institute, USA)
    4. DDoS Attack Detection under SDN Context Yang Xu and Yong Liu (New York University, USA)
    5. FOUM: A Flow-Ordered Consistent Update Mechanism for Software-Defined Networking in Adversarial Settings Jingyu Hua, Xin Ge and Sheng Zhong (Nanjing University, China)
    6. Measurement-based Flow Characterization in Centrally Controlled Networks Zdravko Bozakov (EMC Research Europe, Ireland) Amr Rizk, Divyashri Bhat, Michael Zink (University of Massachusetts Amherst, USA)
    7. On Consistent Migration of Flows in SDNs Sebastian Brandt (ETH Zurich, Switzerland) Klaus-Tycho Förster (ETH Zurich & Microsoft Research, Switzerland) Roger Wattenhofer (ETH Zurich, Switzerland)
    8. Distributed Deterministic Broadcasting Algorithms under the SINR Model Xiang Tian and Jiguo Yu (Qufu Normal University, China) Liran Ma (Texas Christian University, USA) Guangshun Li (Qufu Normal University, China) Xiuzhen Cheng (George Washington Univ, USA)
    9. Streaming Big Data meets Backpressure in Distributed Network Computation Apostolos Destounis and Georgios S. Paschos (Huawei Technologies France Research Center, France) Iordanis Koutsopoulos (Athens University of Economics and Business and CERTH & CERTH, Greece)
    10. A Novel Framework for Modeling and Mitigating Distributed Link Flooding Attacks Christos Liaskos (Institute of Computer Science, Foundation of Research and Technology, Hellas, Greece) Vasileios Kotronis (ETH Zurich, Switzerland) Xenofontas Dimitropoulos (FORTH-ICS, Greece)

  7. Various
    1. Optimal Dynamic Distributed MIS Keren Censor-Hillel, Elad Haramaty and Zohar Karnin
    2. Specification and Complexity of Collaborative Text Editing Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang and Marek Zawirski
    3. An improved distributed algorithm for maximal independent set, SODA’16, best paper Mohsen Ghaffari
    4. Mohsen Ghaffari and Merav Parter, Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures (SPAA) 2016.