Existing Byzantine-resilient replication protocols satisfy two standard correctness criteria, safety and liveness, even in the presence of Byzantine faults. The runtime performance of these protocols is most commonly assessed in the absence of processor faults and is usually good in that case. However, faulty processors can significantly degrade the performance of some protocols, limiting their practical utility in adversarial environments. This paper demonstrates the extent of performance degradation possible in some existing protocols that do satisfy liveness and that do perform well absent Byzantine faults. We propose a new performance-oriented correctness criterion that requires a consistent level of performance, even with Byzantine faults. We present a new Byzantine fault-tolerant replication protocol that meets the new correctness criterion and evaluate its performance in fault-free executions and when under attack.

Existing Byzantine-resilient replication protocols satisfy two standard correctness criteria, safety and liveness, in the presence of Byzantine faults. In practice, however, faulty processors can, in some protocols, significantly degrade performance by causing the system to make progress at an extremely slow rate. While ldquocorrectrdquo in the traditional sense, systems vulnerable to such performance degradation are of limited practical use in adversarial environments. This paper argues that techniques for mitigating such performance attacks are needed to bridge this ldquopracticality gaprdquo for intrusion-tolerant replication systems. We propose a new performance-oriented correctness criterion, and we show how failure to meet this criterion can lead to performance degradation. We present a new Byzantine replication protocol that achieves the criterion and evaluate its performance in fault-free configurations and when under attack.

Constructing logical machines out of collections of physical machines is a well-known technique for improving the robustness and fault tolerance of distributed systems. We present a new, scalable replication architecture, built upon logical machines specifically designed to perform well in wide-area systems spanning multiple sites. The physical machines in each site implement a logical machine by running a local state machine replication protocol, and a wide-area replication protocol runs among the logical machines. Implementing logical machines via the state machine approach affords free substitution of the fault tolerance method used in each site and in the wide-area replication protocol, allowing one to balance performance and fault tolerance based on perceived risk. We present a new byzantine fault-tolerant protocol that establishes a reliable virtual communication link between logical machines. Our communication protocol is efficient (a necessity in wide-area environments), avoiding the need for redundant message sending during normal-case operation and allowing a logical machine to consume approximately the same wide-area bandwidth as a single physical machine. This dramatically improves the wide-area performance of our system compared to existing logical machine based approaches. We implemented a prototype system and compare its performance and fault tolerance to existing solutions.

We present adaptive network QoS (quality of service) technology that provides ongoing, end-to-end assurance that critical traffic belonging to admitted flows has bounded queuing loss, delay, and jitter. Our technology uses a bandwidth broker to provide admission control, and leverages differentiated services and class of service functionality of high-end routers and switches for enforcement. The technology employs an integrated QoS treatment across a hybrid layer-2/layer-3 network and adapts to changes in mission requirements, work load and configurations; it uses discovery algorithms in these layers to maintain a current view of resource availability. Under the DARPA ARMS (adaptive and reflective middleware systems) program, our technology is being developed, integrated and validated in a CORBA-based multilayer resource management framework.

We analyze nineteen months of field trouble reports for a particular highly available software application. We use this data to understand when it makes sense for the creator of a highly available software application to buy commercial software subcomponents rather than building them in-house. In particular we identify a number of potential negative impacts on system operability which can occur if too many or inappropriately chosen commercial software components are used. Our data indicates that the prudent application builder must carefully weigh these potential negative operability impacts against the well known potential cost savings that can accrue from using commercial software components.

Two self-stabilizing topology maintenance protocols for high-speed networks are presented. The protocols tolerate any number and kind of initial faults. The new protocols improve on previous protocols by their stabilization time (the amount of time following the last topology change required to notify every processor of the correct topology), by their utilization of limited switch bandwidth, and by their avoiding the use of unbounded sequence numbers. The first protocol stabilizes in O(log d) time in the worst case, where d is the diameter of the network. This protocol imposes a high bandwidth requirement on individual network nodes. The second, which is implemented by two software layers, reduces the processing load on individual nodes and stabilizes within O(d) time in the worst case and O(1) time when changes are infrequent.

Existing congestion control and network management techniques have been designed to cope with problems such as unexpectedly high offered load and hardware failures. On rare occasions, networks have failed despite the deployment of such techniques. The authors survey the current research in congestion control and network management techniques and their role in ensuring network stability in the presence of software errors. What situations are these techniques intended to address? What are the characteristics of the problems that have led to network collapse? What areas of research offer the best prospect for further improving network reliability?.>

A method is devised for maintaining the continuing availability of a vital service in a real-time shared-memory multiprocessor fault-tolerant computer system. The essential characteristics of the service to be provided are given. The service can be correctly provided by any one operational processor acting alone. The job of selecting the processor to provide the service is the real-time leader election problem. Two protocols are given which solve this problem in shared-memory systems. Each tolerates the failure of any subset of the processors. The first protocol is extremely simple and has running time linear in the number of processors. The second is slightly more complicated and has running time logarithmic in the number of processors. Both protocols use space that is linear in the number of processors.>

