Pith. sign in

REVIEW 3 major objections 6 minor 36 references

Revisiting Consistent Hashing with Bounded Loads

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Bounded-load consistent hashing degrades as servers fill; rehashing overflow with a failure counter restores even loads, provably lowering variance and cutting cache misses.

desk verdict A promising practical fix for cascaded overflow in consistent hashing, with strong empirical results, but the paper's central dominance theorem rests on a proof gap in Lemma 5 that may not be repairable as written. read the letter →

arxiv 1908.08762 v2 pith:CEHNQ63X submitted 2019-08-23 cs.DS

John Chen , Ben Coleman , Anshumali Shrivastava This is my paper · ORCID
classification cs.DS MSC 68W2068M1460C05
keywords consistenthashingboundedloadscascadedoverflowrandomjumploadbalancingdistributedcachingcachemissesminwise
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that the standard way to add capacity limits to consistent hashing, Consistent Hashing with Bounded Loads (CH-BL), gets worse exactly when it is most needed: as servers fill, overflow is sent to the nearest open server in the clockwise direction, so load concentrates on a shrinking set of servers and the imbalance cascades. The proposed fix, Random Jump Consistent Hashing (RJ-CH), rehashes every overflowed object together with a counter of failed attempts, so a redirected object lands uniformly on any currently non-full server and the cascade is broken. The paper proves that RJ-CH dominates CH-BL in the convex order: for every convex function $f$, $\sum_i \mathbb{E}[f(X_i^{\mathrm{RJ-CH}})] \le \sum_i \mathbb{E}[f(X_i^{\mathrm{CH-BL}})]$, which directly implies lower bin-load variance and fewer full bins, and it proves an expected insertion cost of at most $1+1/\epsilon$. On two real user-activity logs the reported additional cache misses fall by one to several orders of magnitude. Distributed caches that must rebalance as servers join or leave depend on exactly this trade-off between even load and cheap reassignment, which is why the claim matters.

What carries the argument

The engine of the argument is the failure-counter rehash. Instead of hashing an object once and walking clockwise when the landed bin is full, RJ-CH computes $h(\text{object}, r)$ for $r = 0,1,2,\ldots$ until the hash lands on an array index whose bin is not full, borrowing the two-argument densification idea from fast minwise hashing. The counter argument decorrelates overflow destinations: two different objects that both miss a full bin collide again with probability only $1/m$, where $m$ is the array length, so overflow behaves like independent uniform draws over the open bins. That uniformity is the property every theorem uses, because it makes the load vector a symmetric multinomial-type distribution, allows the proofs to compare CH-BL and RJ-CH object by object through a stochastic-dominance chain, and is what the optimality claims about insertion cost, objects before first overflow, and pre-overflow variance are evaluated against.

What would settle it

Run both schemes end-to-end with 1000 bins, 10000 objects, and capacity slack $\epsilon = 0.1$ as the appendix implements them, recording every rehash that lands on an empty array index; if the empirical distribution of redirected objects deviates measurably from uniform over the non-full bins, or if any convex $f$ is found with $\sum_i \mathbb{E}[f(X_i^{\mathrm{RJ-CH}})] > \sum_i \mathbb{E}[f(X_i^{\mathrm{CH-BL}})]$, the central theorem is contradicted.

Watch

Extended reading notes

Core claim

Cascaded overflow, not finite capacity itself, is the real source of imbalance in bounded-load consistent hashing. The central claim is that CH-BL's overflow rule, sending an object to the nearest open bin clockwise, concatenates the effective arc lengths of consecutive full bins onto one open bin, making that bin fill faster still and producing an avalanche that builds as load increases. RJ-CH replaces nearest-neighbor overflow with a two-argument rehash, hashing the object together with the number of failed attempts until it reaches an index holding an open bin, so every overflow lands uniformly among the open bins. The main theorem states that for any convex $f$ defined on $\{0,1,\ldots,C\}$, $\sum_i \mathbb{E}[f(X_i^{\mathrm{RJ-CH}})] \le \sum_i \mathbb{E}[f(X_i^{\mathrm{CH-BL}})]$, a stochastic ordering that implies no larger bin-load variance and no larger expected number of full bins; a further theorem shows CH-BL's assignment-probability variance grows geometrically at rate at least $1/(3k)$ per full bin while RJ-CH keeps it at exactly zero.

Load-bearing premise

