Search

We consider the design and analysis of quorum systems over erasure coded warm data (with low frequency of writes and accesses in general) to guarantee sequential consistency under a fail-stop model while supporting atomic read-modify-write operations by multiple clients. We propose a definition of asymmetric quorum systems that suit the framework of coded data by explicitly exploiting the structural properties of code and instantiate it over distinct families of coding strategies: maximum distance separable (MDS) codes and codes with locality, and we indicate a mechanism for synchronizing stale nodes using differential updates, which again exploits the code structures. The proposed quorum system’s behavior is analyzed theoretically, exploring several aspects: viability of quorums under node unavailability; contention of resources between read and write operations; and quorum load. We complement these theoretical exploration with simulation based experiments to quantify the behavior of the proposed mechanism. The overall study demonstrates the feasibility and practicality of quorums over codes under practicable assumptions for achieving a stringent form of consistency, specifically, sequential consistency, while the stored data is being mutated by potentially multiple processes that might read and then modify the existing data. We achieve this in-place, without having to resort to store multiple versions of the data. Ministry of Education (MOE) Accepted version Anwitaman Datta’s research is supported by the Ministry of Education (MoE), Singapore, under its Academic Research Fund Tier 1 (Project ID: 2018- T1-002-076) for the project titled ‘StorEdge: Data store along a cloud-to-thing continuum with integrity and availability’.

We consider the problem of designing grid quorum systems for maximum distance separable (MDS) erasure code based distributed storage systems. Quorums are used as a mechanism to maintain consistency in replication based storage systems, for which grid quorums have been shown to produce optimal load characteristics. This motivates the study of grid quorums in the context of erasure code based distributed storage systems. We show how grid quorums can be built for erasure coded data, investigate the load characteristics of these quorum systems, and demonstrate how sequential consistency is achieved even in the presence of storage node failures. Ministry of Education (MOE) Published version Anwitaman Datta’s work has been supported by Singapore Ministry of Education (MOE) grant award number: 002180-00001 (Funder Reference Number: RG134/18) for the project titled ‘StorEdge: Data store along a cloud-to-thing continuum with integrity and availability’.

