Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.