The theory's superiority proof assumes every redirected object lands uniformly at random among the currently non-full bins, but the implementation hashes roughly 1000 bins into a sparse array of $2^{20}$ slots, so most rehashes land on empty indices, and the paper never shows that this practical procedure produces exactly the uniform distribution over bins that the theorems require.

Editorial extensions

If this is right

  • For any convex measure of imbalance, RJ-CH is never worse than CH-BL: bin-load variance, expected number of full bins, and the expectation of every convex function of bin load all favor RJ-CH.
  • Inserting an object costs at most $1 + 1/\epsilon$ bin searches under RJ-CH, versus roughly $2/\epsilon^2$ for CH-BL at small $\epsilon$, so the advantage grows as capacity slack tightens.
  • Among all stateless addressing schemes, RJ-CH maximizes the expected number of objects placed before the first bin overflows, which means overload starts later for the same capacity.
  • On the two real user-activity logs tested, additional cache misses drop by one to several orders of magnitude in every configuration, not just in a narrow parameter range.
  • CH-BL's assignment-probability variance grows geometrically with rate at least $1/(3k)$ as bins fill, so its imbalance compounds with load, while RJ-CH's assignment probabilities remain exactly uniform.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The counter-seeded rehash is a generic remedy for any 'nearest open slot' bias, so other schemes that suffer analogous cascades, such as rendezvous hashing or cuckoo-style relocation, could plausibly adopt the same two-argument hash; the paper does not discuss these transfers.
  • The claim that duplicate copies created when a bin is added are harmless presumes eviction eventually removes them; in a cache with no expiry, duplication would silently consume capacity, and bounding duplication under server churn is a natural follow-up the paper leaves open.
  • Because RJ-CH changes only how overflow is resolved, not how objects are initially placed on the ring, existing consistent-hashing deployments might adopt it with minimal change; the paper does not quantify the migration or production implementation cost.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The manuscript introduces Random Jump Consistent Hashing (RJ-CH), a variant of consistent hashing with bounded loads in which an object whose primary hash lands in a full bin is rehashed with a counter, rather than being cascaded to the nearest clockwise bin. The central theoretical claim is Theorem 2: for any convex function f, the summed expectation of f(bin load) under RJ-CH is no larger than under CH-BL, yielding lower per-bin load variance and fewer expected full bins as stated in Theorem 1. Supporting results bound the expected number of bin searches (Theorem 3), prove optimality of uniform stateless assignment (Theorems 4 and 5), and claim exponential growth of assignment-probability variance for CH-BL (Theorem 6). Empirically, simulations and logs from the AOL search dataset and the Indiana University Clicks dataset report reductions in additional cache misses by several orders of magnitude.

Significance. If Theorem 2 is established, the paper makes a useful practical contribution: RJ-CH is a simple modification of CH-BL with a clear mechanism for avoiding cascaded overflow, and the reported reductions in cache misses on real logs are striking. The manuscript is commendably explicit about many implementation details and includes extensive simulation tables in Appendices L, O, and R, as well as honest discussion of limitations such as duplicate copies after bin insertion in Section 3.1. The obstacle is that the proof of Theorem 2 currently rests on a step in Lemma 5 that is not justified and, as written, appears incorrect; until that step is repaired, the central theoretical claim is not established. The optimality results in Theorems 4 and 5 are valid for the stated stateless class, but they are close to consequences of RJ-CH's defining uniform assignment and should be framed as such.

major comments (3)
  1. [Appendix F, proof of Lemma 5] The step "It follows from Lemmas 1 and 4 that, under this condition, the conditional distribution of (η1, η2) is the same as the conditional distribution of the above (ξ1, ξ2)" is not justified. Lemma 4 describes the conditional distribution at the end of the CH-BL phase (Step 1/Step (a)), while the RJ-CH phase in Step (b) contributes a fair binomial only if bins i1 and i2 remain equally available for every object in that phase. Once either bin reaches capacity, later RJ-CH objects that would have landed in the full bin are redistributed uniformly over all non-full bins, not equally between i1 and i2. The final conditional split is therefore not the claimed convolution of a Bernoulli with p*/(p*+p*) and a fair Bernoulli, and the stochastic ordering η1 ≺ η2 in Eq. (16) is not derived. Since Lemma 5 is the only bridge from the m-object scheme to the (m+1)-object scheme in the proof of Theorem 2, Theorem 2 is currently unproven.
  2. [Appendix C, Lemma 2] Lemma 2 is a key ingredient in the proof of Lemma 5, but its proof is given as "We omit the details." The constrained-multinomial part of the lemma is not immediate and needs a full proof or an explicit citation. As it stands, the proof chain for Theorem 2 has a missing link here as well.
  3. [Appendix M vs. Section 3] The theoretical analysis models RJ-CH as assigning each object uniformly among the currently non-full bins, but the implementation hashes into a sparse array of size 2^20 containing roughly 1000 bins. The manuscript never states what happens when a rehash lands on an empty index: does the counter increment and continue, or is an empty slot treated as a failure? This missing rule makes the simulation results and Tables 1 and 2 irreproducible and leaves open the question of whether the empirical algorithm actually matches the analyzed scheme. The exact rehashing rule should be specified, and if empty slots are skipped, the effect on uniformity should be discussed.
