Answer Happy

9. We have two mass storage devices, A and B with the same specs. Each can store N bits, but read/write operations are slow. We mitigate this problem by turning the two devices into a storage array: data is alternatingly written to A and B. The array can now store 2N bits, and read and write at almost twice the speed of the individual devices, assuming that the time it takes to send data to A and B is negligible, compared to the time it takes each device to write the data. There is however a flaw in this plan. Since data is distributed over two devices, the total chance of failure has now doubled. The failure of just one device causes the failure of the array. We could eliminate this problem by copying all of A's data redundantly to an additional devices C, and all of B's data to an additional device D. This insures against single and double drive failure, but at the cost of doubling the required amount of storage devices. We decide that simultaneous drive failure is sufficiently unlikely to ignore that possibility, and we will guard against data loss from single drive failure only. This requires only one extra device C, as follows: MAT 243 Week 1/7 Written Homework We abstract each device as a list of bits, A = a₁, a2₂, ..., aN, B = b₁,b2, ..., by and C = C₁, C2, ..., CN- Then for each k = 1...N, C stores Ck = ak XOR bk. Here, XOR is the bitwise exclusive or operation. (a) (2 points) With this scheme, if bit k fails on device A or B (not both), it can be reconstructed from bit k on device C. Explain. (b) (2 points) Would the same reconstruction property still hold if you used logical AND instead of XOR? Explain your answer. (c) (2 points) Would the same reconstruction property still hold if you used logical inclusive OR instead of XOR? Explain your answer.