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}
}

Document

DOI: 10.4230/LIPIcs.DISC.2019.34

Polynomial-Time Fence Insertion for Structured Programs

Authors: Mohammad Taheri, Arash Pourdamghani, and Mohsen Lesani

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract

To enhance performance, common processors feature relaxed memory models that reorder instructions. However, the correctness of concurrent programs is often dependent on the preservation of the program order of certain instructions. Thus, the instruction set architectures offer memory fences. Using fences is a subtle task with performance and correctness implications: using too few can compromise correctness and using too many can hinder performance. Thus, fence insertion algorithms that given the required program orders can automatically find the optimum fencing can enhance the ease of programming, reliability, and performance of concurrent programs. In this paper, we consider the class of programs with structured branch and loop statements and present a greedy and polynomial-time optimum fence insertion algorithm. The algorithm incrementally reduces fence insertion for a control-flow graph to fence insertion for a set of paths. In addition, we show that the minimum fence insertion problem with multiple types of fence instructions is NP-hard even for straight-line programs.

Cite as

Mohammad Taheri, Arash Pourdamghani, and Mohsen Lesani. Polynomial-Time Fence Insertion for Structured Programs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{taheri_et_al:LIPIcs.DISC.2019.34,
  author =	{Taheri, Mohammad and Pourdamghani, Arash and Lesani, Mohsen},
  title =	{{Polynomial-Time Fence Insertion for Structured Programs}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.34},
  URN =		{urn:nbn:de:0030-drops-113412},
  doi =		{10.4230/LIPIcs.DISC.2019.34},
  annote =	{Keywords: Fence Insertion, Synchronization, Concurrent Programming}
}

Search Results

Documents authored by Pourdamghani, Arash

Hash-And-Adjust

Abstract

Cite as

Hash & Adjust: Competitive Demand-Aware Consistent Hashing

Abstract

Cite as

Polynomial-Time Fence Insertion for Structured Programs

Abstract

Cite as

Thanks for your feedback!

Could not send message