Instructions and Topics for Class Projects

Distributed Computing 2020:

Instructions:

  1. The projects are done in pairs.
  2. End of January and/or during Feb/March we will schedule to meet and go over the presentation and discuss each project.
  3. The idea is to take a topic (which would typically cover two or three tightly related papers), and to cover them briefly but in detail, and try to suggest either an improvement, a variation, or to suggest a problem with the papers.
  4. Each project should submit

a)      Two to three pages that summarize the research done, and

b)      15 minutes powerpoint presentation.

  1. The summary document should describe the topic in at most one a page, and describe your suggestions, observations, contributions in at most 2 more pages.
  2. The presentation should follow a similar outline.
  3. 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 about your selection and get an approval.

The deadline for the projects is End of January   

One option to find good topics is to go over the papers presented in (use google search) different years for the following conferences:PODC-2022 …. PODC-2019, PODC -2018 / PODC-2017/2016/2015, or DISC-2022 …. DISC 2019 DISC2018  OR  USENIX Security 2022  USENIX Security 2021  etc. (check for PODC 2023, when the list of accepted papers is announced).  Or search for SIGCOMM, SPAA, Infocom, SODA, etc., programs and published papers. 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 examples.  For each topic/paper use https://www.google.com  and https://scholar.google.com and similar sites and search engines to locate related paper, more up to date papers and publications.

 

  1. Theoretical Distributed Computing

LOOK AT: PODC-2022 …. PODC-2019, PODC -2018 / PODC-2017/2016/2015, or DISC-2022 …. DISC 2019 DISC2018

A.Blockchain Consensus related of interest

1.    Player Replaceability -- Part I

2.    Player Replaceability -- Part II

3.    Unknown participation

4.    Unknown Dynamic participation https://blog.chain.link/instant-finality-in-byzantine-generals-with-unknown-and-dynamic-participation/

5.    2. View Synchronization

6.    Fluctuating Participation

7.    Player Replacability

8.    Hotstuff paper

9.    5. Two round HOTSTUFF

10.                      6. Conider other topics from Decentralized thoughts

11.                      Book:  Foundations of Distributed Consensus and Blockchains  in particular Chp 15 or 16.

 

    1. https://dl.acm.org/doi/pdf/10.1145/2957760 Designing Self-Stabilizing Systems Using Game Theory LI-HSING YEN, National Chiao Tung University JEAN-YAO HUANG, National University of Kaohsiung VOLKER TURAU, Hamburg University of Technology
    2.  Dynamic Scheduling in Distributed Transational Memory Costas Busch ; Maurice Herlihy ; Miroslav Popovic ; Gokarna Sharma https://ieeexplore.ieee.org/abstract/document/9139858
    3. Revisiting Fast Practical Byzantine Fault Tolerance Ittai Abraham, Guy Gueta, Dahlia Malkhi VMware Research
    4. Communication Complexity of Byzantine Agreement, Revisited. Ittai Abraham, T-H.Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi. PODC 2019
    5. Asymptotically Optimal Validated Asynchronous Byzantine Agreement. Ittai Abraham,Dahlia Malkhi, Alexander Spiegelman. PODC 2019
    6. Scalable Byzantine Reliable Broadcast
      Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic and Dragos-Adrian Seredinschi. DISC 2019
    7. Concurrent Connected Components. Robert Tarjan talk:  https://www.univie.ac.at/ct/stefan/tarjan-ct-talk.pdf
    8. Symmetry Breaking with Noisy Processes, Seth Gilbert (National University of Singapore) and Calvin Newport (Georgetown University)
    9. 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)
    10. Deterministic Objects: Life beyond Consensus Yehuda Afek, Faith Ellen and Eli Gafni send me email if you want the pdf. AND
    11. Eli Daian Thesis (DISC 2018 paper, and presentation available).
    12. Life Beyond Set Agreement, David Yu Cheng Chan (University of Toronto), Vassos Hadzilacos (University of Toronto) and Sam Toueg (University of Toronto)
    13. How to Spread a Rumor: Call Your Neighbors or Take a Walk? George Giakkoupis,Frederik Mallmann-Trenn, Hayk Saribekyan, PODC 2019
    14. Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols.David Doty, Mahsa Eftekhari. PODC 2019
    15. On Counting the Population Size. Petra Berenbrink, Dominik Kaaser, Tomasz Radzik. Podc 2019
    16. Secure Distributed Computing Made Optimal. Merav Parter, Eylon Yogev. PODC 2019
    17. Optimal Memory-Anonymous Symmetric Deadlock-Free Mutual Exclusion. Zahra Aghaz-adeh, Damien Imbs, Michel Raynal, Gadi Taubenfeld, Philipp Woelfel. PODC 2019
    18. Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
      Merav Parter. DISC 2019
    19. Randomized Concurrent Set Union and Generalized Wake-Up. Siddhartha Jayanti, RobertE. Tarjan, Enric Boix-Adserŕ.  PODC 2019
    20. Monotonically relaxing concurrent data-structure semantics for increasing performance: An efficient 2D design framework
      Adones Rukundo, Aras Atalar and Philippas Tsigas. DISC 2019
    21. Putting Strong Linearizability in Context: Preserving Hyperproperties in Programs that Use Concurrent Objects
      Hagit Attiya and Constantin Enea.  DISC 2019
    22. Consensus with max registers
      James Aspnes and He Yang Er DISC 2019
    23. Population protocols
    24. Corona distribution process
    25. Why Extension-Based Proofs Fail. Dan Alistarh, James Aspnes, Faith Ellen, Rati

 Gelashvili , Leqi

 Zhu

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

