University of California, Santa Cruz, Spring 2024

The class will be on zoom on Thu 16, and Tue 21. Here is the zoom link

`removed`

Exam.

The exam will not include the following slides: 07.terminating-reliable-broadcast.pdf and 08.atomic-commit.pdf. It will include the following: 00.introduction.pdf, 01.reliable-broadcast.pdf, 02.causal-broadcast.pdf, 03.memory-regular.pdf, 04.memory-atomic.pdf, 05.Consensus.pdf, 06.total-order-broadcast.pdf, 09.bitcoin-intro.pdf, 10.byz-reliable-broadcast.pdf, and 11.byz-consensus.pdfThe paper schedule page:

`https://docs.google.com/spreadsheets/d/1BqN1j0i4DN_bStqrYNM16OCGO-UtWMRaYqbiXBxszQ8/edit#gid=0`

The links to submit the abstracts is in the sheet.

Recorded Lecture

Copy and paste the links to a browser

Recording 1:

`https://ucr.zoom.us/rec/share/MHIz_mPgPwzrzxQ_SZtwbWRHV4d_pzwc1ul5T2CfLJB1uoo9SZ7ZvNvVMHfasXM6.kVsw_nBR2jg05UGl`

Recording 2:

`https://ucr.zoom.us/rec/share/6OaVT7UG04il1YfNy3RlpPwistnL7aqUWfs_IZKn6I64N3qllwBJ9_afa-3SN0fi.qaGPG5DlHnyBf8sS`

There will be a midterm review session on May 17. TA will announce the location.

Distribution is ubiquitous in modern computing systems. For example, today’s telephone systems, banking systems, global information systems, and aircraft and nuclear power plant control systems all depend critically on distributed algorithms. Robust distributed algorithms should offer reliability and security despite process failures, network disconnections, or even malicious attacks on processes. This course will introduce fundamental distributed computing problems and provides a collection of applicable algorithms. It also presents formal specification and rigorous reasoning about distributed algorithms. The course follows a modular and layered approach to the implementation of distributed abstractions. It covers reliable broadcast, causal broadcast, total-order broadcast, distributed shared memory, consensus variants including blockchain consensus, atomic commit and terminating reliable broadcast, and replicated systems. The course considers processes that are subject to crashes and also malicious attacks by non-cooperating processes.

In this course, we will have both lectures by the instructor (in the first half of the class), and presentations by students (in the second half of the class). The presenter presents a paper or related papers and leads the discussion.

Instructor:

Mohsen Lesani

mlesani@ucsc.edu

TA:

Karthik Krishnaraj Bhat

kabhat@ucsc.edu

T/Th 3:20-4:55pm

Cowell 134

https://www.dropbox.com/scl/fo/0rsvypiv97ketway1hnh8/h?rlkey=mrpsf0b39qzcl1l4vc3k0zvrf&dl=0

Introduction to Reliable and Secure Distributed Programming

Christian Cachin, Rachid Guerraoui, Luís Rodrigues

Second Edition, Springer, 2011, XIX, 320 pages, ISBN-13: 978-3-642-15259-7

DOI: doi:10.1007/978-3-642-15260-3

http://distributedprogramming.net/index.shtml

TA:

Wednesday (In Person) 12pm - 1pm

Upper Floor/Level, Science and Engineering Library, Room 332

Friday (Zoom) 2.30pm - 3.30pm:

https://ucsc.zoom.us/j/6673631998?pwd=fvbxE7heYPstzHcJbSqlWXaetZLFxb.1

Passcode: yz74Ww

You can ask questions during the office hours, or post them on the discussion section on Canvas.

Instructor:

Please email me so that I know that you want to come to the office hours.

I am in most days. You can also email me and we can find a time to meet.

One Exam (midterm from lectures in the first half of the class): 50%. May 23 in the class

Presentation and discussion: 50%

Project: extra credit

We track attendance, and only those that attend regularly will get their grades scaled.

See sample questions in the section below Sample Questions.

We may have multiple lectures on a topic.

Please read the slides and suggested reading before the lectures.

Slides

Introduction Components, Process Abstraction, Communication Abstraction, Time Abstraction

Reading: Chapter 1 Sections 1.4, and Chapter 2 Sections 2.2, 2.4, 2.6 of the Textbook

