Problem 3.2 In a data center, it is critical to store information redundantly so
ID: 3042262 • Letter: P
Question
Problem 3.2 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 methods 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 out of the n drives fail. Repetition: Each drive in a rack stores a copy of the same data. Data is lost only if all n drives in the rack fail. . Single Loss Recovery: The first n - 1 drives in a rack store different data and the last 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 n3 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 b3 bi bi Double Loss Recovery bi 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 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.9Explanation / Answer
Back-up Theory
Given drives fail independent of each other, implies that probability of two or more drives failing is the product of individual failure probabilities. ………………………………(1)
Probability of at least one failure = 1 – probability of no failure ………………………(2)
Given probability a drive works at the end of the day = p, probability it fails = 1 – p ….(3)
Part (a)
No Redundancy:
Probability rack loses no data at the end of the day
= 1 - P(one or more out of n drives in the rack fail)
= 1- P(at least one out of n drives in the rack fail)
= 1 – {1 – P(None of n drives fails) [by (2) above]
= P(None of n drives fails)
= P(All n drives work)
= pn [by (1) above] ANSWER 1
Repetition:
Probability rack loses no data at the end of the day
= P(one or more out of n drives in the rack work)
= 1- P(none out of n drives in the rack work)
= 1 – P(all of n drives in the rack fail)
=1 – (1 – p)n [by (2) and (1) above] ANSWER 2
Single Loss Recovery
Probability rack loses no data at the end of the day
= 1 - P(two or more out of n drives in the rack fail)
= 1- {1 - P(none out of n drives in the rack fail) - P(exactly one out of n drives in the rack fails)}
= P(none out of n drives in the rack fail) + P(exactly one out of n drives in the rack fails)
= pn + n(1 - p)pn - 1
= pn – 1(p + n – np)
= pn – 1{n – p(n - 1)} ANSWER 3
Double Loss Recovery
Probability rack loses no data at the end of the day
= 1 - P(three or more out of n drives in the rack fail)
= 1- {1 - P(none out of n drives in the rack fail) - P(exactly one out of n drives in the rack fails) - P(exactly two out of n drives in the rack fails)}
= P(none out of n drives in the rack fail) + P(exactly one out of n drives in the rack fails)
+ P(exactly one out of n drives in the rack fails)
= pn + n(1 - p)pn – 1 + {n(n - 1)/2}(1 - p)2pn – 2
= pn – 2[p2 + {n(1 - p)p} + {n(n - 1)/2}(1 - p)2] ANSWER 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.