BinomialHash: A Constant Time, Minimal Memory Consistent Hash Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917959041024000 |
|---|---|
| author | Coluzzi, Massimo Brocco, Amos Antonucci, Alessandro Leidi, Tiziano |
| author_facet | Coluzzi, Massimo Brocco, Amos Antonucci, Alessandro Leidi, Tiziano |
| contents | Consistent hashing is a technique for distributing data across a network of nodes in a way that minimizes reorganization when nodes join or leave the network. It is extensively applied in modern distributed systems as a fundamental mechanism for routing and data placement. Similarly, distributed storage systems rely on consistent hashing for scalable and fault-tolerant data partitioning. This paper introduces BinomialHash, a consistent hashing algorithm that executes in constant time and requires minimal memory. We provide a detailed explanation of the algorithm, present a pseudo-code implementation, and formally establish its strong theoretical guarantees. Finally, we compare its performance against state-of-the-art constant-time consistent hashing algorithms, demonstrating that our solution is both highly competitive and effective, while also validating the theoretical boundaries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19836 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | BinomialHash: A Constant Time, Minimal Memory Consistent Hash Algorithm Coluzzi, Massimo Brocco, Amos Antonucci, Alessandro Leidi, Tiziano Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Consistent hashing is a technique for distributing data across a network of nodes in a way that minimizes reorganization when nodes join or leave the network. It is extensively applied in modern distributed systems as a fundamental mechanism for routing and data placement. Similarly, distributed storage systems rely on consistent hashing for scalable and fault-tolerant data partitioning. This paper introduces BinomialHash, a consistent hashing algorithm that executes in constant time and requires minimal memory. We provide a detailed explanation of the algorithm, present a pseudo-code implementation, and formally establish its strong theoretical guarantees. Finally, we compare its performance against state-of-the-art constant-time consistent hashing algorithms, demonstrating that our solution is both highly competitive and effective, while also validating the theoretical boundaries. |
| title | BinomialHash: A Constant Time, Minimal Memory Consistent Hash Algorithm |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.19836 |