< Prev		CONTENTS		Source		Next >

Total Order Broadcast

If your program runs only on a single CPU core, it is easy to define a total ordering of operations: it is simply the order in which they were executed by the CPU. However, in a distributed system, getting all nodes to agree on the same total ordering of operations is tricky. In the last section we discussed ordering by timestamps or sequence numbers, but found that it is not as powerful as single-leader replication (if you use timestamp ordering to implement a uniqueness constraint, you cannot tolerate any faults).

As discussed, single-leader replication determines a total order of operations by choosing one node as the leader and sequencing all operations on a single CPU core on the leader. The challenge then is how to scale the system if the throughput is greater than a single leader can handle, and also how to handle failover if the leader fails (see “Handling Node Outages” on page 156). In the distributed systems literature, this problem is known as total order broadcast or atomic broadcast [25, 57, 58].“

Source

< Prev		CONTENTS		Source		Next >

Using total order broadcast
Consensus services such as ZooKeeper and etcd actually implement total order broadcast. This fact is a hint that there is a strong connection between total order broadcast and consensus, which we will explore later in this chapter. Total order broadcast is exactly what you need for database replication:...
(Designing Data-Intensive Applications. The Big Ideas Behind Reliable, Scalable and Maintainable Systems)
Implementing total order broadcast using linearizable storage
The last section showed how to build a linearizable compare-and-set operation from total order broadcast. We can also turn it around, assume that we have linearizable storage, and show how to build total order broadcast from it. The easiest way is to assume you have a linearizable register that stores...
(Designing Data-Intensive Applications. The Big Ideas Behind Reliable, Scalable and Maintainable Systems)
Consensus algorithms and total order broadcast
The best-known fault-tolerant consensus algorithms are Viewstamped Replication (VSR) [94, 95], Paxos [96, 97, 98, 99], Raft [22, 100, 101], and Zab [15, 21, 102]. There are quite a few similarities between these algorithms, but they are not the same [103]. In this book we won’t go into full details...
(Designing Data-Intensive Applications. The Big Ideas Behind Reliable, Scalable and Maintainable Systems)
The causal order is not a total order
A total order allows any two elements to be compared, so if you have two elements, you can always say which one is greater and which one is smaller. For example, natural numbers are totally ordered: if I give you any two numbers, say 5 and 13, you can tell me that 13 is greater than 5. However,...
(Designing Data-Intensive Applications. The Big Ideas Behind Reliable, Scalable and Maintainable Systems)
The limits of total ordering
With systems that are small enough, constructing a totally ordered event log is entirely feasible (as demonstrated by the popularity of databases with single-leader replication, which construct precisely such a log). However, as systems are scaled toward bigger and more complex workloads, limitations...
(Designing Data-Intensive Applications. The Big Ideas Behind Reliable, Scalable and Maintainable Systems)
Partial and Total Order
It is normal in many authorization systems for the user to have not only a security level, as discussed earlier, but also a secondary level of authorization involving a subset of the users at a given security level. For example, a number of users with Secret clearance may be assigned to work together...
(Behavioral Cybersecurity: Fundamental Principles and Applications of Personality Psychology)
Peacekeeping and Order Maintenance
Although patrol officers and traffic patrol officers make up the bulk of policing (Fuller, 2010), the police do a great variety of other things, all of which may fall under the heading of peacekeeping and order maintenance. For example, duties in this category include: Responding to domestic dispute...
(Crime and Intelligence Analysis: An Integrated Real-Time Approach)
Special Orders
A business may receive a special order at a price that is significantly different from the normal pricing scheme. The quantitative analysis will focus on the contribution margin associated with the special order. In other words, it must be determined whether the special order sales price exceeds the...
(Analytics for Managerial Decision Making)
Capacity Constraints and the Impact on Special Order Pricing
A potential error in special order pricing is acceptance of special orders offering the highest contribution margin per dollar of sales, while ignoring capacity constraints. Notice that the special order for Walleye Wigglers offered a 20% contribution margin ($0.20/$1.00). Suppose Bass Pro Fishing World...
(Analytics for Managerial Decision Making)