minor comments (6)
  1. [Eq. (3), Section 4.1] The first sum in Eq. (3) uses X_k^{(RJ-CH)} instead of X_i^{(RJ-CH)}; this appears to be a typographical error.
  2. [Section 4.1 and abstract] The phrase "stochastically dominates" is used in the direction where CH-BL has stochastically larger loads; please reword to avoid the impression that CH-BL is the better method, for example by saying CH-BL loads are stochastically larger than RJ-CH loads.
  3. [Theorems 4 and 5, Section 4.3-4.4] The optimality claims for uniform stateless assignment are correct for the stated class, but they should explicitly note that RJ-CH is defined to use the uniform distribution, so the theorems quantify an optimality property of the construction rather than an unexpected advantage over other schemes.
  4. [Section 3.1] The claim that duplicate copies created when a bin is added are harmless because they will eventually be evicted is neither quantified nor tested; please add a supporting argument, a bound, or experimental evidence.
  5. [Appendix L.3] The text refers to "Table ??" instead of a numbered table; this reference should be fixed.
  6. [Appendix J and Theorem 6] The proof concludes that variance strictly increases for j = 1,...,k-2, while the theorem statement says j = 1,...,k-3; these two ranges should be aligned, and the role of the assumption that each non-full bin has equal probability of being full should be stated more carefully because CH-BL does not satisfy that assumption.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central Theorem 2 is proved against the external CH-BL baseline, and the only self-citation is motivational rather than load-bearing.

full rationale

The paper's central claim is Theorem 2, which states that for any convex f, sum_i E[f(X_i^RJ-CH)] <= sum_i E[f(X_i^CH-BL)]. This is a comparison against an external baseline, CH-BL from Mirrokni et al. [2], and the proof is a hybrid/induction argument through Lemmas 1-5, not an assumption of the conclusion. Nothing is fitted and then renamed as a prediction: RJ-CH has no learned or fitted parameters, and the empirical results are direct measurements against CH-BL on external AOL and Indiana University Clicks logs. Theorems 4 and 5 have a mildly self-definitional flavor because RJ-CH is described as assigning uniformly to non-full bins and is then shown to be optimal among stateless schemes. However, the theorems quantify over all stateless addressing distributions and prove that the uniform distribution maximizes the probability of no full bin and minimizes bin-load variance; they do not assume what they prove. This is a genuine property of the multinomial model, not a tautology. The only self-citation is [29], by coauthor Shrivastava, cited as motivation ("Our proposal is motivated by Optimal Densification [29]"), and no theorem or equation depends on it, so it is not load-bearing. The skeptic's objection about Lemma 5's order-swap argument is a proof-validity concern, not a circularity concern: even if the argument is flawed, the theorem's output is not identical to its input by construction. Accordingly, no circular step is identified and the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper's theoretical results depend on an idealized hashing model and on equal initial CH-BL arcs, while the empirical results depend on an under-specified sparse-array implementation and on duplicate eviction after bin addition.

assumptions (4)
  • domain assumption Each rehash attempt h(object, attempt) yields an independent uniform sample over the array.
    Section 3 and 2.1 claim this follows from universal hashing; it is required for RJ-CH to assign uniformly to non-full bins.
  • domain assumption CH-BL's initial assignment probabilities are equal (optimal bin placement).
    Stated in Section 4.1 before Theorem 1; the proof of Lemma 4 uses p*_j = (L_ij+1)/k.
  • standard math The exchangeability property of Lemma 1 holds for the RJ-CH process.
    Lemma 1 is proved by a short case analysis (Appendix B) and is the basis for swapping the order of the special object in the hybrid scheme.
  • domain assumption Duplicate objects created on bin addition are eventually evicted and do not affect load balance.
    Section 3.1 asserts this; the empirical evaluation relies on it for the dynamic server recovery configurations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Revisiting Consistent Hashing with Bounded Loads." pith.science (2026). https://pith.science/paper/CEHNQ63X