Die vorliegende Arbeit befasst sich mit den Auswirkungen der Corona-Krise auf die Arbeitsweise des Wiener Landtages. Die Autorin untersucht jene Punkte, die sich in der Arbeitsweise des Landtages und seiner Mitglieder krisenbedingt verändert haben. Dabei stellt sie fest, dass das formelle Recht (die Bundesverfassung, die Landesverfassung und die Geschäftsordnung des Landtages) im Wesentlichen unverändert geblieben ist, es aber dennoch zu teils einschneidenden Änderungen in der Arbeitsweise gekommen ist. Das betrifft insbesondere die Etablierung einer „Expressgesetzgebung“, den Verzicht beziehungsweise freiwillige Einschränkung auf parlamentarische Rechte. Das Spannungsfeld zum freien Mandat wird detailliert dargestellt. Fragen wie jene, ob Abgeordneten die Teilnahme an Sitzungen pandemiebedingt überhaupt verwehrt werden darf, werden erörtert. Vor diesem Hintergrund werden weitergehende Fragen, wie die Veränderung der Arbeitsteilung in einem Landtagsklub auf der einen Seite und die Themenverengung, die die Krise mit sich gebracht hat, auf der anderen Seite, besprochen. Ein besonderes Augenmerk legt die Autorin auf die Thematik der Verkürzung von oppositionellen Rechten und Möglichkeiten. Die Auswirkungen auf das Interpellationsrecht werden ebenso untersucht wie der erschwerte Kontakt zu den BürgerInnen. Letzterer ist der Autorin ein wichtiges Anliegen, zumal die Pandemie Grundrechtseingriffe in vielfältiger Gestalt mit sich bringt. In einem fundierten Ausblick weist die Erstellerin der Arbeit auf Möglichkeiten hin, wie in Zukunft in Krisensituationen, in denen das Zusammenwirken des Landtages erschwert ist, verfahren werden kann. Kritisch beleuchtet wird die ExpertInnenabhängigkeit der Politik ebenso wie die Tatsache, dass der Öffentlichkeit die Teilnahme an Sitzungen des Landtages und an Veranstaltungen verwehrt wurde. Zahlreiche Interviews belegen in der Praxis das, was die Autorin theoretisch ausgeführt hat. Die Auswertung erfolgte nach gängigen wissenschaftlichen Methoden. Der Bogen der Interviewten spannt sich hierbei von SpitzenpolitikerInnen, wie dem damaligen Vizebürgermeister von Wien, über Abgeordnete bis hin zu leitenden MitarbeiterInnen der operativen Klubverwaltung. In der Arbeit wird auch auf die theoretische Bedeutung der normativen und empirischen Demokratietheorien beleuchtet. Gerade in der Krise wird uns bewusst, welche Eingriffsmöglichkeiten der Staat gegenüber jedem/jeder Einzelnen hat. Die Bedingungen und die Intensität dieser Eingriffe können je nach Betrachtungsweise differenzieren. Vor diesem Hintergrund ist die Darstellung der Baugesetze der Bundesverfassung von besonderer Bedeutung. Im Lichte der Krise wird auch ein Augenmerk auf die Resilienz gesetzgebender Organe, die auch in Zeiten, in denen ein körperliches Zusammentreten nicht möglich ist, handlungsfähig sein müssen, gelegt. This paper deals with the effects of the Corona crisis on the functioning of the state parliament. The author examines those points that have changed in the functioning of the state parliament and its members as a result of the crisis. She finds out that the formal law (the federal constitution, the provincial constitution and the state parliament's rules of procedure) has remained essentially unchanged, but that there have nevertheless been changes, some of them drastic, in the way the parliament works. This applies in particular to the establishment of "express legislation," the renunciation or voluntary restriction of parliamentary rights. The conflict with the free mandate is also described in detail. Questions such as if members of parliament have might been denied to participate in meetings at all due to the pandemic have been discussed. Against this background, more far-reaching questions have been discussed, such as the change in the division of labor in a state parliamentary club on the one hand and the narrowing of topics brought about by the crisis on the other hand. The author pays particularly attention to the issue of the curtailment of oppositional rights and opportunities. The effects on the right of interpellation are examined, as is the more difficult contact with citizens. The latter is an important concern for the author, especially since the pandemic entails encroachments on fundamental rights in a variety of forms. In a well-founded forecast, the author points out several possibilities how to proceed in the future in crisis situations in which the cooperation of the state parliament is impeded. The dependence of politics on experts is critically examined, given the fact that the public has been denied the opportunity to participate in sessions of the state parliament. Numerous interviews prove in practice what the author has theoretically elaborated. The evaluation was carried out according to standard scientific methods. The interviewees ranged from top politicians, such as the deputy mayor of Vienna at the time, to members of the state parliament as well as senior members of the operational club administration. The paper also focuses on the theoretical significance of normative and empirical theories of democracy. Especially in times of crisis, we become aware of the possibilities of intervention the state has vis-à-vis each individual. The conditions and the intensity of these interventions might differ depending on the point of view. Against this background, the presentation of the building laws of the Federal Constitution is of particular importance. In the light of the crisis, attention is also paid to the resilience of legislative bodies, which must be able to act even in times when physical meetings are not possible. vorgelegt von: Angela Schütz Masterarbeit Wien, FH Campus Wien 2021

The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes. Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions., LIPIcs, Vol. 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), pages 10:1-10:16

Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory and broadcast primitives with processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust., LIPIcs, Vol. 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), pages 7:1-7:16

International audience; In this paper, we introduce a majority quorum system dedicated to p-m-n general threshold schemes where p, n and m are respectively the minimal number of chunks that provide some information (but not necessarily all) on the original data, the total number of nodes in which the chunks of an object are stored and the minimal number of nodes needed to retrieve the original data using this protocol. In other words, less than p chunks reveal absolutely no information about the original data and less than m chunks can't reconstruct the original data. The p-m-n general threshold schemes optimize the usage of storage resources by reducing the total size of data to write and ensure fault-tolerance up to (n é m) nodes failure. With such a data distribution, a specific value of m can be set to have a good tradeoff between resources utilization and fault-tolerance. The only drawback of such schemes is the lack of any consistency protocol. If fact, consistency protocols like classical majority quorum are based on full replication. To successfully read or write a data using the majority quorum protocol, an absolute majority of replicas must be read / written correctly. This condition ensures that any read and write operations will contain at least one common replica, which guarantees their consistency. However, when a threshold scheme is used, an adaptation is needed. In fact, classical majority quorum protocol can no longer ensure that m chunks will have the latest version. In this paper, we introduce a new majority quorum protocol dedicated to general threshold schemes. As for the classical majority quorum protocol, the complexity of the quorum size of our protocol is O(n) but the utilization of storage resources is greatly optimized.

