Catálogo de publicaciones - libros

Byzantine-fault-tolerant service protocols like Q/U and FaB Paxos that optimistically order requests can provide increased efficiency and fault scalability. However, these protocols require ≥ 5b+ 1 servers (where is the maximum number of faults tolerated), owing to their use of ; this is 2 more servers than required by some non-optimistic protocols. In this paper, we present a family of opaque Byzantine quorum systems that require substantially fewer servers. Our analysis is novel in that it assumes Byzantine clients, anticipating that a faulty client may seek quorums that maximize the probability of error. Using this as motivation, we present an optional, novel protocol that allows probabilistic quorum systems to tolerate Byzantine clients. The protocol requires only one additional round of interaction between the client and the servers, and this round may be amortized over multiple operations. We consider actual error probabilities introduced by the probabilistic approach for concrete configurations of opaque quorum systems, and prove that the probability of error vanishes with as few as > 3.15 servers as and grow.

We examine the problem of detecting nested temporal predicates given the execution trace of a distributed program. We present a technique that allows efficient detection of a reasonably large class of predicates which we call the Basic Temporal Logic or BTL. Examples of valid BTL predicates are nested temporal predicates based on local variables with arbitrary negations, disjunctions, conjunctions and the possibly (EF or ) and invariant(AG or ) temporal operators. We introduce the concept of a , a compact representation of all global cuts which satisfy the predicate. We present an algorithm to compute a basis of a computation given any BTL predicate and prove that its time complexity is polynomial with respect to the number of processes and events in the trace although it is not polynomial in the size of the formula. We do not know of any other technique which detects a similar class of predicates with a time complexity that is polynomial in the number of processes and events in the system. We have implemented a predicate detection toolkit based on our algorithm that accepts offline traces from any distributed program.

We consider the problem of minimizing the number of ADMs in optical networks. All previous theoretical studies of this problem dealt with the off-line case, where all the lightpaths are given in advance. In a real-life situation, the requests (lightpaths) arrive at the network on-line, and we have to assign them wavelengths so as to minimize the switching cost. This study is thus of great importance in the theory of optical networks. We present an on-line algorithm for the problem, and show its competitive ratio to be . We show that this result is best possible in general. Moreover, we show that even for the ring topology network there is no on-line algorithm with competitive ratio better than . We show that on path topology the competitive ratio of the algorithm is . This is optimal for this topology. The lower bound on ring topology does not hold when the ring is of bounded size. We analyze the triangle topology and show a tight bound of for it. The analyzes of the upper bounds, as well as those for the lower bounds, are all using a variety of proof techniques, which are of interest by their own, and which might prove helpful in future research on the topic.

Three well studied progress conditions for implementing concurrent algorithms without locking are, obstruction-freedom, non-blocking and wait-freedom. Obstruction-freedom is weaker than non-blocking which, in turn, is weaker than wait-freedom. While obstruction-freedom and non-blocking have the potential to significantly improve the performance of concurrent applications, wait-freedom (although desirable) imposes too much overhead upon the implementation.

In [5], Fich, Luchangco, Moir, and Shavit have presented an interesting transformation that converts any obstruction-free algorithm into a wait-free algorithm when analyzed in the unknown-bound semi-synchronous model. The FLMS transformation uses atomic single-writer registers, atomic multi-writer registers and a single fetch-and-increment object, where is the number of processes.

We define a time complexity measure for analyzing such transformations, and prove that the time complexity of the FLMS transformation is in the number of processes . This leads naturally to the question of whether the time and/or space complexity of the FLMS transformation can be improved by relaxing the wait-freedom progress condition. We present several efficient transformations that convert any obstruction-free algorithm into a non-blocking algorithm when analyzed in the unknown-bound semi-synchronous model. All our transformations have (1) time complexity. One transformation uses atomic single-writer registers and a single compare-and-swap object; another transformation uses only a single compare-and-swap object which is assumed to support also a read operation.