@misc{pith2026190808762,
  author       = {Pith},
  title        = {Pith review of: Revisiting Consistent Hashing with Bounded Loads},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CEHNQ63X}},
  note         = {Machine review of arXiv:1908.08762}
}
read the original abstract

Dynamic load balancing lies at the heart of distributed caching. Here, the goal is to assign objects (load) to servers (computing nodes) in a way that provides load balancing while at the same time dynamically adjusts to the addition or removal of servers. One essential requirement is that the addition or removal of small servers should not require us to recompute the complete assignment. A popular and widely adopted solution is the two-decade-old Consistent Hashing (CH). Recently, an elegant extension was provided to account for server bounds. In this paper, we identify that existing methodologies for CH and its variants suffer from cascaded overflow, leading to poor load balancing. This cascading effect leads to decreasing performance of the hashing procedure with increasing load. To overcome the cascading effect, we propose a simple solution to CH based on recent advances in fast minwise hashing. We show, both theoretically and empirically, that our proposed solution is significantly superior for load balancing and is optimal in many senses. On the AOL search dataset and Indiana University Clicks dataset with real user activity, our proposed solution reduces cache misses by several magnitudes.

Figures

Figures reproduced from arXiv: 1908.08762 by the authors.

Figure 1
Figure 1. Consistent Hashing object and bin assignment. Objects are red. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. CH-BL with bin capacity of 3 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Effective arclength of each non-full bin. Cas￾caded overflow of CH-BL with bin capacity of 3. On bin removal, CH-BL performs the same reallocation procedure as CH, but with bounded loads. Objects from a deleted bin are cached in the closest available bin in the clockwise direction the next time the object is requested. Bin addition is handled the same as CH. 2.4 Cascaded Overflow of Consistent Hashing and Variants C… view at source ↗
Figures from the paper (15 more)
Figure 4
Figure 4. Figure 4: RJ-CH object and bin assignment with bin capacity of 3. [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]
Figure 5
Figure 5. Figure 5: Percentage of total bins full [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 7
Figure 7. Figure 7: Variance of object assignment probabilities against number of full bins. [PITH_FULL_IMAGE:figures/full_fig_p022_7.png]
Figure 8
Figure 8. Figure 8: Variance of bin loads [PITH_FULL_IMAGE:figures/full_fig_p023_8.png]
Figure 10
Figure 10. Figure 10: Percentage of total bins full [PITH_FULL_IMAGE:figures/full_fig_p023_10.png]
Figure 12
Figure 12. Figure 12: Total steps for adding n + 1th object. Note that y values are scaled [PITH_FULL_IMAGE:figures/full_fig_p023_12.png]
Figure 14
Figure 14. Figure 14: Variance of bin loads for different configurations. [PITH_FULL_IMAGE:figures/full_fig_p028_14.png]
Figure 15
Figure 15. Figure 15: Bin searches for the n + 1th object to be placed for different configurations. (a) 10000 objects, 1000 bins, no virtual bins. (b) 10000 objects, 1000 bins, log(k) virtual bins. (c) 3000 objects, 1000 bins, no virtual bins. (d) 3000 objects, 1000 bins, log(k) virtual b…
Figure 16
Figure 16. Figure 16: Percentage of total bins full for different configurations. [PITH_FULL_IMAGE:figures/full_fig_p029_16.png]
Figure 17
Figure 17. Figure 17: Number of objects placed until one bin is full. [PITH_FULL_IMAGE:figures/full_fig_p030_17.png]
Figure 18
Figure 18. Figure 18: Total steps for adding n + 1th object for different configurations. Note that some y values are scaled. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_18.png]
Figure 19
Figure 19. Figure 19: Wall clock time for adding n + 1th object for different configurations. (a) 10000 objects, 1000 bins, no virtual bins. (b) 10000 objects, 1000 bins, log(k) virtual bins. (c) 3000 objects, 1000 bins, no virtual bins. (d) 3000 objects, 1000 bins, log(k) virtual bins [P…
Figure 20
Figure 20. Figure 20: Normalized bin searches for bin removal to be placed for different configurations. [PITH_FULL_IMAGE:figures/full_fig_p031_20.png]
Figure 21
Figure 21. Figure 21: Per object total steps for removing a bin for different configurations. Note that some y values [PITH_FULL_IMAGE:figures/full_fig_p032_21.png]
Figure 22
Figure 22. Figure 22: Per object wall clock time for removing a bin for different configurations. [PITH_FULL_IMAGE:figures/full_fig_p032_22.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web

    David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigraph. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997

    work page 1997

  2. [2]

    Consistent hashing with bounded loads

    Vahab Mirrokni, Mikkel Thorup, and Morteza Zadimoghaddam. Consistent hashing with bounded loads. SODA, 2018

    work page 2018

  3. [3]

    Chord: a scalable peer-to-peer lookup protocol for internet applications

    Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. ACM SIGCOMM Computer Communication Review, 2001

    work page 2001

  4. [4]

    Chord: a scalable peer-to-peer lookup protocol for internet applications

    Ion Stoica, Robert Morris, David Liben-Nowell, David Karger, Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw., 2003

    work page 2003

  5. [5]

    Semantics of caching with spoca: A stateless, proportional, optimally-consistent addressing algorithm

    Anshish Chawla, Benjamin Reed, Karl Juhnke, and Ghousuddin Syed. Semantics of caching with spoca: A stateless, proportional, optimally-consistent addressing algorithm. In USENIX ATM, 2011

    work page 2011

  6. [6]

    Spirakis

    Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul G. Spirakis. Space efficient hash tables with worst case constant access time. Theory Comput. Syst., 2005

    work page 2005

  7. [7]

    Linear probing with constant independence

    Rasmus Pagh and Flemming Friche Rodler. Linear probing with constant independence. SIAM Journal on Computing, 2009

    work page 2009

  8. [8]

    Cuckoo hashing

    Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Springer, 2001

    work page 2001

Show all 36 references
  1. [9]

    Cuckoo hashing

    Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Journal of Algorithms, 2004

    2004

  2. [10]

    Cache in-memory in asp.net core

    Rick Anderson, John Luo, and Steve Smith. Cache in-memory in asp.net core. ASP .NET Core 3.0, 2019

    2019

  3. [11]

    Caching best practices

    Alex Buck, Pedro Wood, Christopher Bennage, Peter Taylor, Tim Reilly, Tim Lovell-Smith, Alexey Sosnin, Nick Schonnig, Chris V oon, Duncan Mackenzie, Andrew Cook, and Marc Wilson. Caching best practices. Microsoft docs, 2017

    2017

  4. [12]

    Mozilla docs, 2020

    Caching. Mozilla docs, 2020

    2020

  5. [13]

    How discord scaled elixir to 5,000,000 concurrent users

    Stanislav Vishnevskiy. How discord scaled elixir to 5,000,000 concurrent users. Discord Blog, 2017

    2017

  6. [14]

    Dynamo: Amazon’s highly available key-value store

    Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter V osshall, and Werner V ogels. Dynamo: Amazon’s highly available key-value store. SOSP, 2007

    2007

  7. [15]

    Cassandra: a decentralized structured storage system

    Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, 2010

    2010

  8. [16]

    Consistent hashing with bounded loads

    Vahab Mirrokni and Morteza Zadimoghaddam. Consistent hashing with bounded loads. Google Research Blog, 2017. 9 A PREPRINT - J UNE 17, 2020

    2017

  9. [17]

    Improving load balancing with a new consistent-hashing algorithm

    Andrew Rodland. Improving load balancing with a new consistent-hashing algorithm. Vimeo Engineering Blog, 2016

    2016

  10. [18]

    Information retrieval - algorithms and heuristics, second edition, volume 15 of the kluwer international series on information retrieval

    David Grossman and Ophir Frieder. Information retrieval - algorithms and heuristics, second edition, volume 15 of the kluwer international series on information retrieval. Kluwer, 2004

    2004

  11. [19]

    Principles of distributed database systems, third edition

    Tamer Ozsu and Patrick Valduriez. Principles of distributed database systems, third edition. Springer, 2011

    2011

  12. [20]

    Redis in action

    Josiah Carlson. Redis in action. Manning Publications Co., 2013

    2013

  13. [21]

    Scaling memcache at facebook

    Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, and Venkateshwaran Venkataramani. Scaling memcache at facebook. In Proceedings of the 10th USENIX Conference on Ne...

    2013

  14. [22]

    Web caching with consistent hashing.Computer Networks, 1999

    David Karger, Alex Sherman, Andy Berkheimer, Bill Bogstad, Rizwan Dhanidina, Ken Iwamoto, Brian Kim, Luke Matkins, and Yoav Yerushalmi. Web caching with consistent hashing.Computer Networks, 1999

    1999

  15. [23]

    Load balancing using consistent hashing: A real challenge for large scale distributed web crawlers

    Mitra Nasri and Mohsen Sharifi. Load balancing using consistent hashing: A real challenge for large scale distributed web crawlers. 23rd International Conference on Advanced Information Networking and Applications, 2009

    2009

  16. [24]

    Load-balancing performance of consistent hashing: Asymp- totic analysis of random node join

    Xiaoming Wang and Dmitri Loguinov. Load-balancing performance of consistent hashing: Asymp- totic analysis of random node join. IEEE/ACM Transactions on Networking, 2007

    2007

  17. [25]

    Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems

    Antony Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. Middleware, 2001

    2001

  18. [26]

    Scribe: A large- scale and decentralized application-level multicast infrastructure

    Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, and Antony IT Rowstron. Scribe: A large- scale and decentralized application-level multicast infrastructure. Selected Areas in Communications, IEEE, 2002

    2002

  19. [27]

    A scalable content-addressable network

    Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A scalable content-addressable network. ACM, 2001

    2001

  20. [28]

    Meiss, F

    M. Meiss, F. Menczer, S. Fortunato, A. Flammini, and A. Vespignani. Ranking web sites with real user traffic. In Proc. First ACM International Conference on Web Search and Data Mining (WSDM), pages 65–75, 2008

    2008

  21. [29]

    Optimal densification for fast and accurate minwise hashing

    Anshumali Shrivastava. Optimal densification for fast and accurate minwise hashing. In International Conference on Machine Learning, 2017

    2017

  22. [30]

    Cisco docs, 2020

    Cisco annual internet report (2018–2023) white paper. Cisco docs, 2020

    2018

  23. [31]

    Tejas Karkhanis and J.E. Smith. A day in the life of a data cache miss. Workshop on Memory Performance Issues, 2002. 10 A PREPRINT - J UNE 17, 2020 Appendix A Proof of Theorem 1 Theorem 1 restated Following the notations in Theorem 2, ford≥ 1, E[(X (RJ−CH ) i )d]≤E[(X (CH−BL) ...

    2002

  24. [32]

    self-contained

    In other words,Q(D,K ) is the probability that allD objects are "self-contained" in bins 1,...,K under the CH-BL of relocation. Fix valuesz1,...,z J such that 0≤zj <C and∑J j=1zj =n∗. We consider the conditional distribution under the condition Lij = lj for some fixed lj , j = ...

    2020

  25. [33]

    Steps (b) and (c) switch Steps 2 and 3

    same as Step 2, and reassigning following RJ-CH. Steps (b) and (c) switch Steps 2 and 3. Unlike in Step 2, where the object need not be reassigned, in Step (c), the object may be assigned to a full bin and, in that case, reassigned following RJ-CH. The equivalence of these two...

  26. [34]

    Set ξ1 =∑a1+a2 j=1 ∆j andξ2 =a1 +a2−ξ1

    = 1−P (∆j = 0) forj = 1,...,a 1 13 A PREPRINT - J UNE 17, 2020 and P (∆j = 1) = P (∆j = 0) = 1 /2 for j = a1 + 1,...,a 1 +a2, where p∗ l = (1 + Lil)/K. Set ξ1 =∑a1+a2 j=1 ∆j andξ2 =a1 +a2−ξ1. Sincep∗ 1≤p∗ 2, Lemma 2 implies that, ξ1| (ξ1 <C,ξ 2 <C )≺ξ2| (ξ1 <C,ξ 2 <C ). Now co...

    2020

  27. [35]

    CH-BL continues to worsen with the cascading effect

    After the bins in the biased regions of the array are full, RJ-CH recovers the uniform distribution. CH-BL continues to worsen with the cascading effect

  28. [36]

    For CH-BL, the closest clockwise bin is severely affected

    Given that no bins are hashed into the biased regions of the array, RJ-CH recovers the uniform distribution. For CH-BL, the closest clockwise bin is severely affected. Appendix O Tabulated simulation results Simulation results in the main manuscript in tabulated form in Tables...

    2020

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.