In distributed storage systems like parallel file systems or storage virtualization middleware, data replication is the mainly used solution to implement data avaialability. The more replicas are distributed among nodes, the more robust is the storage system. However, the price to pay for this dependability becomes significant, due to both direct costs (the price of disks) and indirect costs (the energy consumption of this large amount of disks needed). In order to lower the disk space needed for a given availalbility, Erasure Resilient Codes (referred to as ERC after this) are of interest and start to be implemented in this context. However, the use of such codes involves some new problems in data management. In fact, if some constraints like data concurrency can be solved using classical ways, others like coherency protocols need some adaptations in order to fit this context. In this paper, we present an adaptation of trapezoid protocol in the context of ERC schemes (instead of full replication). This new quorum protocol shows an increase of storage space efficiency while maintaining a high level of availability for read and writes operations.

A network partition, which makes it impossible for some pairs of processes to communicate with each other, is one of the most serious network failures. Although the notion of k-coterie is introduced to design a k-mutual exclusion algorithm that is robust against network failures, the number of processes allowed to simultaneously access the critical section may fatally decrease once network partition occurs. We discuss how to construct a k-coterie such that the k-mutual exclusion algorithm adopting it is robust against a network 2-partition. To this end, we introduce the notion of complemental k-coterie, and show that complemental k-coteries meet our requirements. We then give methods for constructing complemental k-coteries, and show a necessary and sufficient condition for a k-coterie to be complemental.

In the $k$-set agreement problem, each process (in a set of $n$ processes) proposes a value and has to decide a proposed value in such a way that at most $k$ different values are decided. While this problem can easily be solved in asynchronous systems prone to $t$ process crashes when $k>t$, it cannot be solved when $k\leq t$. Since several years, the failure detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the $k$-set agreement problem in read/write shared-memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases $k=1$ (consensus) and $k=n-1$ (set agreement). This paper introduces a candidate for the general case. It presents a new failure detector class, denoted $\Pi_k$, and shows $\Pi_1=\Sigma\times \Omega$ (the weakest class for $k=1$), and $\Pi_{n-1}={\cal L}$ (the weakest class for $k=n-1$). Then, the paper investigates the structure of $\Pi_k$ and shows it is the combination of two failures detector classes denoted $\Sigma_k$ and $\Omega_k$ (that generalize the previous ``quorums'' and ``eventual leaders'' failure detectors classes). Finally, the paper proves that $\Sigma_k$ is a necessary requirement (as far as information on failure is concerned) to solve the $k$-set agreement problem in message-passing systems. The paper presents also a $\Pi_{n-1}$-based algorithm that solves the $(n-1)$-set agreement problem. This algorithm provides us with a new algorithmic insight on the way the $(n-1)$-set agreeement problem can be solved in asynchronous message-passing systems (insight from the point of view of the non-partitioning constraint defined by $\Sigma_{n-1}$).

This report presents Timed Quorum System (TQS), a new quorum system especially suited for large-scale and dynamic systems. TQS requires that two quorums intersect with high probability if they are used in the same small period of time. It proposes an algorithm that implements TQS and that verifies probabilistic atomicity: a consistency criterion that requires each operation to respect atomicity with high probability. This TQS implementation has quorum of size O(√nD) with expected access time of O(log√nD) message delays, where n measures the size of the system and D is a required parameter to handle dynamism.