Article Modular construction of nearly optimal Byzantine agreement protocols Share on Authors: B. A. Coan Bell Communications Research Bell Communications ResearchView Profile , J. L. Welch GTE Laboratories Incorporated GTE Laboratories IncorporatedView Profile Authors Info & Claims PODC '89: Proceedings of the eighth annual ACM Symposium on Principles of distributed computingJune 1989 Pages 295–305https://doi.org/10.1145/72981.73002Published:01 June 1989 7citation261DownloadsMetricsTotal Citations7Total Downloads261Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The distributed firing squad problem is defined in the context of a synchronous distributed system where the correct processors operate in lock-step synchrony but do not share a global clock. If one or more correct processors receive a command to start a firing squad synchronization, then at some future time all correct processors must “fire” (formally, enter a special state) at exactly the same step. For various fault models, upper and lower bounds are proved on the number of faulty processors that can be tolerated and on the number of rounds of communication required between the reception of the start command and firing. For example, if a firing squad protocol is resilient to t fail-stop faults, then at least $t + 1$ rounds are necessary and sufficient. For the case of Byzantine faults with authentication where the faulty processors can take steps in between the synchronous steps of the correct processors, the firing squad problem can be solved in $t + 5$ rounds, provided that $n > 3t$, where n is the number of processors and t is the number of faults, and the problem cannot be solved at all if $n \leqq 3t$. Moreover, in the case that $n \leqq 3t$, the impossibility of a firing squad protocol holds even for a weaker “timing fault model” where all processors generate messages correctly according to the protocol, but the faulty processors can affect the system by slightly slowing down or speeding up messages.

A compiler that increases the fault tolerance of certain asynchronous protocols is presented. Specifically, it transforms a source protocol that is resilient to crash faults into an object protocol that is resilient to Byzantine faults. The compiler simplifies the design of protocols for the Byzantine fault model because it allows the design process to be broken in two steps. The first step is to design a protocol for the crash fault model. The second step, which is completely mechanical, is to compile the protocol into one for the Byzantine fault model. The compiler is used to produce an asynchronous approximate agreement protocol that operates in the Byzantine fault model and improves in several respects on the performance of the asynchronous approximate agreement protocol of D. Dolev et al. (1986).>

Many fault-tolerant distributed protocols are known.Some of these require a large (exponential) amount of communication.We present a general simulation of any synchronous fault-tolerant consensus protocol by a communication-efficient protocol.An important corollary of the simulation technique is a new communicationefficient Byzantine agreement protocol that uses about half the number of rounds required by the best previouslyknown communication-efficient Byzantine agreement protocol.Our new protocol approaches the known lower bound for rounds to within a small factor arbitrarily close to 1.The only known protocols which achieve the lower bound for rounds use an exponential amount of communication.

Article Free Access Share on Transaction commit in a realistic fault model Authors: Brian Coan Massachusetts Institute of Technology Massachusetts Institute of TechnologyView Profile , Jennifer Lundelius Massachusetts Institute of Technology Massachusetts Institute of TechnologyView Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 40–51https://doi.org/10.1145/10590.10594Published:01 November 1986Publication History 6citation207DownloadsMetricsTotal Citations6Total Downloads207Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract : In designing fault-tolerant distributed database, a frequent goal is making the system highly available despite component failure. We examine software approaches to achieving high availability in the presence of partitions. In particular, we consider various replicated-data management protocols that maintain database consistency and attempt to increase database availability when networks partition. We conclude that no protocol does better than a bound we have determined. Our conclusions hold under the assumption. There may be some particular distribution for which specialized protocols can increase availability. (KR)

this paper we justify the design assumption of simultaneous starts. Specifically, we provide algorithms to solve the associated synchronization problem, which we call the distributed firing squad problem (abbreviated DFS). A distributed algorithm for the DFS problem has two properties: (I) if any correct processor receives a .message to start a DFS synchronization, then at some future time all cor- rect processors will "fire" (formally, enter a special state), and (2) the correct processors all fire at exactly the same step

A new randomized Byzantine agreement algorithm is presented. This algorithm operates in a synchronous system of n processors, at most t of which can fail. The algorithm reaches agreement in 0(t/log n) expected rounds and O(n2tf/log n) expected message bits independent of the distribution of processor failures. This performance is further improved to a constant expected number of rounds and O(n2) message bits if the distribution of processor failures is assumed to be uniform. In either event, the algorithm improves on the known lower bound on rounds for deterministic algorithms. Some other advantages of the algorithm are that it requires no cryptographic techniques, that the amount of local computation is small, and that the expected number of random bits used per processor is only one. It is argued that in many practical applications of Byzantine agreement, the randomized algorithm of this paper achieves superior performance.