Eventual failure detectors, such as or P, can make arbitrarily many mistakes before they start providing correct information. This paper shows that any detector implementable in a purely asynchronous system can be implemented as a function of only the order of most-recently heard-from processes. The finiteness of this representation means that eventual failure detectors can be enumerated and their relative strengths tested automatically. The results for systems with two and three processes are presented.

Implementability can also be modelled as a game between Prover and Disprover. This approach not only speeds up automatic implementability testing, but also results in shorter and more intuitive proofs. I use this technique to identify the new weakest failure detector - and prove its properties. Anti- outputs process ids and, while not necessarily stabilizing, it ensures that some correct process is eventually never output.

Recently, we challenged the belief that randomized Byzantine agreement protocols are inefficient, by designing, implementing and assessing the performance of a stack of protocols of that type [3]. That assessment lead us to a set of properties desirable for Byzantine asynchronous binary consensus protocols: (1) Strong validity . if all correct processes propose the same value v, the decision is v (values proposed by Byzantine processes are often useless); (2) Asynchrony . no time assumptions are made (systems are often prone to arbitrary delays); (3) Decentralization . there is no leader (leader elections have a great impact on performance); (4) Optimal resilience - n ≥ 3f +1 processes to tolerate f Byzantine (extra processes are costly); (5) Optimal message complexity . O(n2) (high impact on throughput); (6) Signature freedom (high impact of signatures based on public-key cryptography on the performance); (7) Early decision . in “nice” runs the protocol should decide in a few communication steps (good latency in the “normal” case).

Distributed Greedy Coloring is an interesting and intuitive variation of the standard Coloring problem. It still consists in coloring in a distributed setting each node of a given graph in such a way that two adjacent nodes do not get the same color, but it adds a further constraint. Given an order among the colors, a coloring is said to be if there does not exist a node for which its associated color can be replaced by a color of lower position in this order without violating the coloring property. We provide lower and upper bounds for this problem in Linial’s model and we relate them to other well-known problems, namely , , and . Whereas the best known upper bound for Coloring, MIS, and Greedy Coloring are the same, we prove a lower bound which is strong in the sense that it now makes a difference between Greedy Coloring and MIS.

There is a proliferation of models for distributed computing, consisting of both shared memory and message passing paradigms. Different communities adopt different variants as the “standard” model for their research setting. Since subtle changes in the communication model can result in significant changes to the solvability/unsolvability or to the complexity of various problems, it becomes imperative to understand the relationships between the many models. The situation becomes even more complicated when additional requirements such as fault-tolerance are added to the mix. This motivates us to determine exactly under what circumstances a program designed for one model and delivering some set of additional guarantees can be converted into an “equivalent” programs for a different model while delivering comparable guarantees. Once these relationships are understood, they can be exploited in system design.

This brief announcement focuses on interoperability of software transactions with ad hoc nonblocking algorithms. Specifically, we modify arbitrary nonblocking operations so that (1) they can be used both inside and outside transactions, (2) external uses serialize with transactions, and (3) internal uses succeed if and only if the surrounding transaction commits. Interoperability enables seemless integration with legacy code, atomic composition of nonblocking operations, and the equivalent of hand-optimized, closed nested transactions.

Fault-tolerant systems often require a means by which independent processes or processors can arrive at an exact mutual agreement of some kind. The work announced in this note studies the problem, which is a general tool for enabling actions that are performed at the same time at different sites of the system to be consistent with one another (e.g., mutual exlusion, firing squad etc). Suppose that we are interested in maintaining a simultaneously consistent view regarding a set of events E in the system. These are applicationdependent, but will typically record inputs that processes receive at various times, values that certain variables have at a given time, and faulty behavior in the form of failed or inconsistent message deliveries. A continuous consensus (CC) protocol maintains at all times k ≥ 0 a [] of events of at every site . In every run of this protocol the following three properties are required to hold, for all nonfaulty processes and .