CS435 - Distributed Systems
with Dr. Basit Qureshi

Tutorial 7
_____________
Read through this tutorial on Synchronization Algorithms.

_____________

1. Define Distributed Mutual Exclusion. What are the goals to achieve in any solution for this issue?[S 5]

2. Explain how a FIFO queue can help with a centralized algorithm. Why it causes a bottleneck? [S 8-13]

3. What is the "cost" of Lamport Mutual Exclusion algorithm in terms of communication? [S 24]

4. In a ring based algorithm, explain what happens when a node fails? Using the following figure, give a step by step illustration with messages. Assume node 24 (leader) crashed. Show communication between 15 and 24. [S37-45]



5. In bully algorithm, what gives if bully is not responsive?

6. Explain why maintaining a quorum is essential in concensus algorithms? [S 47-54]

7. Explain why managing network partitions is such a pain? [S 46]

8. Read the Paxos vs RAFT paper [pdf] Answer the following:

How does each algorithm handle leader election, and what are the implications of their respective approaches?

How do Paxos and Raft ensure consistency and data integrity in distributed systems, and what are the differences in their approaches to maintaining consistency?

Discuss the scalability characteristics of Paxos and Raft, including their ability to handle large-scale distributed systems and increasing numbers of nodes?

What are the recovery mechanisms employed by Paxos and Raft in the event of network partitions, and how do they ensure system resilience and consistency?