Problem 3.3 In a data center, it is critical to store information redundantly so

Question

Problem 3.3 In a data center, it is critical to store information redundantly so that no data is lost if a single hard drive fails. In this problem, we will examine a few methods1 for adding redundancy across the n hard drives in a single server rack: » No Redundancy: Each drive in a rack stores different data. Data is lost if one or more » Repetition: Each drive in a rack stores a copy of the same data. Data is lost only if all » Single Loss Recovery: The first n - 1 drives in a rack store different data and the last out of the n drives fail. n drives in the rack fail drive stores the XOR of the data from these drives. Data is lost if two or more out of the n drives fail. » Double Loss Recovery: This is a more complex scheme that can tolerate two drive failures. Data is lost if three or more out of the n drives fail Below, we have illustrated examples of the first three strategies for n 3 drives and the fourth strategy for n = 8 drives. The symbols b1, b2, b3, b4 refer to blocks of bits and thesymbol refers to the XOR operation No Redundancy Repetition Single Loss Recovery bi Double Loss Recovery 3 You may assume that drives fail independently of one another and the probability that a drive is working at the end of a day is p (a) For each of the four strategies described above, write down an expression for the probability that the rack loses no data at the end of the day. Your expressions should be in terms of n and p. Simplify as much as you can (b) Evaluate the probabilities from part (a) for n = 8 and p = 0.9. (c) To further increase the reliability, you have decided to maintain 3 identical copies of each rack. Using your expressions from part (a) as a building block, determine, for each of the four strategies, the probability that at least one of these three racks has lost no data at the end of the day (d) Evaluate the probabilities from part (c) for n = 8 and p = 0.9

Explanation / Answer

No Redundancy:

Data would be lost of 1 or more drive out of n drives fails. So, all should be working at the end of the day.

Required probability is pxpxpxpxp.....n times = pn

Repetition:

Data would be lost only if all fail. So, atleast one out of n should be working at the end of the day.

Required probability = pn + pn1(1p) + pn2(1p)2 + pn3(1p)3 + ....+p(1p)n1

Using Formula for Geometric Progression with Common Ratio as(1p) /p,

Required probability = pn {1 (1p)n /pn}/ {1 (1p)/p}

Single Loss Recovery:

Data is lost if two or more drives fail, so maximum of 1 drive can fail

Required Probability = pn + pn1(1p) = pn1

Double Loss Recovery:

Data is lost if three or more out of n drives fail. So, at max 2 drives could fail.

Required probability = pn + pn1(1p) + pn2(1p)2

     = pn1 + pn2(p2 2p + 1)

= pn pn1 + pn2

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.