Traditionally, fault-tolerant systems assume that failures are independent, often expressed as a threshold on the number of failures. This assumption, however, is increasingly unrealistic for current distributed systems. This dissertation presents a model of dependent failures based on two abstractions: cores and survivor sets. Cores are minimal sets of processes such that at least one process is correct in every execution. Survivor sets are minimal sets of processes such that in every execution at least one survivor set contains only correct processes. This model has both theoretical and practical use. Theoretically, this model enables more flexible designs of distributed algorithms. This flexibility often improves efficiency; for example, it enables systems to meet reliability goals with fewer processes. Practically, I apply these replication techniques for multi-site systems that tolerate site failures, and for cooperative backup systems that tolerate Internet attacks. Multi-site systems, such as grid systems, experience failures that render all the processes in a site unavailable. These failures are often caused by failures of shared resources. Under such site failures, previous availability results on replication techniques, such as quorum systems, no longer necessarily hold. Using a failure model that explicitly captures dependent failures, I develop techniques for selecting replicas and forming quorums that do have optimal availability in multi-site systems. Internet attacks by worms and viruses can infect a large number of hosts, resulting in catastrophic failures. To cope with such attacks, I propose a new approach for designing distributed systems called informed replication. Informed replication uses a model of correlated failures to exploit software diversity. To demonstrate this approach, I design and evaluate a cooperative backup service called The Phoenix Recovery System. Phoenix uses heuristics to select replicas that provide excellent reliability guarantees, result in low degree of replication, limit the storage burden on each host in the system, and lend themselves to a distributed implementation. Incorporating dependent failures into the design of systems and algorithms therefore results in important advantages such as more efficient algorithms, higher availability and efficient utilization of resources. As systems increase in size and extent, these advantages will become increasingly more effective

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

In this paper, we address connectivity in the South American Internet. We analyze routing traces from sources inside and outside South America in order to investigate the behavior of communication both within and from outside the continent. In particular, we examine the round-trip time of IP packets and the routing paths between sources and destinations.

Pre-2018 CSE ID: CS2003-0733

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 present a protocol for general state machine replication -- a method that provides strong consistency -- that has high performance in a wide-area network. In particular, our protocol Mencius has high throughput under high client load and low latency under low client load even under changing wide-area network environment and client load. We develop our protocol as a derivation from the well-known protocol Paxos. Such a development can be changed or further refined to take advantage of specific network or application requirements.

Pre-2018 CSE ID: CS2008-0930