·  More practical distributed computing

z.       Various Algorithms from Algorand, here:

aa.   Vitor Enes, Carlos Baquero, Tuanir França Rezende, Alexey Gotsman, Matthieu Perrin, Pierre Sutra:
State-Machine Replication for Planet-Scale Systems (Extended Version). CoRR abs/2003.11789 (2020) (talk video is available)

bb.  You may choose a topic(s) from https://decentralizedthoughts.github.io/ and after discussing with me, it and its related papers can be a project.

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

dd.  Breaking the O(n^2 ) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary. Valerie King ∗ Jared Saia †

ee.  Communication Complexity of Byzantine Agreement, Revisited. Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi.

ff.     HotStuff: BFT Consensus with Linearity and Responsiveness. Maofan Yin, Dahlia Malkhi,Michael K. Reiter, Guy Golan Gueta, Ittai Abraham PODC 2019

gg.   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 

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

ii.       The Impact of RDMA on Agreement. Marcos K. Aguilera, Naama Ben-David, RachidGuerraoui, Virendra Marathe, Igor Zablotchi.  PODC 2019

jj.      On the Parallels between Paxos and Raft, and how to Port Optimizations. Zhaoguo Wang,Changgeng Zhao, Shuai Mu, Haibo Chen, Jinyang Li.  PODC 2019

kk.   Implementing Mediators with Asynchronous Cheap Talk. Ittai Abraham, Danny Dolev,Ivan Geffner, Joseph Y. Halpern. PODC 2019

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

mm.                      Strongly Linearizable Implementations of Snapshots and Other Types. Sean Ovens, PhilippWoelfel. PODC 2019

·         Cyber Security

LOOK AT  USENIX Security 2022  USENIX Security 2021  etc. and other related conferences

a)      https://www.sivak.dev/projects/8-ferret

b)      https://dl.acm.org/doi/abs/10.1145/3387514.3405871

c)      https://team-cymru.com/blog/2022/03/08/record-breaking-ddos-potential-discovered-cve-2022-26143/

d)     https://www.m3aawg.org/

e)      https://www.cylab.cmu.edu/news/2022/08/26-eliminating-algorithmic-complexity-attacks.html

f)       https://dl.acm.org/doi/pdf/10.1145/3484266.3487369

g)      https://dl.acm.org/doi/abs/10.1145/3365609.3365863?casa_token=RX9vohlmya8AAAAA:8dkLy2uFIqlNqIwBQ6NVhOxwQfG_UpeiM06Vri5TbnedrWcOqSm_2bxuM2pg__imN_AflFq0L4Y

h)      https://www.oecd.org/sti/security-of-the-domain-name-system-dns-285d7875-en.htm

i)        https://www.usenix.org/conference/usenixsecurity21/presentation/moon

j)        https://www.oecd.org/sti/security-of-the-domain-name-system-dns-285d7875-en.htm

k)      https://lizizhikevich.github.io/assets/papers/ZDNS.pdf

l)        https://cyber-security-group.cs.tau.ac.il/

·  Blockchain

  1. https://scholar.google.com/citations?view_op=view_citation&hl=en&user=rejzeocAAAAJ&citation_for_view=rejzeocAAAAJ:u5HHmVD_uO8C
  2. https://dl.acm.org/doi/abs/10.1145/3433210.3460016
  3.  
    1.  

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

c.       Stellar Consensus by Instantiation
Eli Gafni, Giuliano Losa and David Mazičres  DISC 2019

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

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

f.        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.

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

h.      Short Overview of Alternatives of PoW

i.         Christian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas. 2018. Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang (Eds.). ACM, 913–930. https://doi.org/10.1145/3243734.3243848

j.        Jing Chen and Silvio Micali. 2019. Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci. (2019), 155–183.

