Distributed Systems 2020/21 spring

Seminar 10: Quorum-Based Protocols

---

Goal:

• Gifford's Scheme of Voting for supporting replicated writes
• Apply Gifford Quorum-Based protocol to a set of examples and look for Conflicts.

---

Definitions:

Quorum-Based Protocols:

• Resolves write-write or read-write conflicts
• Client processes are required to request and acquire the permission of multiple servers before reading and writing a replicated data item.
• Example protocol (on a distributed file system):
  • A process that wants to update a replicated file first contacts at majority of servers and get them to agree to do the update.
  • Once they agreed, the file is changed and a new version number is associated with the file.
  • To read a replicated file, a client must also contact at least half the servers plus one and ask them to send the version numbers associated with the file.
  • If all version numbers agree then the file is the most recent one.

Gifford's Scheme:

• N replicas exist.
• To read a file, a client needs to assemble a Read Quorum:
  • An arbitrary collection of any N_R servers.
• To write a file, a client needs to assemble a Write Quorum:
  • An arbitrary collection of any N_W servers
• Constraints: The values N_R and N_W are subject to following constraints:

1. . N_R + N_W > N
2. . N_W > {$ \frac{N}{2} $}
   • The first constraint prevents Read-Write conflicts
   • The second constraint prevents Write-Write conflicts

---

Examples:

Example 1: N = 12 , N_R = 3 , N_W = 10

A correct choice of read and write set

Example 2: N = 12 , N_R = 7 , N_W = 6

• A Write-Write conflict may occur because N_W <= {$ \frac{N}{2} $}.
• One client may choose (A, B, C, E, F,G) as its write set and another client may choose (D,H, I, J,K, L) as its write set.
• Trouble as the two updates will both be accepted without detecting that they actually conflict.

Example 3: N = 12 , N_R = 1 , N_W = 12

• Sets N_R to one, making it possible to read a replicated file by finding any copy and using it.
• Read-One, Write-All (ROWA).

---

EXERCISE Given below are the N, N_R, N_W, Where N denotes the total number of replica servers available; N_R denotes the read quorum and N_W denotes the write quorum. Against each, denote whether the combination is a correct choice or not using above mentioned constraints:

1. N = 5 , N_R = 2 , N_W = 4
2. N = 16 , N_R = 8 , N_W = 10
3. N = 16 , N_R = 9 , N_W = 8
4. N = 10 , N_R = 1 , N_W = 10
5. N = 11 , N_R = 4 , N_W = 5
6. N = 20 , N_R = 6 , N_W = 11

Deliverables of practical session: A PDF file containing the answers to above exercise

---

Referrences:

• Distributed Systems, Third edition, Version 3.02 (2018) by Maarten van Steen and Andrew S. Tanenbaum

---