# Clarification reg. jump consistent hashing

I was reading the paper on Jump consistent hashing, and I'm having some trouble understanding one particular line (page 5, paragraph 2)

"Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+1) / i."

My understanding is that:

• P(j ≥ i) is the probability that a key "jumps"/moves to a different bucket after bucket#i
• r is a pseudo random number between [0, 1) with a uniform distribution
• b is the last bucket# for which a jump occurred for this key

In particular, I am having trouble understanding this phrase: "we set P(j ≥ i) iff".

Set it to what? Do they mean to say "We want a key to jump to a different bucket ≥ i with a random probability r. This means that P(j ≥ i) ≥ r, which implies that (b+1)/i ≥ r. Hence the smallest such bucket number is obtained by the equation i = floor((b+1)/r)"?

• Yeah, that phrase makes no sense. Errors happen. I guess you'll have to reconstruct their reasoning from context. The "we set (j ≥ i) iff" can't be right, and similarly in the next two sentences.
– D.W.
Commented Aug 15, 2018 at 17:51
• @D.W. Thank you. I guess there is no good way of knowing what the authors meant unless they publish a new revision, or I'm able to reach out to one of them (which seems unlikely). Commented Aug 15, 2018 at 18:56
• I think it's a great question for this site; maybe someone here will work through their logic, reconstruct the gaps, and explain in an answer.
– D.W.
Commented Aug 15, 2018 at 20:14
• Today it's really hard to find someone who CAN'T be reached :) First author has profiles on linkedin and google+, I don't even checked the second one. Commented Aug 15, 2018 at 23:12
• I did find them on LinkedIn, but I had to send them a connection invite. I'm not so sure they'll accept. :) I'm sure they're swamped with many requests every day. Commented Aug 17, 2018 at 0:06

I suggest this as a better version of the paragraph.

Now, for a given $i$ and $k$, we generate a pseudo­random variable, $r$, that is uniformly distributed between 0 and 1, and set $j = \lfloor(b+1) / r\rfloor$. This gives $P(j \ge i) = (b+1) / i$, as we want:
$P(j \ge i)$
$= P(\lfloor(b+1) / r\rfloor ≥ i)\quad$ substituting the definition of j
$= P((b+1) / r \ge i)\quad$ because $i$ is an integer
$= P(r \le (b+1) / i)\quad$ solving the inequality for $r$
$= (b+1) / i\quad$ because $r$ is uniformly distributed between 0 and 1

• Thank you for responding Mr. Lamping.<br /> 1. "Now, for a given k and j" -> Do you mean for a given i and j? 2. While this is easier to follow mathematically, I'm still having a hard time understanding the intuition behind setting j = floor((b+1)/r)? What is the relation between j, b, r (a randomly chosen number)? Commented Aug 18, 2018 at 0:47
• Or put in a different way, how does sampling from k (k = number of keys) uniform distributions result in the selection of 1/(j+1) keys being moved? Kindly excuse my ignorance in case my probability theory is not up to the mark. :) Commented Aug 18, 2018 at 0:59
• I see this explanation in page 4, para 1: "In order to jump for the right fraction of keys, it uses a pseudo­random number generator with the key as its seed. To jump for 1/(j+1) of keys, it generates a uniform random number between 0.0 and 1.0, and jumps if the value is less than 1/(j+1)." Do the samplings of k independent uniform distributions themselves form a uniform distribution (X)? Is that the piece I'm missing? Because if they do, then I understand that P(X ≤ 1/(j+1)) = 1/(j+1) [because X is a uniform distribution, and P(X ≤ T) = T]. Meaning that 1/j+1 are expected to be chosen. Commented Aug 18, 2018 at 1:18
• Caught again! it now reads "for a given i and k". It's trying to say that you should generate a new r for computing each jump. Perhaps saying just that would be simpler. I don't have a great intuition about the formula. I got to it by working the derivation backwards. For an intuition for why is is roughly right, you know that the next jump should be to something on the order of 2*(b+1), and since r is 1/2 on average, (b+1)/r will be on the order of 2*(b+1). P.S. I find it quite disappointing that we couldn't find a shorter explanation for 10 lines of code! Commented Aug 18, 2018 at 1:33
• Thank you! The statement about next jump being in the order of 2*(b+1) provides a much better intuition to me as to why the algo works. Commented Aug 20, 2018 at 16:36