2 Search Results for "Lesani, Mohsen"

Document
DOI: 10.4230/LIPIcs.DISC.2023.28
Quorum Subsumption for Heterogeneous Quorum Systems

Authors: Xiao Li, Eric Chan, and Mohsen Lesani

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Byzantine quorum systems provide higher throughput than proof-of-work and incur modest energy consumption. Further, their modern incarnations incorporate personalized and heterogeneous trust. Thus, they are emerging as an appealing candidate for global financial infrastructure. However, since their quorums are not uniform across processes anymore, the properties that they should maintain to support abstractions such as reliable broadcast and consensus are not well-understood. It has been shown that the two properties quorum intersection and availability are necessary. In this paper, we prove that they are not sufficient. We then define the notion of quorum subsumption, and show that the three conditions together are sufficient: we present reliable broadcast and consensus protocols, and prove their correctness for quorum systems that provide the three properties.
Cite as

Xiao Li, Eric Chan, and Mohsen Lesani. Quorum Subsumption for Heterogeneous Quorum Systems. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.DISC.2023.28,
  author =	{Li, Xiao and Chan, Eric and Lesani, Mohsen},
  title =	{{Quorum Subsumption for Heterogeneous Quorum Systems}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.28},
  URN =		{urn:nbn:de:0030-drops-191541},
  doi =		{10.4230/LIPIcs.DISC.2023.28},
  annote =	{Keywords: Distributed Systems, Impossibility Results, Byzantine fault tolerance}
}
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-dev.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}
}
  • Refine by Author
  • 2 Lesani, Mohsen
  • 1 Chan, Eric
  • 1 Li, Xiao
  • 1 Pourdamghani, Arash
  • 1 Taheri, Mohammad

  • Refine by Classification
  • 1 Computer systems organization → Availability
  • 1 Computer systems organization → Reliability
  • 1 Computing methodologies → Distributed algorithms
  • 1 Software and its engineering → Concurrent programming structures
  • 1 Software and its engineering → Memory management
  • Show More...

  • Refine by Keyword
  • 1 Byzantine fault tolerance
  • 1 Concurrent Programming
  • 1 Distributed Systems
  • 1 Fence Insertion
  • 1 Impossibility Results
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact