MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would like to implement a form of consistent hashing using a set of permutations. The rules are as follows:

  • I have Y=~32 buckets and X items. Buckets may be "alive" or "dead". Items are to be distributed evenly across "alive" buckets, regardless of the subset of buckets which are alive. By distributed evenly I mean that the bucket with the most items will not have many more items than the bucket with the least items (hopefully a difference of at most 1 item).
  • To do this I want to generate permutations of the buckets - one permutation per item, such that each item will fall into the first "alive" bucket in that item's permutation.

From what I can gather, if each row is a permutation and we generate a table with X rows and Y columns - we want permutations with the following traits:

  • The first column should have (roughly) the same amount of appearances for each of the Y buckets.
  • Assuming a subset S of the buckets are dead, all permutations which begin with a subset T of S should have (roughly) the same amount of apearances for each of the Y buckets when observing the spots directly after (T) in each of these permutations. (T is obviously not necessarily the same subset of S for each permutation)

The questions are: Do there exist such permutations for X which is approximately equal to Y^2 or smaller, for a gap of at most 1 item between buckets in the worst case? For a gap of 2? Etc... If there do exist such permutations - how can they be built?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.