In this paper, we present a generalization of the threshold model for process replication for a model of dependent process failures. This model is based on two abstractions, called cores and survivor sets. We show two equivalent properties that assume cores and survivor sets, and use these properties to derive lower bounds for process replication. We also conjecture that a class of protocols in distributed computing can be be automatically translated to our model by simply modifying predicates in these protocols.

Pre-2018 CSE ID: CS2003-0743

Leader election is an important primitive in fault-tolerant distributed computing. In this paper, we propose a new specification for Leader Election motivated by the development of systems with the Primary-Backup approach to fault tolerance. We repeat a lower bound result on process replication that was previously shown, and then provide a new algorithm. There are three main contributions in the derivation of this algorithm. First, we show that a known lower bound is actually tight. Second, we design it using our model of dependent failures based on cores and survivor sets, thus enabling the use of such an algorithm in heterogeneous settings and illustrating the process of designing algorithms in this model. Finally, due to weaker requirements, this algorithm uses less replication than previous algorithms for leader election for receive-omission failures.

Pre-2018 CSE ID: CS2005-0812

In this paper, we explore new failure models for multi-site systems, which are systems characterized by a collection of sites spread across a wide area network, each site formed by a set of computing nodes running processes. In particular, we introduce two failure models that allow sites to fail, and we use them to derive coteries. We argue that these coteries have better availability than quorums formed by a majority of processes, which are known for having best availability when process failures are independent and identically distributed. To motivate introducing site failures explicitly into a failure model, we present availability data from a production multi-site system, showing that sites are frequently unavailable. We then discuss the implementability of our abstract models, showing possibilities for obtaining these models in practice. Finally, we present evaluation results from running an implementation of the Paxos algorithm on PlanetLab using different quorum constructions. The results show that our constructions have substantially better availability and response time compared to majority coteries.

Pre-2018 CSE ID: CS2005-0831

Leader Election is an important primitive in fault-tolerant distributed computing. In this paper, we propose a new, weaker specification of the Leader Election problem motivated by the design of Primary-Backup protocols for receive-omission failures. The lower bound for this problem assuming a threshold on the number of failures has been known for many years, but this bound was not known to be tight. We repeat this result and generalize the bound to our model of dependent failures. We then propose and show the correctness of an algorithm that solves Weak Leader Election. There are three main contributions in the derivation of this algorithm. First, we show that a known lower bound is actually tight. Second, we design it using our model of dependent failures based on cores and survivor sets, thus enabling the use of such an algorithm in heterogeneous settings and illustrating the process of designing algorithms in this model. Finally, due to weaker requirements, this algorithm uses less replication than previous algorithms.

Pre-2018 CSE ID: CS2005-0829

We present a new abstraction to replace the $t$ of $n$ assumption used in designing fault-tolerant algorithms. This abstraction models dependent process failures yet it is as simple to use as the $t$ of $n$ assumption. To illustrate this abstraction, we look at the Consensus problem for synchronous systems with both crash and arbitrary process failures. By considering failure correlations, we are able to reduce latency and enable the solution of Consensus for system configurations in which it is not possible when forced to use protocols designed under the $t$ of $n$ assumption. We give lower bounds for the number of rounds and replication requirements that are sufficient to solve Consensus. We show that, in general, the lower bound for number of rounds in the worst case assuming crash failures is different from the lower bound assuming arbitrary failures given the same system configuration. This is in contrast with the traditional result under the $t$ of $n$ assumption.

Pre-2018 CSE ID: CS2002-0722

We present an abstraction to replace the t of n assumption used in designing fault-tolerant algorithms. This abstraction models dependent process failures yet it is as simple to use as the t of n assumption. To illustrate this abstraction, we consider the Consensus problem for synchronous and asynchronous systems with both crash and arbitrary process failures. We give process replication requirements for our model and describe algorithms for system configurations satisfying these requirements. By considering failure correlations, we enable the solution of Consensus for system configurations with arbitrary failures in which it is not possible when forced to use protocols designed under the t of n assumption. Additionally, we are able to solve Consensus with fewer rounds in synchronous systems with crash failures.

Pre-2018 CSE ID: CS2003-0737

In this paper, we generalize the lower bound on the number of rounds for Consensus algorithms assuming that processes fail dependently. This lower bound is general in the sense that it is independent of the failure assumptions for processes. In order to instantiate it, one needs to provide a necessary condition on process replication for a given failure model in terms of our abstractions to represent dependent failures. A surprising corollary of our generalization is that the lower bound on the number of rounds, in general, differs between the crash and the arbitrary failure models.

Pre-2018 CSE ID: CS2003-0734

We study the problem of reliable dissemination information in a wide area network. Traditional reliable broadcast protocols provide high reliability but do not scale well. Gossip-based protocols appear to be a viable approach. They have been developed to address scalability while still providing high reliability of message delivery. However, gossip protocols either ignore the topology of the wide-area network and thus incur a large load on some network elements or can suffer from a low reliability because they do not take the connectivity of the wide-area network into account. We present a new gossip protocol, called directional gossip, that uses flooding when necessary to attain good reliability and that uses gossip when flooding (and hence its inherent high overhead) is not needed. The determination of when to use flooding or gossip is done dynamically.

Pre-2018 CSE ID: CS1999-0622

In this paper we consider the problem of detecting whether a compromised router is maliciously manipulating its stream of packets. In particular, we are concerned with a simple yet effective attack in which a router selectively drops packets destined for some victim. Unfortunately, it is quite challenging to attribute a missing packet to a malicious action because normal network congestion can produce the same effect. Modern networks routinely drop packets when the load temporarily exceeds a router's buffering capacity. Previous detection protocols have tried to address this problem using a user-defined threshold: too many dropped packets implies malicious intent. However this heuristic is fundamentally unsound; setting this threshold is, at best, an art and will necessarily create unnecessary false positives or mask highly-focused attacks. We have designed, developed and implemented a compromised router detection protocol that dynamically infers, based on measured traffic rates and buffer sizes, the number of congestive packet losses that will occur. Once the ambiguity from congestion is removed, subsequent packet losses can be attributed to malicious actions. We have tested our protocol in Emulab and have studied its effectiveness in differentiating attacks from legitimate network behavior.

Pre-2018 CSE ID: CS2007-0889