We model a distributed system by a graph G=(V, E), where V represents the set of processes and E the set of bidirectional communication links between two processes. G may not be complete. A popular (distributed) mutual exclusion algorithm on G uses a coterie C(/spl sube/2/sup V/), which is a nonempty set of nonempty subsets of V (called quorums) such that, for any two quorums P, Q/spl isin/C, 1) P/spl cup/Q/spl ne/0 and 2) P/spl nsub/Q hold. The availability is the probability that the algorithm tolerates process and/or link failures, given the probabilities that a process and a link, respectively, are operational. The availability depends on the coterie used in the algorithm. This paper proposes a method to improve the availability by transforming a given coterie.

Mutual exclusion is a well-known problem that arise when multiple processes compete, in an uncoordinated way, for the acquisition of shared resources over a distributed system. In particular, k-mutual exclusion allows at most k processes to get one unit of the same resource simultaneously. These paradigms do not cover all the cases in which resource accesses must be serialized over a distributed system. There exist cases (e.g. the bandwidth of communication lines) where the amount of shared resource might differ from request to request (for example, audio and video communications). In this paper, we formalize this problem as the {h-out of-k mutual exclusion problem}, in which each request concerns some number h $(1 \le h \le k)$ of units of shared resource and no unit is allocated to multiple processes at the same time. We present a general scheme for a {\em quorum-based h-out of-k mutual exclusion algorithm} that relies on a collection of quorums called {\em $k$-arbiter}. Several examples of $k$-arbiters are discussed, two particular classes of k-arbiters are investigated and a metric to evaluate the resiliency with respect to failures of k-arbiters is also given.

In the k -set agreement problem, each process (in a set of n processes) proposes a value and has to decide a proposed value in such a way that at most k different values are decided. While this problem can easily be solved in asynchronous systems prone to t process crashes when k > t , it cannot be solved when k ≤ t . For several years, the failure-detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the k -set agreement problem in read/write shared memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases k = 1 (consensus) and k = n − 1 (set agreement). This paper presents four contributions whose aim is to help pave the way to discover the weakest failure detector class for k -set agreement in message-passing systems. These contributions are the following. (a) The first is a new failure detector class, denoted Π k , that is such that Π 1 = Σ × Ω (the weakest class for k = 1 ), and Π n − 1 = L (the weakest class for k = n − 1 ). (b) The second is an investigation of the structure of Π k that shows that Π k is the combination of two failure detector classes Σ k (that is new) and Ω k (they generalize the previous “quorums” and “eventual leaders” failure detector classes, respectively). (c) The third contribution concerns Σ k that is shown to be a necessary requirement (as far as information on failure is concerned) to solve the k -set agreement problem in message-passing systems. (d) Finally, the last contribution is a Π n − 1 -based algorithm that solves the ( n − 1 ) -set agreement problem. This algorithm provides us with a new algorithmic insight on the way the ( n − 1 ) -set agreement problem can be solved in asynchronous message-passing systems. It is hoped that these contributions will help discover the weakest failure detector class for k -set agreement in message-passing systems.

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contention. This paper initiates the first study of quorum systems that help design such implementations. Namely, our study of quorum systems encompasses, at the same time, the optimal resilience of distributed object implementations (just like traditional quorum systems), as well as their {\em optimal best-case complexity} (unlike traditional quorum systems). We introduce the notion of a \emph{refined} quorum system (RQS) of some set $S$ as a set of three refined classes of subsets (quorums) of $S$: first class quorums are also second class quorums, which are also third class quorums. First class quorums have large intersections with all other quorums, second class quorums might have slightly smaller intersections with those of the third class, the latter simply correspond to traditional quorums. Intuitively, under uncontended and synchronous conditions, a distributed object implementation would expedite an operation if a quorum of the first class is accessed, then degrade gracefully depending on whether a quorum of the second or the third class is accessed. The latter case corresponds somehow to the worst situation under uncontended and synchronous conditions. Our refined quorum system is devised assuming a general adversary structure, and this basically implies that algorithms relying on such a quorum system do not need to make the assumption of independent process failures, often questioned in practice. We illustrate the power of refined quorums by introducing two new optimal distributed object implementations: a Byzantine-resilient atomic storage algorithm and a Byzantine-resilient consensus algorithm. Both match previously established resilience and best-case complexity lower bounds, closing open gaps, as well as new complexity bounds we establish here.