Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97, 1997 · paper · Computer science
Describes caching protocols for large networks that relieve hot spots on the Web, built on consistent hashing, a hash function that changes minimally as its range changes. The protocols let users work without a current or consistent view of the network.
Checked: PDF from cs.princeton.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
5 findings
Substance Theorem 8.1 states "then with probability 1/N , the bound on the rate of new requests per cache ... is", whereas the paper's high-probability bounds hold with probability at least 1 − 1/N.
- p. 10 Theorem 8.1
then with probability 1/N , the bound on the rate
- p. 10 Theorem 8.1
then with probability 1/N , the bound on the
- p. 3 Section 2, Objective
“with probability at least 1 − 1/N”
- p. 10 Theorem 8.1
then with probability 1/N , the bound on the rate of new requests per cache
Judge's note: Page 10 image, Theorem 8.1, shows 'with probability 1/N'. Page 3 defines 'with high probability' as 'with probability at least 1 − 1/N', and Theorem 3.1 (page 4), from which Theorem 8.1 is obtained by plugging in, holds with probability at least 1 − 1/N. An upper bound that holds only with probability 1/N would be nearly vacuous, so '1 −' appears to have been dropped. Lemma 3.3's '1/N' is a lower-bound (tightness) statement and does not explain this.
Second check: another model agreed
Report a problem with this finding
Substance Theorem 3.4 bound '2ρ log_d C + O((kqN(d+ρ))^{1/k}(1 + ρ/k + dq/log(kdq/ρ) + ρ/log k))' becomes, at k = log N, smaller than the Theorem 3.1 bound that Lemma 3.3 says is tight; a factor (probably k) seems to be missing.
- p. 5 Theorem 3.4
O((kqN(d+ρ))^{1/k}(1+ρ/k+dq/log(kdq/ρ)+ρ/log k))
- p. 5 Corollary 3.5
The high probability bound proved in theorem 3.1 for the number of requests a cache gets holds even if h is selected from a log N-universal hash family.
Only the authors can say what is right here.
Judge's note: Page 5 image confirms the printed bound. With k = log N, (kqN(d+ρ))^{1/k} = O(1), assuming q, d and ρ are polynomial in N, because N^{1/log N} = 2. The bound then reads 2ρ log_d C + O(1 + ρ/log N + dq/log(dq log N/ρ) + ρ/log log N). Theorem 3.1 has ρ log N/log log N and dq log N/log(...) in place of these terms. A fully random h belongs to every k-universal family, so a bound under k-universality cannot be below the Lemma 3.3 lower bound Ω(ρ log_d C + ρ log N/log log N + dq log N/log(...)). As printed, the theorem contradicts Lemma 3.3. Multiplying the bracket by k restores agreement with Theorem 3.1, which fits Corollary 3.5. The proof is deferred to the full paper, so only the authors can confirm the intended form.
Second check: another model agreed
Report a problem with this finding
Substance The proof of Theorem 3.1 says "The preceding lemma tells us that n_j ... is at most 2R/2^j except for j = 0", but Lemma 3.2 ("at least qx requests is at most 2R/x if x > 1") yields 2qR/2^j, and only when 2^j > q. The bound 2R/2^j is false when 2^j ≤ q (the range is also printed as "0 ≤ qj ≤ log dq − 1").
- p. 5 Lemma 3.2
at least qx requests is at most 2R/x if x > 1
- p. 5 Paragraph immediately following Lemma 3.2
is at most 2R/2ʲ except for j = 0
- p. 5 Requests to Internal Nodes, paragraph after Lemma 3.2
is at most 2R/2^j except for j = 0
- p. 5 Lemma 3.2
The total number of internal nodes which receive at least qx requests is at most 2R/x if x > 1
Only the authors can say what is right here.
Judge's note: Checked the page 5 image. Page 3 describes the protocol: a cache that has already made q requests for a page makes no more, so it forwards up to q requests. Page 5 says the count holds for "any arbitrary arrangement of paths", so the claim is deterministic. Setting qx = 2^j gives x = 2^j/q, so the lemma bounds the count by 2R/x = 2qR/2^j, and only for 2^j > q. My counterexample, following reviewer 1: q = 2, R = 2, and both requests for one page pass through the same leaf of a binary tree of depth 4. Each of the 3 non-root internal nodes on that path receives both requests, because the counter is below q when each arrives. So n_1 ≥ 3, but the printed bound is 2R/2 = 2. The final sum uses C/n_j ≥ 2^j/(2ρ) to get the log((dq/ρ) log N) denominator in Theorem 3.1. That internal-node term is therefore left without a valid proof as printed. I have not determined whether the theorem itself still holds.
Second check: another model agreed
Report a problem with this finding
Substance Theorem 4.5 states "λ(b) ≤ (1+√(4C/tI)) tI log(2NVI)/C2." (a stray "2"; the proof defines λ with denominator C). The stated load bound also places no restriction on tI relative to C, and it fails when tI ≪ C.
- p. 8 Theorem 4.5 statement vs proof
tI log(2NVI)/C2.
- p. 8 Proof of Theorem 4.5, definition of λ
tI log(2NVI) / C
- p. 8 Theorem 4.5
each of the following hold with probability at least 1 − 1/N
- p. 8 Proof of Theorem 4.5, definition of λ
λ = (1 + √(4C/(tI))) tI log(2NVI)/C
Only the authors can say what is right here.
Judge's note: The page 8 image shows the statement ending "/C2.", while the proof defines λ = (1+√(4C/tI)) tI log(2NVI)/C. Page 6 defines the load as λ(b) = |∪_V f_V^{-1}(b)|. Theorem 4.5 does not assume I = C; that assumption belongs to Theorem 4.1. I checked reviewer 3's instance: one view equal to B (t = 1, V = 1), I = 1, C = 10^6, N = 10^12. The bound is about 0.082 with base-2 logs (smaller with natural logs, and smaller again if read as /C²), so it asserts λ(b) = 0. But the item lands in b with probability 1/C = 10^-6, which exceeds the allowed failure probability 1/N = 10^-12. The proof's intermediate claim fails on the same instance: b is among the first t log(2NVI) ≈ 41 buckets with probability about 41/10^6, far above 1/(2NVI). The Chernoff step needs δ = √(4C/tI) ≤ 1, or a large-deviation form. So the theorem is wrong as printed without a parameter restriction.
Second check: another model agreed
Report a problem with this finding
Reference or label Wrong section pointer: 'Rather, in Section 4.4 we define a “ranged hash function”'; the definition is in Section 4.1 (Definitions).
- p. 6 Section 4 intro, last paragraph
Rather, in Section 4.4 we define a “ranged hash function”
- p. 6 Section 4.1 Definitions
A ranged hash function is a function of the form
- p. 6 end of Section 4 introduction
in Section 4.4 we define a “ranged hash function”
Judge's note: Page 6 image: Section 4.1 'Definitions' defines the ranged hash function, balance, monotonicity, spread and load. Page 7 shows that Section 4.4 is 'Some Theorems on Consistent Hashing', which the same paragraph correctly cites for 'other aspects'.
Second check: another model agreed
Report a problem with this finding
37 minor (typos and the like; most checked by the judge only)
Wording ρ is defined in Section 2 as "R = ρC where ρ is a constant" (requests per cache), but Theorem 4.1(3) reuses it as "If the number of views V = ρC for some constant ρ".
- p. 3 Section 2 Model
R = ρC where ρ is a constant
- p. 7 Theorem 4.1 item 3
If the number of views V = ρC for some constant ρ
Judge's note: Page 3 Section 2 and page 7 Theorem 4.1 item 3 both show ρ. In the theorem, ρ is locally quantified ('for some constant ρ'), so the statement is not wrong. However, the symbol now names a different quantity from the model-wide ρ. This is a notation-overload observation.
Second check: another model agreed
Report a problem with this finding
Wording Symbol t is defined in Section 2 as the constant where "each machine is aware of a 1/t fraction of the caches", and Section 7 reuses it: "Choose a parameter t, and simultaneously send t requests for the page".
- p. 9 Section 7, after Lemma 7.1
Choose a parameter t, and simultaneously send t requests for the page.
- p. 3 Section 2
each machine is aware of a 1/t fraction of the caches for some constant t
- p. 9 Section 7, paragraph after Lemma 7.1
Choose a parameter t, and simultaneously send t requests
- p. 3 Section 2
aware of a 1/t fraction of the caches
Judge's note: Page 3 image (Section 2, 1/t fraction for some constant t) and page 9 image (Section 7, t = number of simultaneous requests, said to be logarithmic). Section 7 still refers to views ('a specified fraction s of the machines in every view'), so the two meanings can be confused. This is a notation clash, not an error in any result.
Second check: another model agreed
Report a problem with this finding
Wording The protocol caches when "the counter reaches q" (Sec 3.1), but Sec 3.2.3 and the proof of Lemma 3.6 count pages/nodes receiving "more than q requests".
- p. 4 Section 3.1 Protocol, Cache rule
If the counter reaches q, it caches a copy of the page.
- p. 5 Section 3.2.3 Storage
the number of pages for which it receives more than q requests.
Judge's note: Page 4 Cache rule: 'If the counter reaches q, it caches a copy'. Page 5 Sec 3.2.3: 'number of pages for which it receives more than q requests'. The Lemma 3.6 proof says 'cached only if it requested q times' and also 'weight of one if it gets more than q requests'. This is an off-by-one wording inconsistency that has no asymptotic effect.
Second check: another model agreed
Report a problem with this finding
Wording Sec 3.2 opens with "The analysis of swamping runs much the same way, except that the 'weights' on our abstract nodes are now the number of requests ... As above, ..." before any analysis or definition of weights it could refer to.
- p. 4 Section 3.2 Analysis, second paragraph
The analysis of swamping runs much the same way, except that the “weights” on our abstract nodes are now the number of requests
Only the authors can say what is right here.
Judge's note: Page 4 image: the paragraph comes right after the three-part overview. 'Abstract nodes' and their 'weights' are introduced only later, in 3.2.2, so 'much the same way' and 'As above' have no antecedent. The paragraph appears misplaced, and only the authors can say where it belongs.
Second check: another model agreed
Report a problem with this finding
Wording Lemma 6.2 prints the total storage as "O(R/q log R log_d C log C)", a product. Section 6.2 promises "only a log(C) blowup" over Lemma 3.6's O(log R log_d C + R/q), and Lemma 6.2's per-cache bound O(log C(ρ/q + log R)) is exactly log C times Lemma 3.6's.
- p. 9 Lemma 6.2
is O(R/q log R log_d C log C)
- p. 5 Lemma 3.6
is O(log R log_d C + R/q)
- p. 9 Section 6.2
we have only a log(C) blowup in the bound.
- p. 9 Theorem 6.1
log C(ρ(8 log_d C + O(
Only the authors can say what is right here.
Judge's note: Page 9 image (Lemma 6.2, Section 6.2 text) and page 5 image (Lemma 3.6); page 8 Lemma 5.2 has the parallel form σλ(log R log_d C + R/q). The product form looks like a missing '+' (expected log C(log R log_d C + R/q)). It is still a valid but looser upper bound, so only the authors can say which was meant. The second point raised (constant 8 in Theorem 6.1 against 2 in Theorem 3.1) is not a defect: 'log(C) blowup' is an asymptotic statement and constants in a proof sketch need not carry over. The 'repeated log' text-rule hit is an extraction artefact.
Second check: another model agreed, code check
Report a problem with this finding
Wording Section 6.2 says "the latency will be no more than the depth of the tree, logd C, times the latency between the browser and the server", but Section 3.2.1 counts latency as "twice the length of the path, 2 logd C".
- p. 9 Section 6.2 Analysis
the latency will be no more than the depth of the tree, logd C, times the latency between the browser and the server.
- p. 4 Section 3.2.1
the latency is twice the length of the path, 2 logd C.
Judge's note: Page 4 image (Section 3.2.1: round trip counted as 2 log_d C) and page 9 image (Section 6.2: log_d C times δ). Under the ultrametric each hop is at most δ(browser, server), so a round trip gives at most 2 log_d C·δ. The 6.2 bound matches only if latency there means one-way, which the paper does not say. The difference is a constant factor, so this is a wording inconsistency only.
Second check: another model agreed
Report a problem with this finding
Wording After Theorem 8.1 (leading term γ(2 log_d C / C + ...)) the text says the load decreases with m "but never below Ω(γ log C/C)", dropping the base d while the same paragraph varies d.
- p. 10 Discussion after Theorem 8.1
but never below Ω(γ log C/C).
- p. 10 Theorem 8.1
2 log_d C / C
- p. 10 text after theorem
Ω(γ log C/C)
- p. 4 after Theorem 3.1
is the average number of requests per cache
Judge's note: Page 10 image. The factor 2 is consistent with Theorem 3.1 (page 4 prints 2ρ log_d C with ρ = R/C = γτ/C), so the claim that the factor 2 is spurious is wrong. The stated floor, however, uses log C instead of log_d C. These agree only when d is treated as a constant, and the paragraph immediately discusses increasing d. This is a minor imprecision.
Second check: another model agreed
Report a problem with this finding
Wording p.7, Section 4.3: "At first we choose the largest x such that 1/2^x ≤ 1/κC log(C)". The set of such x has no largest element; the smallest x (or the largest x with 1/2^x ≥ 1/κC log(C)) seems intended.
- p. 7 Section 4.3, last paragraph
At first we choose the largest x such that 1/2^x ≤ 1/κC log(C).
- p. 7 Section 4.3 Implementation, last paragraph
first we choose the largest x such that 1/2^x ≤ 1/κC log(C)
Only the authors can say what is right here.
Judge's note: The page image shows the text as quoted. My own reworking: 1/2^x decreases in x, so if some x satisfies the inequality, every larger x does too, and no maximum exists. For example, with bound 1/1000, x=10 gives 1/1024 ≤ 1/1000, and x=11,12,... also qualify. The intended segment length of about 1/(κC log C) needs the smallest such x. The O(1) expected-time claim still holds under the evident fix, so the step is faulty but the result stands.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Theorem 5.1 (p.8): "each abstract node sends out up to q′ requests to its parent". The symbol q′ is never defined; two sentences earlier each node "sends out at most qσ requests".
- p. 8 Proof of Theorem 5.1
sends out up to q′ requests to its parent
Only the authors can say what is right here.
Judge's note: The page image shows q′ (the text layer gives "q 0"). C′ is defined as C/t in this proof, but q′ is not defined anywhere, so presumably q′ = qσ. Only the authors can confirm this.
Second check: another model agreed
Report a problem with this finding
Wording The intuition in the proof of Theorem 6.1, "with probability O((log_d i)/i). Summing over i, the expected load on m is O(log C)", is off by a factor: Σ_{i≤C} (log_d i)/i = Θ(log C · log_d C).
- p. 9 Proof of Theorem 6.1, second paragraph
Summing over i, the expected load on m is O(log C).
- p. 9 Proof of Theorem 6.1, paragraph spanning the columns
with probability O((log_d i)/i)
- p. 9
log C (( log d C + O ( log N log log N )) + O ( dq log N
Only the authors can say what is right here.
Judge's note: Checked the page 9 image. Σ_{i≤C} ln i/(i ln d) ≈ (ln C)^2/(2 ln d), which is Θ(log C · log_d C), not O(log C). The formal argument just below (O(log_d C) per cluster, summed over log C clusters) and the statement of Theorem 6.1 (log C(ρ(8 log_d C + ...))) both give the log C · log_d C order. So the stated result stands and only this intuitive summation line is faulty. Reviewer 5's 'repeated log' is a text-layer artefact: the image reads "log C(ρ(8 log_d C", which is not a duplicated word.
Second check: another model agreed, code check
Report a problem with this finding
Wording Lemma 7.1 ("Suppose that d = Ω(log N). With high probability, the fraction of abstract-tree leaves that have a working path to the root is Ω(s^{log_d C})") states no condition tying s to d. When s ≤ 1/d, all root children are down with constant probability.
- p. 9 Section 7, fault assumptions
a specified fraction s of the machines in every view must be up
- p. 9 Lemma 7.1
Suppose that d = Ω(log N).
- p. 9 Lemma 7.1
the fraction of abstract-tree leaves that have a working path to the root is Ω(s^{log_d C})
Only the authors can say what is right here.
Judge's note: Checked the page 9 image. Section 7 lets the adversary fix a fraction s of working machines without seeing the random bits. Lemma 7.1 has no proof beyond 'trivial (using standard Chernoff bounds)'. With s = 1/d, the d root children all land on failed caches with probability (1−1/d)^d → 1/e, and then no leaf has a working path. That contradicts a positive lower bound holding with high probability. With fixed constants in Ω(log N), this works for every constant multiple. If s is meant to be a fixed constant, the constant in d = Ω(log N) must depend on s. The paper does not say this, so the authors should state the restriction. Graded minor because the 'In particular' case s = 1 − O(1/log_d C) is unaffected.
Second check: another model agreed
Report a problem with this finding
Wording "Increasing q seems only to hurt, suggesting that we should always take q = 2": if the bound only gets worse as q grows, the smallest q would be q = 1, and no reason is given for excluding it.
- p. 10 Discussion after Theorem 8.1
Increasing q seems only to hurt, suggesting that we should always take q = 2.
- p. 10 after Theorem 8.1
suggesting that we should always take q = 2
Only the authors can say what is right here.
Judge's note: Page 10 image (discussion after Theorem 8.1) and page 4 image (Cache protocol: the cache stores the page when its counter reaches q, so q = 1 is allowed). A text search found no stated constraint q ≥ 2. Only the authors can say why q = 2 is chosen over q = 1.
Second check: another model agreed
Report a problem with this finding
Typo Footnote 1 email list "{karger,e lehman,danl,ftl,mslevine,danl,rinap}@theory.lcs.mit.edu" lists 'danl' twice (seven usernames for six authors).
- p. 1 Footnote 1
{karger,e lehman,danl,ftl,mslevine,danl,rinap}@theory.lcs.mit.edu
Judge's note: Page 1 image: the email line shows danl twice. The URL line below it, "{karger,e lehman,ftl,mslevine,danl,rinap}", lists six names without the duplicate.
Second check: none (judge only)
Report a problem with this finding
Typo Footnote 1: "A full version of this paper is availble at:" should read 'available'.
- p. 1 Footnote 1
A full version of this paper is availble at:
- p. 1 footnote
A full version of this paper is availble at
Judge's note: The misspelling is visible in the page 1 footnote image.
Second check: none (judge only)
Report a problem with this finding
Typo Abstract, first line: "caching protocols for distrib-uted networks" has a stray mid-line hyphen; it should read 'distributed'.
- p. 1 Abstract, line 1
distrib-uted networks
Judge's note: The crop shows the hyphen in the middle of the line, not at a line break.
Second check: none (judge only)
Report a problem with this finding
Typo Section 1.2: "Each time a new machine joins the network, the require a central server to redistribute" should read 'they require'.
- p. 2 Section 1.2, Feeley et al. paragraph
the require a central server to redistribute
Judge's note: Visible in the page 2 image, right column, in the Feeley et al. sentence.
Second check: none (judge only)
Report a problem with this finding
Typo Sec 3.2.1: "The existence of tree schemes, like the Harvest Cache, suggests that is acceptable in practice." is missing a word ('that this is').
- p. 4 Section 3.2.1
suggests that is acceptable in practice.
Judge's note: Visible in the page 4 image, left column, in Sec 3.2.1.
Second check: none (judge only)
Report a problem with this finding
Typo Index range printed as 'where 0 ≤ qj ≤ log dq − 1'; equation (1) sums over j = 0 … log(dq) − 1, so it should read '0 ≤ j ≤ log dq − 1'.
- p. 5 Requests to Internal Nodes
where 0 ≤ qj ≤ log dq − 1
Judge's note: Page 5 image and the text layer (tokens 0, q, j) both show 'qj'. The bucketing is by 2^j, and equation (1) indexes j over 0..log(dq)−1, so the stray q is a typo.
Second check: none (judge only)
Report a problem with this finding
Typo Extra word: 'the probability that a machine m is receives more than z of these nodes'; should be 'machine m receives'.
- p. 5 Requests to Internal Nodes
a machine m is receives more than z
- p. 5 Requests to Internal Nodes
a machine m is receives more than
Judge's note: Seen in the C023-a crop on page 5.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling 'ignoring log log(dq) in comparision with dq'; should be 'comparison'.
- p. 5 End of proof of Theorem 3.1
in comparision with dq
- p. 5 end of proof of Theorem 3.1
in comparision with
Judge's note: Page 5 image and text layer line 1055 both show 'comparision'.
Second check: none (judge only)
Report a problem with this finding
Typo Article error: 'which cache stores a object' (also 'to map a object', 'to which a object', 'Distributing a object' on page 6); should be 'an object'.
- p. 5 Section 4
which cache stores a object
Judge's note: Page 5 image shows 'stores a object.' The text layer shows three more instances on page 6, at lines 1252, 1258 and 1266.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling on p.6, Section 4 intro: "discuss other aspects of consistent hashing whihc, though not germane to this paper"; should be "which".
- p. 6 Section 4 intro
consistent hashing whihc, though not ger-
Judge's note: The page image shows "whihc" in the left column above Section 4.1.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling on p.6, Balance paragraph: "they distribute items among buckets in a balanced fa-sion"; should be "fashion".
- p. 6 Section 4.1, Balance
in a balanced fa- sion.
- p. 6 Balance
balanced fa-sion
- p. 6
balanced fa- sion.
Judge's note: The crop shows "fa-" at a line end and "sion." on the next line. The word is missing the h, so this is a real misspelling, not a hyphenation artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Missing word on p.6, Section 4.1: "(We will use the notation f_V(i) in place f(V, i) from now on.)"; should be "in place of f(V, i)".
- p. 6 Section 4.1
in place f(V, i) from now on.
Judge's note: On the page image, Section 4.1 (ranged hash function paragraph) reads "in place f(V, i) from now on", with no "of".
Second check: none (judge only)
Report a problem with this finding
Typo Misspellings on p.7, proof sketch of Theorem 4.1: "each bucket is with highu probability responsible" (should be "high") and "of combinatroially distinct ways" (should be "combinatorially").
- p. 7 Proof of Theorem 4.1
with highu probability
- p. 7 Proof of Theorem 4.1
combinatroially distinct ways
- p. 7
each bucket is with highu probability responsible
Judge's note: The crop shows both misspellings in the proof sketch of Theorem 4.1.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling on p.7, Section 4.3: "how the hash family just dexcrobed can be implemented"; should be "described".
- p. 7 Section 4.3, first sentence
the hash family just dexcrobed
- p. 7 Implementation
hash family just dexcrobed can
- p. 7
the hash family just dexcrobed can
Judge's note: The crop shows "dexcrobed" in the first sentence of Section 4.3.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling on p.7, Section 4.4: "though unneccessary for the remainder of the paper"; should be "unnecessary".
- p. 7 Section 4.4, first sentence
though unneccessary for the remainder of the paper
- p. 7 Section 4.4
though unneccessary for the remainder
Judge's note: The crop shows "unneccessary" in the first sentence of Section 4.4.
Second check: none (judge only)
Report a problem with this finding
Typo p.8, paragraph after Theorem 4.5: "the good properties proved in the this section" (duplicated determiner) and "could be restrictivly slow" (should be "restrictively").
- p. 8 Paragraph after proof of Theorem 4.5
proved in the this section
- p. 8 end of Section 4.4
restrictivly slow
- p. 8
could be restrictivly slow for large bucket sets
Judge's note: The crop shows both defects in the paragraph just before Section 5.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling in proof of Theorem 5.1: "we know from Corrollary 4.2" should read "Corollary 4.2".
- p. 8 Proof of Theorem 5.1
we know from Corrollary 4.2
- p. 8 Proof of Theorem 5.1
Corrollary 4.2
Judge's note: Page 8 image, right column, Proof of Theorem 5.1: 'Corrollary 4.2' is printed as quoted.
Second check: none (judge only)
Report a problem with this finding
Typo Wrong word in proof of Theorem 5.1: "We now assign and abstract node to a given machine" should read "an abstract node".
- p. 8 Proof of Theorem 5.1
We now assign and abstract node to a given machine
Judge's note: Page 8 image, right column, proof of Theorem 5.1, confirms 'assign and abstract node'.
Second check: none (judge only)
Report a problem with this finding
Typo Typos in proof of Theorem 6.1: "The intuition behind are proof" (should be 'our proof') and "Sumnming over the log C clusters" (should be 'Summing').
- p. 9 Proof of Theorem 6.1, first sentence
The intuition behind are proof is the following.
- p. 9 Proof of Theorem 6.1
behind are proof
- p. 9 Proof of Theorem 6.1
Sumnming over the
Judge's note: Page 9 image: both 'behind are proof' (left column, Proof (sketch)) and 'Sumnming' (right column, end of proof) are printed as quoted.
Second check: none (judge only)
Report a problem with this finding
Typo Extra comma in proof of Theorem 6.1: "m1,, m2, . . .".
- p. 9 Proof of Theorem 6.1
m1,, m2, . . .
Judge's note: Page 9 image, left column, Proof (sketch) of Theorem 6.1 shows 'm_1, , m_2, ...' with a doubled comma.
Second check: none (judge only)
Report a problem with this finding
Typo Typos in Section 7: "A logarithmic number if requests is sufficient" ('of requests') and "If a you de-cide a machine is down" (stray 'a').
- p. 9 Section 7
A logarithmic number if requests is sufficient
- p. 9 Fault Tolerance
If a you de-
- p. 9 Fault Tolerance
number if requests
Judge's note: Page 9 image, right column, Section 7: both phrases are printed as quoted.
Second check: none (judge only)
Report a problem with this finding
Typo Conclusion (Section 9), right column of p.10: "Is there a k-universal consistent hash function that can be evaluated efficiently??" has a doubled question mark.
- p. 10 Section 9, last paragraph
can be evaluated efficiently??
- p. 10 Conclusion
evaluated efficiently??
Judge's note: I checked both the crop and the full page image of p.10. The doubled '??' is printed in the Conclusion's final paragraph, so this is not an artefact of text extraction. The fix is to drop one question mark.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [11] gives the venue as "Proc. 4th ACS-SIAM Symposium on Discrete Algorithms, 1993"; the expected name is ACM-SIAM.
- p. 10 Reference [11]
Proc. 4th ACS-SIAM Symposium on Discrete Algorithms
- p. 10 References
4th ACS-SIAM Symposium
- p. 10 References
Steen McCanne
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: SODA is the ACM-SIAM Symposium on Discrete Algorithms. The crop and the page image of p.10 both show "ACS-SIAM" in reference [11]. This cluster also quotes 'Steen McCanne'; that misspelling is a separate defect and is judged under C063.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [4] lists a co-author as "Steen McCanne"; the expected spelling is Steven McCanne.
- p. 10 Reference [4]
Steen McCanne
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the co-author of the SIGCOMM '95 SRM paper is Steven McCanne. The crop and the page image of p.10 both show "Steen McCanne" in reference [4], so this is not caused by text extraction.
Second check: none (judge only)
Report a problem with this finding
Typo Section 8, first paragraph: "Recall that our temporal model says that browsers issues requests at a certain rate γ" has a subject–verb agreement error and should read "browsers issue".
- p. 10 Section 8, first paragraph
browsers issues requests at a certain rate γ.
Judge's note: The text layer (main.txt line 2713) has 'browsers issues requests at a certain rate'. The page image of p.10 shows the same wording in Section 8's first paragraph. This is a grammatical slip, and the fix is evident.
Second check: none (judge only)