When you are writing a program on a single computer, it normally behaves in a fairly predictable way: either it works or it doesn’t. Buggy software may give the appearance that…
- 10.01Faults and Partial FailuresWhen you are writing a program on a single computer, it normally behaves in a fairly predictable way: either it works or it doesn’t. Buggy software may give the appearance that…
- 10.02Unreliable NetworksIn the past, older computers such as mainframes were made reliable by ensuring that individual components were redundant—for example, by employing RAID to sustain individual…
- 10.03The Limitations of TCPNetwork packets have a maximum size (generally a few kilobytes), but many applications need to send messages (requests, responses) that are too big to fit in one packet. These…
- 10.04Network Faults in PracticeWe have been building computer networks for decades—one might hope that by now we would have figured out how to make them reliable. Unfortunately, we have not yet succeeded.…
- 10.05Fault DetectionMany systems need to automatically detect faulty nodes. For example:
- 10.06Timeouts and Unbounded DelaysIf a timeout is the only sure way of detecting a fault, then how long should the timeout be? There is unfortunately no simple answer.
- 10.07Synchronous Versus Asynchronous NetworksDistributed systems would be a lot simpler if we could rely on the network to deliver packets with a fixed maximum delay and to not drop packets. Why can’t we solve this at the…
- 10.08Unreliable ClocksClocks and time are important. Applications depend on clocks in various ways, to answer questions like the following:
- 10.09Monotonic Versus Time-of-Day ClocksModern computers have at least two kinds of clocks: a time-of-day clock and a monotonic clock. Although both measure time, it is important to distinguish between them, since…
- 10.10Clock Synchronization and AccuracyMonotonic clocks don’t require synchronization, but time-of-day clocks need to be set according to an NTP server or other external time source in order to be useful.…
- 10.11Relying on Synchronized ClocksThe problem with clocks is that while they seem simple and easy to use, they have a surprising number of pitfalls. A day may not have exactly 86,400 seconds, time-of-day clocks…
- 10.12Process PausesLet’s consider another example of dangerous clock use in a distributed system. Say you have a database with a single leader per shard. Only the leader is allowed to accept…
- 10.13Knowledge, Truth, and LiesSo far in this topic we have explored the ways in which distributed systems are different from programs running on a single computer. Distributed systems have no shared memory,…
- 10.14The Majority RulesImagine a network with an asymmetric fault: a node is able to receive all messages sent to it, but any outgoing messages from that node are dropped or delayed. Even though that…
- 10.15Distributed Locks and LeasesLocks and leases in distributed applications are prone to misuse and are a common source of bugs. Let’s look at one particular case of how they can go wrong.
- 10.16Byzantine FaultsFencing tokens can detect and block a node that is inadvertently acting in error (e.g., because it hasn’t yet found out that its lease has expired). However, if the node…
- 10.17System Model and RealityMany algorithms have been designed to solve distributed systems problems—for example, we will examine solutions for the consensus problem in the related discussion. In order to…
- 10.18Formal Methods and Randomized TestingHow do we know that an algorithm satisfies the required properties? Because of concurrency, partial failures, and network delays, there are a huge number of potential states.…
- 10.19Recap: The Trouble with Distributed SystemsIn this topic we have discussed a wide range of problems that can occur in distributed systems. For example: