Suppose that we would like to implement a distributed file system. There are mm files and nn servers to store the file. We want to spread the work load to the servers so that each one keeps approximate mn\frac{m}{n} files. One way to achieve this is by hashing. Let p≫mp \gg m be a prime number. Then

h(x)=ax+bmod  pmod  n h(x) = ax + b \mod p \mod n

gives us the desired property if a∈{1,2,...,p−1}a \in \{1, 2, ..., p -1\} and b∈{0,1,2,...,p−1}b \in \{0, 1, 2, ..., p - 1\} are selected uniformly at random.

The problem is that what if nn changes constantly?

Consider mapping the nn servers uniformly and independently to real numbers in [0,1][0, 1]. Let's divide [0,1][0, 1] into nn equally sized intervals [0,1/n][0, 1/n], [1/n,2/n][1/n, 2/n], ..., [(n−1)/n,1][(n - 1)/n, 1]. Now, for an interval that a particular server belongs, the probability that no server maps to the 2log⁡n2 \log n intervals to the left of this interval is given by

(1−2lognn)n−1≤e−2lognn(n−1)=1n2e2lognn≤en2 (1 - \frac{2 log n}{n})^{n - 1} \le e^{-\frac{2 log n}{n} (n - 1)} = \frac{1}{n^2} e^{\frac{2 log n}{n}} \le \frac{e}{n^2}

By union bound, this happens to some server is bounded by en\frac{e}{n}.

What is the probability that the interval between some pair of servers is O(1/n2)O(1 / n^2). If we divide [0,1][0, 1] into Θ(n2)\Theta(n^2) equally size intervals, by Birthday's Paradox, there is high probability that some interval contains two servers.