DROPS

Artifact

Software

Hash-And-Adjust

Authors: Arash Pourdamghani, Chen Avin, Robert Sama, Maryam Shiran, and Stefan Schmid

Abstract

Cite as

Arash Pourdamghani, Chen Avin, Robert Sama, Maryam Shiran, Stefan Schmid. Hash-And-Adjust (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagpub-supp--paper-21643-urlgithub.com-inet-tub-Hash-And-Adjust,
   title = {{Hash-And-Adjust}}, 
   author = {Pourdamghani, Arash and Avin, Chen and Sama, Robert and Shiran, Maryam and Schmid, Stefan},
   note = {Software, version 1.0., This project has received funding from the European Research Council (ERC) under grant agreement No. 864228 (AdjustNet), 2020-2025., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:77be335343d4a118b82953ed6c1bb8a05cd91335;origin=https://github.com/inet-tub/Hash-And-Adjust;visit=swh:1:snp:92f8dea41d62b077bdfcc74688522b8f0d67d68b;anchor=swh:1:rev:d680a69b5437c59d062d532743a3385e87d0e4f7}{\texttt{swh:1:dir:77be335343d4a118b82953ed6c1bb8a05cd91335}} (visited on 2025-01-08)},
   url = {https://github.com/inet-tub/Hash-And-Adjust},
   doi = {10.4230/artifacts.22600},
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2024.24

Hash & Adjust: Competitive Demand-Aware Consistent Hashing

Authors: Arash Pourdamghani, Chen Avin, Robert Sama, Maryam Shiran, and Stefan Schmid

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract

Distributed systems often serve dynamic workloads and resource demands evolve over time. Such a temporal behavior stands in contrast to the static and demand-oblivious nature of most data structures used by these systems. In this paper, we are particularly interested in consistent hashing, a fundamental building block in many large distributed systems. Our work is motivated by the hypothesis that a more adaptive approach to consistent hashing can leverage structure in the demand, and hence improve storage utilization and reduce access time. We initiate the study of demand-aware consistent hashing. Our main contribution is H&A, a constant-competitive online algorithm (i.e., it comes with provable performance guarantees over time). H&A is demand-aware and optimizes its internal structure to enable faster access times, while offering a high utilization of storage. We further evaluate H&A empirically.

Cite as

Arash Pourdamghani, Chen Avin, Robert Sama, Maryam Shiran, and Stefan Schmid. Hash & Adjust: Competitive Demand-Aware Consistent Hashing. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pourdamghani_et_al:LIPIcs.OPODIS.2024.24,
  author =	{Pourdamghani, Arash and Avin, Chen and Sama, Robert and Shiran, Maryam and Schmid, Stefan},
  title =	{{Hash \& Adjust: Competitive Demand-Aware Consistent Hashing}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.24},
  URN =		{urn:nbn:de:0030-drops-225607},
  doi =		{10.4230/LIPIcs.OPODIS.2024.24},
  annote =	{Keywords: Consistent hashing, demand-awareness, online algorithms}
}

Search Results

Documents authored by Shiran, Maryam

Hash-And-Adjust

Abstract

Cite as

Hash & Adjust: Competitive Demand-Aware Consistent Hashing

Abstract

Cite as

Thanks for your feedback!

Could not send message