Cyber security

    1. Thirty Years of DNS Insecurity: Current Issues and Perspectives
    2. OARConline 35a Preview
    3. Putting DNS in Context
    4. https://www.ripe.net/publications/docs/ripe-759
    5.  
    6. https://innovationisrael.org.il/kol-kore/5472
    7.  
    8. https://www.ndss-symposium.org/wp-content/uploads/2019/02/ndss2019_02B-2_Cetin_paper.pdf
    9.  
    10. https://dl.acm.org/doi/abs/10.1145/3419394.3423659 Putting DNS in Context
    11.  
    12. Articles with videos: 
    13.  
    14. https://dl.acm.org/doi/abs/10.1145/3419394.3423625
    15. https://dl.acm.org/doi/abs/10.1145/3419394.3423640
    16. https://dl.acm.org/doi/abs/10.1145/3419394.3423649
    17. https://dl.acm.org/doi/10.1145/3419394.3423623
    18. https://dl.acm.org/doi/10.1145/3419394.3423638
    19. https://dl.acm.org/doi/10.1145/3419394.3423659
    20.  
    21. https://www.ieee-security.org/TC/EuroSP2022/cfp.html
    22.  
    23. http://jianying.space/conference-ranking.html
    24.  
    25. https://www.nanog.org/events/nanog-82/agenda/?timezone=Asia/Jerusalem




    27. https://askubuntu.com/questions/542840/dns-points-to-the-right-ip-but-i-cant-ssh-based-on-dns
    28.  
    29. Google Public DNS blog  https://developers.google.com/speed/public-dns/faq#locations
    30. DNS Cache Poisoning Attack: Resurrections with Side Channels
    31. Digging Deeper – An In-Depth Analysis of a Fast Flux Network
    32. A First Look at the Consolidation of DNS and Web Hosting Providers
    33. https://labs.ripe.net/Members/anandb/expansion-of-ripe-nccs-anycasted-authoritative-dns-cluster
    34. https://arxiv.org/pdf/2006.15277.pdf
    35. https://arxiv.org/pdf/2007.00651.pdf
    36. https://www.isi.edu/~johnh/PAPERS/Moura20a.pdf
    37. https://ieeexplore.ieee.org/document/8023137
    38. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8440758 Classifying IoT Devices in Smart Environments Using Network Traffic Characteristics; Arunan Sivanathan , Hassan Habibi Gharakheili , Franco Loi, Adam Radford, Chamith Wijenayake , Arun Vishwanath , Senior Member, IEEE, and Vijay Sivaraman
    39. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7980220  IOT SENTINEL Demo: Automated Device-Type Identification for Security Enforcement in IoT;
    40.  
    41. https://groups.cs.umass.edu/ramesh/wp-content/uploads/sites/3/2020/07/sigcomm2020-final289.pdf
    42. 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.
    43. “Adaptive Software Cache Management”, Gil Einziger, Ohad Eytan, Roy Friedman, Benjamin Manes
    44. DNS security issues
    45. Onion and TOR
  1. Federated learning:
    1. Communication-efficient learning of deep networks from decentralized data‏, HB cMahan, E Moore, D Ramage, S Hampson, B Agüera y Arcas‏ Proceedings of the 20 th International Conference on Artificial Intelligence 

b.    Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. 2018. Byzantine Stochastic Gradient Descent. In NeurIPS.

c.    Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. 2017. Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent. In NIPS.

d.    El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. 2018. The Hidden Vulnerability of Distributed Learning in Byzantium. In ICML.

e.    Yudong Chen, Lili Su, and Jiaming Xu. 2017. Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent. In SIGMETRICS 2017.

f.     Jiashi Feng, Huan Xu, and Shie Mannor. 2014. Distributed Robust Learning. ArXiv abs/1409.5937 (2014).

g.    Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor-Yiing Su. 2014. Scaling Distributed Machine Learning with the Parameter Server. In BigDataScience ’14.

h.    https://arxiv.org/pdf/1905.04374.pdf   5/19  Fast and Secure Distributed Learning in High Dimension

i.      http://proceedings.mlr.press/v80/damaskinos18a/damaskinos18a.pdf    PMLR 2018  Asynchronous Byzantine Machine Learning (the case of SGD)

j.      https://arxiv.org/pdf/1705.08435.pdf      2/18  Personalized and Private Peer-to-Peer Machine Learning

k.    http://proceedings.mlr.press/v80/mhamdi18a/mhamdi18a.pdf    PMLR 2018  The Hidden Vulnerability of Distributed Learning in Byzantium

l.      https://arxiv.org/pdf/1802.07834.pdf   feb  2018  Learning to Gather without Communication

m.   https://arxiv.org/pdf/1805.11447.pdf   may 2018  Virtuously Safe Reinforcement Learning

n.    http://papers.nips.cc/paper/6617-machine-learning-with-adversaries-byzantine-tolerant-gradient-descent.pdf  nips 2017  Machine Learning with Adversaries:Byzantine Tolerant Gradient Descent

o.    http://papers.nips.cc/paper/6618-dynamic-safe-interruptibility-for-decentralized-multi-agent-reinforcement-learning.pdf  nips 2017  Dynamic Safe Interruptibility for DecentralizedMulti-Agent Reinforcement Learning

p.    https://arxiv.org/pdf/1703.02757.pdf   Byzantine-Tolerant Machine Learning 

q.    (https://dl.acm.org/citation.cfm?doid=3087801.3087861 brief announcement podc 17 Brief Announcement: Byzantine-Tolerant Machine Learning)

r.        http://openaccess.thecvf.com/content_CVPR_2019/papers/Liu_Rob-GAN_Generator_Discriminator_and_Adversarial_Attacker_CVPR_2019_paper.pdf

s.       http://proceedings.mlr.press/v97/chen19m/chen19m.pdf

t.        https://openreview.net/pdf?id=rk4Qso0cKm

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