3 Search Results for "Keshav, S."

Document
DOI: 10.4230/LIPIcs.SEA.2023.15
FREIGHT: Fast Streaming Hypergraph Partitioning

Authors: Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.
Cite as

Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz. FREIGHT: Fast Streaming Hypergraph Partitioning. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 15:1-15:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eyubov_et_al:LIPIcs.SEA.2023.15,
  author =	{Eyubov, Kamal and Fonseca Faraj, Marcelo and Schulz, Christian},
  title =	{{FREIGHT: Fast Streaming Hypergraph Partitioning}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.15},
  URN =		{urn:nbn:de:0030-drops-183657},
  doi =		{10.4230/LIPIcs.SEA.2023.15},
  annote =	{Keywords: Hypergraph partitioning, graph partitioning, edge partitioning, streaming}
}
Document
DOI: 10.4230/OASIcs.FAB.2021.4
TimeFabric: Trusted Time for Permissioned Blockchains

Authors: Aritra Mitra, Christian Gorenflo, Lukasz Golab, and S. Keshav

Published in: OASIcs, Volume 92, 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)

Abstract
As the popularity of blockchains continues to rise, blockchain platforms must be enhanced to support new application needs. In this paper, we propose one such enhancement that is essential for financial applications and online marketplaces - support for time-based logic such as verifying deadlines or expiry dates and examining a time window of recent account activity. We present a lightweight solution to reach consensus on the current time without relying on external time oracles. Our solution assigns timestamps to blocks at transaction validation time and maintains a cache reflecting the effects of recent transactions. We implement a proof-of-concept prototype, called TimeFabric, in Hyperledger Fabric, a popular permissioned blockchain platform, and experimentally demonstrate high throughput and minimal overhead (approximately 3%) of maintaining trusted time. We also demonstrate a 2x performance improvement due to the cache, compared to reconstructing account histories from the ledger.
Cite as

Aritra Mitra, Christian Gorenflo, Lukasz Golab, and S. Keshav. TimeFabric: Trusted Time for Permissioned Blockchains. In 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021). Open Access Series in Informatics (OASIcs), Volume 92, pp. 4:1-4:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mitra_et_al:OASIcs.FAB.2021.4,
  author =	{Mitra, Aritra and Gorenflo, Christian and Golab, Lukasz and Keshav, S.},
  title =	{{TimeFabric: Trusted Time for Permissioned Blockchains}},
  booktitle =	{4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)},
  pages =	{4:1--4:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-196-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{92},
  editor =	{Gramoli, Vincent and Sadoghi, Mohammad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2021.4},
  URN =		{urn:nbn:de:0030-drops-139906},
  doi =		{10.4230/OASIcs.FAB.2021.4},
  annote =	{Keywords: Permissioned Blockchain, Timestamp, Clock, Sliding Window, Hyerpleger Fabric}
}
Document
DOI: 10.4230/DagSemRep.237
Instruction-Level Parallelism and Parallelizing Compilation (Dagstuhl Seminar 99161)

Authors: D. K. Arvind, Kemal Ebcioglu, Christian Lengauer, Keshav Pingali, and Robert S. Schreiber

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

D. K. Arvind, Kemal Ebcioglu, Christian Lengauer, Keshav Pingali, and Robert S. Schreiber. Instruction-Level Parallelism and Parallelizing Compilation (Dagstuhl Seminar 99161). Dagstuhl Seminar Report 237, pp. 1-30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (1999)

Copy BibTex To Clipboard

@TechReport{arvind_et_al:DagSemRep.237,
  author =	{Arvind, D. K. and Ebcioglu, Kemal and Lengauer, Christian and Pingali, Keshav and Schreiber, Robert S.},
  title =	{{Instruction-Level Parallelism and Parallelizing Compilation (Dagstuhl Seminar 99161)}},
  pages =	{1--30},
  ISSN =	{1619-0203},
  year =	{1999},
  type = 	{Dagstuhl Seminar Report},
  number =	{237},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.237},
  URN =		{urn:nbn:de:0030-drops-151237},
  doi =		{10.4230/DagSemRep.237},
}
  • Refine by Author
  • 1 Arvind, D. K.
  • 1 Ebcioglu, Kemal
  • 1 Eyubov, Kamal
  • 1 Fonseca Faraj, Marcelo
  • 1 Golab, Lukasz
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 Clock
  • 1 Hyerpleger Fabric
  • 1 Hypergraph partitioning
  • 1 Permissioned Blockchain
  • 1 Sliding Window
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 1999
  • 1 2021
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact