Instructions
and Topics for Class Projects
Distributed
Computing 2020:
Instructions:
- The
projects are done in pairs.
- End
of June and/or during July we will schedule to meet and go over the
presentation and discuss each project.
- 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.
- Each
project should submit
a)
Two
to three pages that summarize the research done,
and
b)
15
minutes powerpoint presentation.
- 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.
- The
presentation should follow a similar outline.
- 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 July 10.
One option
to find good topics is to go over the papers presented in (use google search)
different years for the following conferences: PODC-2019, PODC -2018
/ PODC-2017/2016/2015, or DISC 2019 DISC2018 (check for PODC 2020, 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.
- Theoretical
Distributed Computing
- Revisiting
Fast Practical Byzantine Fault Tolerance Ittai
Abraham, Guy Gueta, Dahlia Malkhi
VMware Research
- Communication Complexity of Byzantine Agreement,
Revisited. Ittai Abraham, T-H.Hubert
Chan, Danny Dolev, Kartik
Nayak, Rafael Pass, Ling Ren, Elaine Shi. PODC
2019
- Asymptotically Optimal Validated Asynchronous
Byzantine Agreement. Ittai Abraham,Dahlia
Malkhi, Alexander Spiegelman. PODC 2019
- Scalable Byzantine Reliable Broadcast
Rachid Guerraoui,
Petr Kuznetsov, Matteo Monti, Matej Pavlovic and Dragos-Adrian Seredinschi. DISC
2019
- Concurrent Connected Components. Robert Tarjan talk: https://www.univie.ac.at/ct/stefan/tarjan-ct-talk.pdf
- Symmetry Breaking with Noisy Processes, Seth Gilbert
(National University of Singapore) and Calvin Newport (Georgetown
University)
- 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)
- Deterministic Objects: Life beyond Consensus Yehuda Afek, Faith Ellen and Eli Gafni
send me email if you want the pdf.
AND
- Eli Daian Thesis (DISC 2018
paper, and presentation available).
- Life Beyond Set Agreement, David Yu Cheng Chan
(University of Toronto), Vassos Hadzilacos (University of Toronto) and Sam Toueg (University of Toronto)
- How to Spread a Rumor: Call Your Neighbors or Take a
Walk? George Giakkoupis,Frederik
Mallmann-Trenn, Hayk Saribekyan,
PODC 2019
- Efficient Size Estimation and Impossibility of
Termination in Uniform Dense Population Protocols.David
Doty, Mahsa Eftekhari.
PODC 2019
- On Counting the Population Size. Petra Berenbrink, Dominik Kaaser,
Tomasz Radzik. Podc
2019
- Secure Distributed Computing Made Optimal. Merav Parter, Eylon Yogev. PODC 2019
- Optimal Memory-Anonymous Symmetric Deadlock-Free
Mutual Exclusion. Zahra Aghaz-adeh, Damien Imbs, Michel Raynal, Gadi Taubenfeld, Philipp Woelfel. PODC 2019
- Small Cuts and Connectivity Certificates: A Fault
Tolerant Approach
Merav Parter.
DISC 2019
- Randomized Concurrent Set Union and Generalized
Wake-Up. Siddhartha Jayanti, RobertE. Tarjan, Enric Boix-Adserà. PODC 2019
- Monotonically relaxing concurrent data-structure
semantics for increasing performance: An efficient 2D design framework
Adones Rukundo,
Aras Atalar and Philippas
Tsigas. DISC 2019
- Putting Strong Linearizability
in Context: Preserving Hyperproperties in Programs
that Use Concurrent Objects
Hagit Attiya
and Constantin Enea. DISC 2019
- Consensus with max registers
James Aspnes and He Yang Er
DISC 2019
- Population protocols
- Corona distribution process
- 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
- Revisiting Fast Practical Byzantine Fault Tolerance Ittai Abraham, Guy Gueta,
Dahlia Malkhi VMware Research
- HotStuff:
BFT Consensus with Linearity and Responsiveness. Maofan
Yin, Dahlia Malkhi,Michael
K. Reiter, Guy Golan Gueta, Ittai
Abraham PODC 2019
- 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
- “The Gap Game”, Itay Tsabary, Ittay Eyal (Presenter: Itay Tsabary,)
- The Impact of RDMA on Agreement. Marcos K. Aguilera, Naama Ben-David, RachidGuerraoui,
Virendra Marathe,
Igor Zablotchi.
PODC 2019
- On the Parallels between Paxos
and Raft, and how to Port Optimizations. Zhaoguo
Wang,Changgeng Zhao, Shuai Mu, Haibo Chen, Jinyang Li.
PODC 2019
- Implementing Mediators with Asynchronous Cheap Talk. Ittai Abraham, Danny Dolev,Ivan
Geffner, Joseph Y. Halpern. PODC 2019
- Gossip in a Smartphone
Peer-to-Peer Network, Calvin Newport (Georgetown University)
- Strongly Linearizable
Implementations of Snapshots and Other Types. Sean Ovens, PhilippWoelfel. PODC 2019
- Blockchain
- Formal Barriers to
Longest-Chain Proof-of-Stake Protocols
Jonah Brown-Cohen, Arvind Narayanan, Christos-Alexandros Psomas, S. Matthew Weinberg.
Manuscript, 2018.
- Stellar Consensus by Instantiation
Eli Gafni, Giuliano Losa
and David Mazières DISC 2019
- VMWare
Blockchain, SBFT: https://research.vmware.com/projects/vmware-blockchain
- Majority is not Enough: Bitcoin Mining is Vulnerable∗ Ittay Eyal and
Emin G¨un Sirer
- 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.
- https://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf
- Short
Overview of Alternatives of PoW
- 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
- Jing Chen and Silvio Micali.
2019. Algorand: A secure and efficient
distributed ledger. Theor. Comput.
Sci. (2019), 155–183.
- Cyber
security
- 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.
- “Adaptive Software Cache
Management”, Gil Einziger, Ohad
Eytan, Roy Friedman, Benjamin Manes
- DNS security issues
- Onion and TOR
- Federated
learning:
- 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
- Game
theory and distributed computing (see e.g. http://dl.acm.org/citation.cfm?id=2611481
):
- Spanning tree or MIS with rational agents (or MST)
(like the homework question about the senators).
- Variations on coloring problems (blinking, 2-
neighbors coloring, etc)?
- Byzantine? Read the paper "Rational
Consensus" Halpern Vilaca
- Multi-core
programming:
- On the Complexity of Reader-Writer Locks, by Danny Hendler
- Analysing Snapshot Isolation" by Andrea Cerone_ Alexey Gotsman
- 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
).
- Practical concurrent programming issues you faced at
work.
- A. Matveev, N. Shavit, P. Felber, P. Marlier Read-Log-Update:
A Lightweight Synchronization Mechanism for Concurrent Programming.
SOSP 2015, Monterey, California, USA
- D. Alistarh, W. M. Leiserson, A. Matveev, N. Shavit ThreadScan Automatic and Scalable Memory Reclamation
SPAA 2015
- A. Matveev, N. Shavit Reduced
Hardware NOrec: A Safe and Scalable Hybrid
Transactional Memory. ASPLOS 2015, Istanbul, Turkey
- A Template For Implementing
Fast Lock-free Trees Using HTM, Trevor Brown (University of Toronto)
- Analyzing Contention and Backoff
in Asynchronous Shared Memory, Naama Ben-David (Carnegie
Mellon University) and Guy Blelloch (Carnegie
Mellon University)
- Biological
Distributed Algorithms
- New paper Gadi Taubenfeld (IDC) and Ziv
Bar-Yoseph (CMU) 2019
- 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/)
- Read about Ants Task Allocation, and other, and think of a new one.
- Can you do Neural Distributed Algorithms? Mimic
network of neurons by a distributed network of cells?
- +Game theory between ant colonies, Competition or
cooperation between ant colonies - in foraging, task allocation, and
other problems?
- Consider other social insects (Bees, Bats, Rats, you
name it).