skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Quorum subsumption for heterogeneous quorum systems
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.  more » « less
Award ID(s):
1942711
PAR ID:
10491935
Author(s) / Creator(s):
; ;
Editor(s):
Oshman, Rotem
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Journal Name:
Leibniz International Proceedings in Informatics (LIPIcs):37th International Symposium on Distributed Computing (DISC 2023)
Subject(s) / Keyword(s):
Distributed Systems Impossibility Results Byzantine fault tolerance Computing methodologies → Distributed algorithms Computer systems organization → Availability Computer systems organization → Reliability
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021))
    We investigate the importance of quorum sensing in the success of house-hunting of emigrating Temnothorax ant colonies. Specifically, we show that the absence of the quorum sensing mechanism leads to failure of consensus during emigrations. We tackle this problem through the lens of distributed computing by viewing it as a natural distributed consensus algorithm. We develop an agent-based model of the house-hunting process, and use mathematical tools such as conditional probability, concentration bounds and Markov mixing time to rigorously prove the negative impact of not employing the quorum sensing mechanism on emigration outcomes. Our main result is a high probability bound for failure of consensus without quorum sensing in a two-new-nest environment, which we further extend to the general multiple-new-nest environments. We also show preliminary evidence that appropriate quorum sizes indeed help with consensus during emigrations. Our work provides theoretical foundations to analyze why Temnothorax ants evolved to utilize the quorum rule in their house-hunting process. 
    more » « less
  2. ; ; ; ; (, Computer Aided Verification)
    Lahiri, Shuvendu; Wang, Chao (Ed.)
    Inspired by distributed applications that use consensus or other agreement protocols for global coordination, we define a new computational model for parameterized systems that is based on a general global synchronization primitive and allows for global transition guards. Our model generalizes many existing models in the literature, including broadcast protocols and guarded protocols. We show that reachability properties are decidable for systems without guards, and give sufficient conditions under which they remain decidable in the presence of guards. Furthermore, we investigate cutoffs for reachability properties and provide sufficient conditions for small cutoffs in a number of cases that are inspired by our target applications 
    more » « less
  3. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Alistarh, Dan (Ed.)
    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. 
    more » « less
  4. ; ; (, Journal of Computer Security)
    Calzavara, Stefano; Naumann, David (Ed.)
    Availability is crucial to the security of distributed systems, but guaranteeing availability is hard, especially when participants in the system may act maliciously. Quorum replication protocols provide both integrity and availability: data and computation is replicated at multiple independent hosts, and a quorum of these hosts must agree on the output of all operations applied to the data. Unfortunately, these protocols have high overhead and can be difficult to calibrate for a specific application’s needs. Ideally, developers could use high-level abstractions for consensus and replication to write fault-tolerant code that is secure by construction. This paper presents Flow-Limited Authorization for Quorum Replication (FLAQR), a core calculus for building distributed applications with heterogeneous quorum replication protocols while enforcing end-to-end information security. Our type system ensures that well-typed FLAQR programs cannot fail (experience an unrecoverable error) in ways that violate their type-level specifications. We present noninterference theorems that characterize FLAQR’s confidentiality, integrity, and availability in the presence of consensus, replication, and failures, as well as a liveness theorem for the class of majority quorum protocols under a bounded number of faults. Additionally, we present an extension to FLAQR that supports secret sharing as a form of declassification and prove it preserves integrity and availability security properties. 
    more » « less
  5. ; ; ; ; ; (, Frontiers in Microbiology)
    null (Ed.)
    Members of the Rhizobiaceae , often carry multiple secondary replicons in addition to the primary chromosome with compatible repABC -based replication systems. Unlike secondary chromosomes and chromids, repABC -based megaplasmids and plasmids can undergo copy number fluctuations and are capable of conjugative transfer in response to environmental signals. Several Agrobacterium tumefaciens lineages harbor three secondary repABC -based replicons, including a secondary chromosome (often linear), the Ti (tumor-inducing) plasmid and the At megaplasmid. The Ti plasmid is required for virulence and encodes a conjugative transfer ( tra ) system that is strictly regulated by a subset of plant-tumor released opines and a well-described acyl-homoserine lactone (AHL)-based quorum-sensing mechanism. The At plasmids are generally not required for virulence, but carry genes that enhance rhizosphere survival, and these plasmids are often conjugatively proficient. We report that the At megaplasmid of the octopine-type strain A. tumefaciens 15955 encodes a quorum-controlled conjugation system that directly interacts with the paralogous quorum sensing system on the co-resident Ti plasmid. Both the pAt15955 and pTi15955 plasmids carry homologs of a TraI-type AHL synthase, a TraR-type AHL-responsive transcription activator, and a TraM-type anti-activator. The traI genes from both pTi15955 and pAt15955 can direct production of the inducing AHL (3-octanoyl- L -homoserine lactone) and together contribute to the overall AHL pool. The TraR protein encoded on each plasmid activates AHL-responsive transcription of target tra gene promoters. The pAt15955 TraR can cross-activate tra genes on the Ti plasmid as strongly as its cognate tra genes, whereas the pTi15955 TraR is preferentially biased toward its own tra genes. Putative tra box elements are located upstream of target promoters, and comparing between plasmids, they are in similar locations and share an inverted repeat structure, but have distinct consensus sequences. The two AHL quorum sensing systems have a combinatorial effect on conjugative transfer of both plasmids. Overall, the interactions described here have implications for the horizontal transfer and evolutionary stability of both plasmids and, in a broad sense, are consistent with other repABC systems that often have multiple quorum-sensing controlled secondary replicons. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email