The notion of completion has been proposed by Francez et al. to transform a non-equivalence-robust fairness notion to an equivalence-robust one while maintaining several properties of the source. However, a completion...
详细信息
The notion of completion has been proposed by Francez et al. to transform a non-equivalence-robust fairness notion to an equivalence-robust one while maintaining several properties of the source. However, a completion may not preserve strong-feasibility - a necessary and sufficient condition for a completion to be implementable. In this paper, we study the system requirement for a completion to be strongly-feasible, and determine the strongest implementable completion for every given fairness notion. Moreover, for most systems we obtain a fairness notion, which we refer to as SG+, such that SG+ is the strongest fairness notion that is both implementable and equivalence-robust. Finally, we show that, if equivalence-robustness is dropped, then in general it is impossible to define a fairness notion that is implementable and stronger than all other implementable fairness notions. This implies plenty of leeway in the design of fairness notions suitable for various applications.
We show the following time and space complexity lower bounds. Let I be any randomized non-blocking n-process implementation of any object in set A from any combination of objects in set B, where A = {increment, store-...
详细信息
We show the following time and space complexity lower bounds. Let I be any randomized non-blocking n-process implementation of any object in set A from any combination of objects in set B, where A = {increment, store-conditional bit, compare & swap, bounded-counter, single-writer atomic snapshot, fetch & add}, and B = {resettable consensus, register, swap register}. The space complexity of I is at least n - 1. Moreover, if I is deterministic, both its time and space complexity are at least n - 1. These lower bounds hold even if objects used in the implementation are of unbounded size. This improves on some of the Ω(√n) space complexity lower bounds of Fich, Herlihy & Shavit [FHS93]. It also shows the near optimality of some known wait-free implementations in terms of space complexity.
We address the problem of the impossibility of implementing synchronous fault-tolerant service specifications in asynchronous distributed systems. We introduce a method for weakening a synchronous service specificatio...
详细信息
ISBN:
(纸本)9780897918008
We address the problem of the impossibility of implementing synchronous fault-tolerant service specifications in asynchronous distributed systems. We introduce a method for weakening a synchronous service specification so that it becomes implementable in 'timed' asynchronous systems, that is, asynchronous systems in which processes have access to local hardware clocks. The method (1) adds to a service interface an exception indicator so that a client knows at any time if a server is currently providing its standard 'synchronous' semantics or some other specified exceptional semantics, (2) the standard behavior provided when the exception indicator does not signal an exception is 'similar' to the original synchronous service behavior, and (3) a server has to provide its standard semantics whenever the underlying communication and process services exhibit 'synchronous behavior'. To illustrate our method, we show how the specification of a synchronous datagram service and an internal clock synchronization service can be transformed into a fail-aware service specification. Further illustrations of the usefulness of fail-aware services are provided by describing a fail-safe railway crossing service and a fail-aware weak group membership service.
We consider the amount of randomness used in private distributed computations. Specifically, we show how n players can compute the exclusive-or (xor) of n boolean inputs t-privately, using only O(t2log(n/t)) random bi...
详细信息
ISBN:
(纸本)9780897918008
We consider the amount of randomness used in private distributed computations. Specifically, we show how n players can compute the exclusive-or (xor) of n boolean inputs t-privately, using only O(t2log(n/t)) random bits (the best known upper bound is O(tn)). We accompany this result by a lower bound on the number of random bits required to carry out this task;we show that any protocol solving this problem requires at least t random bits (again, this significantly improves over the known lower bounds). For the upper bound, we show how, given m subsets of {1, ..., n}, to construct in (deterministic) polynomial time a probability distribution of n random variables such that (1) the parity of random-variables in each of these m subsets is 0 or 1 with equal probability;and (2) the support of the distribution is of size at most 2m. This construction generalizes previously considered types of sample spaces (such as k-wise independent spaces and Schulman's spaces [S92]). We believe that this construction is of independent interest and may have various applications.
A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication and ...
详细信息
A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication and dissemination of information. When the elements may fail, a user of a distributed protocol needs to quickly find a quorum all of whose elements are alive, or evidence that no such quorum exists. This is done by probing the system elements, one at a time, to determine if they are alive or dead. This paper studies the probe complexity PC(S) of a quorum system S, defined as the worst case number of probes required to find a live quorum or to show its non-existence in S, using the best probing strategy. We show that for large classes of quorum systems, all n elements must be probed in the worst case. Such systems are called evasive. However, not all quorum systems are evasive;we demonstrate a system where O(log n) probes always suffice. Then we prove two lower bounds on the probe complexity in terms of the minimal quorum cardinality c(S) and the number of minimal quorums m(S). Finally we show a universal probe strategy which never makes more than c(S)2 probes, thus any system with c(S) &le √n is non-evasive.
distributed services are often provided by process groups for purposes of reliability, availability, and performance. It is often important for the members of a such a group to have a consistent view of the group'...
详细信息
distributed services are often provided by process groups for purposes of reliability, availability, and performance. It is often important for the members of a such a group to have a consistent view of the group's membership. For this reason, membership services are important part of many distributed software systems. Despite their importance, the specification and implementation of membership services in completely asynchronous systems has challenged researchers. Recent papers have demonstrated that earlier specifications are either unsolvable or admit trivial solutions. Informally, membership services require a kind of agreement among processes and it has been shown that it is impossible to solve many consensus-like problems in completely asynchronous systems. If the specification of membership service is nearly as strong as that of consensus, the specification will be unsolvable. If it is much weaker, its solutions may be useless. This paper provides an alternative specification of group membership and exhibits an algorithm that satisfies it. The specification is solvable in spite of earlier impossibility results because it permits executions in which all processes are evicted from the process group yet none ever learns that the group has become empty. This represents a weakening of earlier specifications, which required that, at all times, at least one process be aware of a group's membership. However, the new specification cannot be trivially satisfied because it prohibits a potential solution from arbitrarily removing a process for no reason. This specification thus represents an important step towards a better understanding of membership services in completely asynchronous systems.
A shared coin is one which n players 'simultaneously' hold and can later reveal, but no sufficiently small coalition can influence or a priori predict the outcome. Such coins are expensive to produce, yet many...
详细信息
A shared coin is one which n players 'simultaneously' hold and can later reveal, but no sufficiently small coalition can influence or a priori predict the outcome. Such coins are expensive to produce, yet many distributed protocols (including broadcast and Byzantine agreement) need them in bulk. We introduce a new paradigm for obtaining shared coins. We suggest distributed, pseudo-random bit generators (D-PRBGs). Analogous to a pseudo-random bit generator, which is an efficient algorithm to expand a short random seed into a long random looking sequence, a D-PRBG is a protocol which 'expands' a 'distributed seed,' consisting of shared coins, into a longer 'sequence' of shared coins, at low amortized cost per coin produced. Our main result is the construction of a D-PRBG in which this amortized cost (computation and communication) is significantly lower than the cost of any 'from-scratch' shared coin generation protocol. Furthermore, for applications which are executed repeatedly, we suggest bootstrapping: each run of the D-PRBG produces not only the coins for the current execution but also the seed for the next execution. Since the cost of the initial seed can now effectively be neglected, we get very fast coin generation. Underlying these constructions are some techniques of independent interest. We consider batch Verifiable Secret Sharing (VSS), where we need to do a large number of VSSs simultaneously. We provide a method in which the amortized cost per VSS is significantly lower than the cost of a VSS for any known VSS protocol.
The literature on software reuse assumes a software repository and a tool that helps the engineer to find appropriate components. Library search is based on the structure of the library and the meta-information about ...
详细信息
暂无评论