Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantifying and Generalizing the CAP Theorem
170
0
0.0
(
0
)
Added by
Marten Lohstroh
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In distributed applications, Brewers CAP theorem tells us that when networks become partitioned, there is a tradeoff between consistency and availability. Consistency is agreement on the values of shared variables across a system, and availability is the ability to respond to reads and writes accessing those shared variables. We quantify these concepts, giving numerical values to inconsistency and unavailability. Recognizing that network partitioning is not an all-or-nothing proposition, we replace the P in CAP with L, a numerical measure of apparent latency, and derive the CAL theorem, an algebraic relation between inconsistency, unavailability, and apparent latency. This relation shows that if latency becomes unbounded (e.g., the network becomes partitioned), then one of inconsistency and unavailability must also become unbounded, and hence the CAP theorem is a special case of the CAL theorem. We describe two distributed coordination mechanisms, which we have implemented as an extension of the Lingua Franca coordination language, that support arbitrary tradeoffs between consistency and availability as apparent latency varies. With centralized coordination, inconsistency remains bounded by a chosen numerical value at the cost that unavailability becomes unbounded under network partitioning. With decentralized coordination, unavailability remains bounded by a chosen numerical quantity at the cost that inconsistency becomes unbounded under network partitioning. Our centralized coordination mechanism is an extension of techniques that have historically been used for distributed simulation, an application where consistency is paramount. Our decentralized coordination mechanism is an extension of techniques that have been used in distributed databases when availability is paramount.
rate research
Read More
Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish consensus (e.g., longest chain rules vs. BFT-inspired protocols). These fundamental differences have hindered apples-to-apples comparisons between different categories of blockchain protocols and, in turn, the development of theory to formally discuss their relative merits. This paper presents a parsimonious abstraction sufficient for capturing and comparing properties of many well-known permissionless blockchain protocols, simultaneously capturing essential properties of both proof-of-work and proof-of-stake protocols, and of both longest-chain-type and BFT-type protocols. Our framework blackboxes the precise mechanics of the user selection process, allowing us to isolate the properties of the selection process which are significant for protocol design. We illustrate our frameworks utility with two results. First, we prove an analog of the CAP theorem from distributed computing for our framework in a partially synchronous setting. This theorem shows that a fundamental dichotomy holds between protocols (such as Bitcoin) that are adaptive, in the sense that they can function given unpredictable levels of participation, and protocols (such as Algorand) that have certain finality properties. Second, we formalize the idea that proof-of-work (PoW) protocols and non-PoW protocols can be distinguished by the forms of permission that users are given to carry out updates to the state.
Longest-chain blockchain protocols, such as Bitcoin, guarantee liveness even when the number of actively participating users is variable, i.e., they are adaptive. However, they are not safe under network partitions, i.e., they do not guarantee finality. On the other hand, classical blockchain protocols, like PBFT, achieve finality but not adaptivity. Indeed, the CAP theorem in the context of blockchains asserts that no protocol can simultaneously offer both adaptivity and finality. We propose a new blockchain protocol, called the checkpointed longest chain, that offers individual users the choice between finality and adaptivity instead of imposing it at a system-wide level. This protocols salient feature is that it supports two distinct confirmation rules: one that guarantees adaptivity and the other finality. The more optimistic adaptive rule always confirms blocks that are marked as finalized by the more conservative rule, and may possibly confirm more blocks during variable participation levels. Clients (users) make a local choice between the confirmation rules as per their personal preference, while miners follow a fixed block proposal rule that is consistent with both confirmation rules. The proposed protocol has the additional benefit of intrinsic validity: the finalized blocks always lie on a single blockchain, and therefore miners can attest to the validity of transactions while proposing blocks. Our protocol builds on the notion of a finality gadget, a popular technique for adding finality to longest-chain protocols.
We introduce the notion of $k$-trace and use interpolation of operators to prove the joint concavity of the function $(A,B)mapstotext{Tr}_kbig[(B^frac{qs}{2}K^*A^{ps}KB^frac{qs}{2})^{frac{1}{s}}big]^frac{1}{k}$, which generalizes Liebs concavity theorem from trace to a class of homogeneous functions $text{Tr}_k[cdot]^frac{1}{k}$. Here $text{Tr}_k[A]$ denotes the $k_{text{th}}$ elementary symmetric polynomial of the eigenvalues of $A$. This result gives an alternative proof for the concavity of $Amapstotext{Tr}_kbig[exp(H+log A)big]^frac{1}{k}$ that was obtained and used in a recent work to derive expectation estimates and tail bounds on partial spectral sums of random matrices.
The celebrated 1999 Asynchronous Computability Theorem (ACT) of Herlihy and Shavit characterized the distributed tasks that are wait-free solvable, and thus uncovered a deep connection with algebraic topology. We present a novel interpretation of this theorem, through the notion of continuous task, defined by an input/output specification that is a continuous function. To do so, we introduce a chromatic version of a foundational result for algebraic topology: the simplicial approximation theorem. In addition to providing a different proof of the ACT, the notion of continuous task seems interesting in itself. Indeed, besides the fact that certain distributed problems are naturally specified by continuous functions, continuous tasks have an expressive power that also allows to specify the density of desired outputs for each combination of possible inputs,for example.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
