Their definition of "minimal disruption" seems really off to me. In distributed storage systems, it's not necessary for keys to be either left alone or reassign

Their definition of "minimal disruption" seems really off to me. In distributed storage systems, it's not necessary for keys to be either left alone or reassigned only to the new bucket when a bucket is added. Other reassignments are perfectly valid, even if they're usually undesirable (part of a balancing act that I'll get to in a moment). Similarly, their definition of balance as equal probability seems unduly restrictive. Yes, it's desirable, but has to be weighed against the cost of reassignment. What they've done is set up an overly restrictive set of inclusion criteria, while ignoring the metrics that actual practitioners would use to compare hashing methods. (1) Total number of reassignments when a bucket is added. Note that this can be minimized independently of whether those reassignments are only to the new bucket or include others as well. They're orthogonal properties. (2) Number of reassignment destinations when a bucket is removed. Sometimes you want this to be low and sometimes you want it to be high, but it's rarely something you can ignore. (3) Load associated with reassignments. Perfect balance (in the authors' sense) has to be weighed against the cost of reassignment, which can be high for storage applications. Depending on this cost and the rate of change, sometimes it's better to reach approximate balance and then leave things alone. I've worked on systems that over-optimized for perfect balance, and the results weren't good. Perhaps this work is more applicable to something like load-balancing requests. For storage, it basically seems to be missing the point. IMO they should have left storage out of their introduction.