Topics for Class Projects in Distributed Computing 2019:

  1. The projects are done in pairs.
  2. We will schedule with each project during June 10 mid-July to meet and go over the presentation and discuss your project.
  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.
  5. Let me know if you encounter difficulties in finding any specific paper(s).

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 June 16.

To find good topics you can go over the papers presented in (use google search) different years for the following conferences: PODC -2018 / PODC-2017/2016/2015, or DISC2018, list of PODC2019 accepted papers. 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!:

1. Why Extension-Based Proofs Fail. Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili , Leqi Zhu  

2. Formal Barriers to Longest-Chain Proof-of-Stake Protocols
Jonah Brown-Cohen, Arvind Narayanan, Christos-Alexandros Psomas, S. Matthew Weinberg.
Manuscript, 2018.

3. Web-based Attacks to Discover and Control Local IoT Devices
Gunes Acar, Danny Yuxing Huang, Frank Li, Arvind Narayanan, Nick Feamster.
SIGCOMM Workshop on IoT Security and Privacy, 2018.
Blog post.

4. Majority is not Enough: Bitcoin Mining is Vulnerable∗ Ittay Eyal and Emin G¨un Sirer

5.  An empirical study of Namecoin and lessons for decentralized namespace design
Harry Kalodner, Miles Carlsten, Paul Ellenbogen, Joseph Bonneau, Arvind Narayanan.
WEIS 2015.
Blog post.

6. https://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf

7. Short Overview of Alternatives of PoW

8. EPaxos:  http://delivery.acm.org/10.1145/2520000/2517350/p358-moraru.pdf?ip=109.65.0.103&id=2517350&acc=OA&key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2EC42B82B87617960C&__acm__=1556294623_da160791f66c9d49abca2cd71d1c3bd5    https://www.youtube.com/watch?v=9Bvfy9pXXpk  

9. VMWare Blockchain, SBFT:  https://research.vmware.com/projects/vmware-blockchain   

10.   Revisiting Fast Practical Byzantine Fault Tolerance Ittai Abraham, Guy Gueta, Dahlia Malkhi VMware Research

11.   Concurrent Connected Components. Robert Tarjan talk:  https://www.univie.ac.at/ct/stefan/tarjan-ct-talk.pdf

12.   Symmetry Breaking with Noisy Processes, Seth Gilbert (National University of Singapore) and Calvin Newport (Georgetown University)

13.   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)

14.   Distributed MST and Routing in Almost Mixing Time, Mohsen Ghaffari (ETH Zurich), Fabian Kuhn (University of Freiburg) and Hsin-Hao Su (MIT)

15.   Analyzing Contention and Backoff in Asynchronous Shared Memory, Naama Ben-David (Carnegie Mellon University) and Guy Blelloch (Carnegie Mellon University)

16.   A Template For Implementing Fast Lock-free Trees Using HTM, Trevor Brown (University of Toronto)

17.   Deterministic Objects: Life beyond Consensus Yehuda Afek, Faith Ellen and Eli Gafni send me email if you want the pdf. AND

18.   Eli Daian Thesis (DISC 2018 paper, and presentation available).

19.   Life Beyond Set Agreement, David Yu Cheng Chan (University of Toronto), Vassos Hadzilacos (University of Toronto) and Sam Toueg (University of Toronto)

20.   Population protocols

21.   Gossip in a Smartphone Peer-to-Peer Network, Calvin Newport (Georgetown University)

22.   “Adaptive Software Cache Management”, Gil Einziger, Ohad Eytan, Roy Friedman, Benjamin Manes

23.   “The Gap Game”, Itay Tsabary, Ittay Eyal (Presenter: Itay Tsabary, University)

  1. Biological Distributed Algorithms

a.       New paper Gadi Taubenfeld (IDC) and Ziv Bar-Yoseph (CMU) 2019

b.      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/)

c.       Read about Ants Task Allocation, and other, and think of a new one.

d.      Can you do Neural Distributed Algorithms? Mimic network of neurons by a distributed network of cells?

e.       +Game theory between ant colonies, Competition or cooperation between ant colonies - in foraging, task allocation, and other problems?

f.        Consider other social insects (Bees, Bats, Rats, you name it).

 

  1. Multi-core programming:

a.       On the Complexity of Reader-Writer Locks, by Danny Hendler

b.      Analysing Snapshot Isolation" by Andrea Cerone_ Alexey Gotsman

c.       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 ).

d.      Practical concurrent programming issues you faced at work.

e.       A. Matveev, N. Shavit, P. Felber, P. Marlier Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming. SOSP 2015, Monterey, California, USA

f.        D. Alistarh, W. M. Leiserson, A. Matveev, N. Shavit ThreadScan Automatic and Scalable Memory Reclamation SPAA 2015

g.       A. Matveev, N. Shavit Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory. ASPLOS 2015, Istanbul, Turkey

  1. Game theory and distributed computing (see e.g. http://dl.acm.org/citation.cfm?id=2611481 ):

a.       Spanning tree or MIS with rational agents (or MST) (like the homework question about the senators).

b.      Variations on coloring problems (blinking, 2- neighbors coloring, etc)?

c.       Byzantine? Read the paper "Rational Consensus" Halpern Vilaca

 

  1. Models of Read/write message passing,

a.       Why Extension-Based Proofs Fail, Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili , Leqi  Zhu

  1. Biological Distributed Algorithms
    1. New paper Gadi Taubenfeld (IDC) and Ziv Bar-Yoseph (CMU) 2019
    2. 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/)
    3. Read about Ants Task Allocation, and other, and think of a new one.
    4. Can you do Neural Distributed Algorithms? Mimic network of neurons by a distributed network of cells?
    5. +Game theory between ant colonies, Competition or cooperation between ant colonies - in foraging, task allocation, and other problems?
    6. Consider other social insects (Bees, Bats, Rats, you name it).

 

  1. 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 ).