6 Search Results for "Lesani, Mohsen"

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.8
Weaker Assumptions for Asymmetric Trust

Authors: Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
In distributed systems with asymmetric trust, each participant is free to make its own trust assumptions about others, captured by an asymmetric quorum system. This contrasts with ordinary, symmetric quorum systems and threshold models, where trust assumptions are uniformly shared among participants. Fundamental problems like reliable broadcast and consensus are unsolvable in the asymmetric model if quorum systems satisfy only the classical properties of consistency and availability. Existing approaches overcome this by introducing stronger assumptions. We show that some of these assumptions are overly restrictive, so much so that they effectively eliminate the benefits of asymmetric trust. To address this, we propose a new approach to characterize asymmetric problems and, building upon it, present algorithms for reliable broadcast and consensus that require weaker assumptions than previous solutions. Our methods are general and can be extended to other core problems in systems with asymmetric trust.
Cite as

Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis. Weaker Assumptions for Asymmetric Trust. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2025.8,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Kamp, Simon Holmgaard and Villacis, Juan},
  title =	{{Weaker Assumptions for Asymmetric Trust}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.8},
  URN =		{urn:nbn:de:0030-drops-251812},
  doi =		{10.4230/LIPIcs.OPODIS.2025.8},
  annote =	{Keywords: Asymmetric Trust, Quorum Systems, Reliable Broadcast, Consensus}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.50
Brief Announcement: Weaker Assumptions for Asymmetric Trust

Authors: Christian Cachin and Juan Villacis

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In protocols with asymmetric trust, each participant is free to make its own trust assumptions about others, captured by an asymmetric quorum system. This contrasts with ordinary, symmetric quorum systems and threshold models, where trust assumptions are uniformly shared among participants. Fundamental problems like reliable broadcast and consensus are unsolvable in the asymmetric model if quorum systems satisfy only the classical properties of consistency and availability. As a result, existing solutions introduce stronger assumptions to circumvent this limitation. We show that some requirements used by state-of-the-art approaches are overly restrictive, so much so that they effectively eliminate the benefits of asymmetric trust. To address this, we propose a new approach to characterize asymmetric problems and, building upon it, present an asymmetric asynchronous unauthenticated reliable broadcast algorithm that significantly weakens the assumptions needed to solve the problem. Our techniques are general and can be readily adapted to other core problems in the asymmetric trust setting.
Cite as

Christian Cachin and Juan Villacis. Brief Announcement: Weaker Assumptions for Asymmetric Trust. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 50:1-50:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2025.50,
  author =	{Cachin, Christian and Villacis, Juan},
  title =	{{Brief Announcement: Weaker Assumptions for Asymmetric Trust}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{50:1--50:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.50},
  URN =		{urn:nbn:de:0030-drops-248667},
  doi =		{10.4230/LIPIcs.DISC.2025.50},
  annote =	{Keywords: Asymmetric Trust, Quorum Systems, Reliable Broadcast}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.4
Ensuring Convergence and Invariants Without Coordination

Authors: Dina Borrego, Nuno Preguiça, Elisa Gonzalez Boix, and Carla Ferreira

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
The CAP theorem demonstrates a trade-off between consistency and availability (and, by extension, latency) in systems where network partitions are unavoidable, such as in cloud computing and local-first software. While adopting weak consistency can preserve availability, it may result in inconsistencies that compromise application correctness. Replicated data types provide a principled, coordination-free approach to guarantee convergence but do not consider application invariants. Existing methods for maintaining invariants in replicated systems either rely on coordination - undermining the benefits of weak consistency - or suffer from limited applicability. This paper introduces the No-Op framework, a generic approach for enforcing consistency without coordination while guaranteeing both convergence and invariant preservation. The core idea of the No-Op approach is to resolve conflicts among concurrent operations by prioritising one operation over the other according to programmer-defined conflict resolution policies. This prioritisation transforms the less-preferred operation into a no-side-effect operation, ensuring conflict-free execution. We formalise the model underlying the No-Op framework and introduce a replication protocol built upon it, accompanied by a formal proof of correctness for both the framework and the protocol. Furthermore, we demonstrate the framework’s applicability by showcasing the design of widely used replicated data types and the preservation of a wide range of application invariants.
Cite as

Dina Borrego, Nuno Preguiça, Elisa Gonzalez Boix, and Carla Ferreira. Ensuring Convergence and Invariants Without Coordination. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 4:1-4:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{borrego_et_al:LIPIcs.ECOOP.2025.4,
  author =	{Borrego, Dina and Pregui\c{c}a, Nuno and Gonzalez Boix, Elisa and Ferreira, Carla},
  title =	{{Ensuring Convergence and Invariants Without Coordination}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{4:1--4:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.4},
  URN =		{urn:nbn:de:0030-drops-232978},
  doi =		{10.4230/LIPIcs.ECOOP.2025.4},
  annote =	{Keywords: distributed systems, conflict resolution, RDTs, invariant preservation}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.52
Brief Announcement: Reconfigurable Heterogeneous Quorum Systems

Authors: Xiao Li and Mohsen Lesani

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
In contrast to proof-of-work replication, Byzantine quorum systems maintain consistency across replicas with higher throughput, modest energy consumption, and deterministic liveness guarantees. If complemented with heterogeneous trust and open membership, they have the potential to serve as blockchains backbone. This paper presents a general model of heterogeneous quorum systems where each participant can declare its own quorums, and captures the consistency, availability and inclusion properties of these systems. In order to support open membership, it then presents reconfiguration protocols for heterogeneous quorum systems including joining and leaving of a process, and adding and removing of a quorum, and further, proves their correctness in the face of Byzantine attacks. The design of the protocols is informed by the trade-offs that the paper proves for the properties that reconfigurations can preserve. The paper further presents a graph characterization of heterogeneous quorum systems, and its application for reconfiguration optimization.
Cite as

Xiao Li and Mohsen Lesani. Brief Announcement: Reconfigurable Heterogeneous Quorum Systems. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 52:1-52:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.DISC.2024.52,
  author =	{Li, Xiao and Lesani, Mohsen},
  title =	{{Brief Announcement: Reconfigurable Heterogeneous Quorum Systems}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{52:1--52:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.52},
  URN =		{urn:nbn:de:0030-drops-212804},
  doi =		{10.4230/LIPIcs.DISC.2024.52},
  annote =	{Keywords: Quorum Systems, Reconfiguration, Heterogeneity}
}
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.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.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 Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2024
  • 1 2023
  • 1 2019

  • Refine by Author
  • 3 Lesani, Mohsen
  • 2 Cachin, Christian
  • 2 Li, Xiao
  • 2 Villacis, Juan
  • 1 Amores-Sesar, Ignacio
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 3 Computer systems organization → Availability
  • 3 Theory of computation → Distributed algorithms
  • 2 Computer systems organization → Reliability
  • 2 Computing methodologies → Distributed algorithms
  • 1 Computing methodologies → Distributed computing methodologies
  • Show More...

  • Refine by Keyword
  • 3 Quorum Systems
  • 2 Asymmetric Trust
  • 2 Reliable Broadcast
  • 1 Byzantine fault tolerance
  • 1 Concurrent Programming
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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