Slides

Reading: Chapter 3 Sections 3.2, 3.3, 3.4, 3.9 of the Textbook

Slides

Reading: Chapter 3 Section 3.9 of the Textbook

Slides

Reading: Chapter 4 Sections 4.2 of the Textbook

Slides

Reading: Chapter 4 Sections 4.3, 4.4 of the Textbook

Slides

Reading: Chapter 2 Section 2.7, and Chapter 5 Section 5.1, 5.2, 5.3 of the Textbook

Slides

Reading: Chapter 6 Section 6.1, 6.2 of the Textbook

Slides

Reading: Chapter 6 Section 6.3 of the Textbook

Slides

Reading: Chapter 6 Section 6.6 of the Textbook

Slides

Reading: Chapter 6 Section 6.8 of the Textbook

Slides

Reading: Bitcoin A Peer-to-Peer Electronic Cash System. Nakamoto. White paper. 2008.

Slides

Reading: Chapter 3 Sections 3.10, 3.11, 3.12 of the Textbook

Slides

Reading: Chapter 5 Section 5.6 of the Textbook

Slides

The notion of conflict, and coordination minimization by graph optimization

1. May 14

A comprehensive study of Convergent and Commutative Replicated Data Types.

M. Shapiro, N. Preguica, C. Baquero, M. Zawirski.

2011.

2. May 14

Coordination Avoidance in Database Systems.

P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, I. Stoica.

VLDB 2014.

3. May 16

Checking Invariant Confluence, In Whole or In Parts.

M. Whittaker, J. M. Hellerstein

VLDB 20.

4. May 16

Hamsaz: Replication Coordination Analysis and Synthesis

Farzin Houshmand, Mohsen Lesani

POPL ’19 (ACM SIGPLAN Symposium on Principles of Programming Languages)

5. May 21 (This date has 3 presentation)

Efficient Numerical Error Bounding for Replicated Network Services.

VLDB 2001. Haifeng Yu, Amin Vahdat.

6. May 21

Hampa: Solver-aided Recency-Aware Replication

Xiao Li, Farzin Houshmand, Mohsen Lesani

CAV ’20 (International Conference on Computer-Aided Verification)

7. May 21

Hamband: RDMA Replicated Data Types

Farzin Houshmand, Javad Saberlatibari, Mohsen Lesani

PLDI ’22 (ACM SIGPLAN Conference on Programming Language Design

and Implementation)

May 23

Exam

8. May 28

Language-based Information-Flow Security.

A. Sabelfeld, A. C. Myers.

JSAC 2003

9. May 28

Secure Program Partitioning

S. Zdancewic, L. Zheng, N. Nystrom, A. C. Myers

TOCS 2002.

10. May 30

Hamraz: Resilient Partitioning and Replication

Xiao Li, Farzin Houshmand, Mohsen Lesani

S&P ’22 (IEEE Symposium on Security and Privacy)

11. May 30

Federated Byzantine Quorum Systems.

A. G. Perez, A. Gotsman

OPODIS 2018.

12. June 4

Deconstructing Stellar Consensus.

A. G. Perez, M. A. Schett

OPODIS 2019.

13. June 4

Quorum Subsumption for Heterogeneous Quorum Systems

Xiao Li, Eric Chan, Mohsen Lesani

DISC ’23 (The International Symposium on Distributed Computing)

14. June 6

Atomic cross-chain swaps

Maurice Herlihy

PODC 2018 (ACM symposium on principles of distributed computing. 2018)

15. June 6

Cross-Chain Transactions

Narges Shadab, Farzin Houshmand, Mohsen Lesani

ICBC ’20 (IEEE International Conference on Blockchain and Cryptocurrency)

See sample questions in the following folder.

- Exercise 1_Solution.pdf
- Exercise 1.pdf
- Exercise 2_Solution.pdf
- Exercise 2.pdf
- Exercise 3.pdf
- SampleQuestions1.pdf
- SampleQuestions2.pdf
- SampleSolutions1.pdf
- SampleSolutions2_part1.pdf
- SampleSolutions2_part2.pdf
- Spring2020_exam1_solution.pdf
- Spring2020_exam2_solution.pdf
- Spring2020_exam3_solution.pdf