2.49

Replication scheme.
Assign every data item to three different nodes in a cyclic way, so each node ends up with exactly three distinct items:

for item i in 0..999:    place replicas on nodes  i, (i+1) mod 1000, (i+2) mod 1000

This consumes all 3 000 available replica slots (1 000 items × 3 replicas) and keeps every item on three independent nodes.

Expected loss when 3 random nodes fail.
An item disappears only if its three replica nodes are exactly the three that fail.
Probability that one chosen triple of nodes is the failure set:
[math]P=\dfrac{1}{\binom{1000}{3}}=\dfrac{6}{1000\cdot999\cdot998}\approx6.0\times10^{-9}.[/math]
By linearity of expectation, the expected number of lost items is
[math]E=1000\cdot P=\dfrac{1000}{\binom{1000}{3}}\approx6.0\times10^{-6}.[/math]
So, with the proposed replication scheme, the average loss under three random node failures is essentially zero (about six-millionths of a single item).

Back to Chapter 2