Amazon has had a few problems of late, one of the more interesting ones being something S3 users encountered. It took Amazon a little while to identify the root cause:

We’ve isolated this issue to a single load balancer that was brought into service at 10:55pm PDT on Friday, 6/20. It was taken out of service at 11am PDT Sunday, 6/22. While it was in service it handled a small fraction of Amazon S3’s total requests in the US. Intermittently, under load, it was corrupting single bytes in the byte stream.

Perhaps they had anticipated this scenario as the S3 API features explicit support for software-level check-summing via MD5:

For all PUT requests, Amazon S3 computes its own MD5, stores it with the object, and then returns the computed MD5 as part of the PUT response code in the ETag. By validating the ETag returned in the response, customers can verify that Amazon S3 received the correct bytes even if the Content MD5 header wasn’t specified in the PUT request. Because network transmission errors can occur at any point between the customer and Amazon S3, we recommend that all customers use the Content-MD5 header and/or validate the ETag returned on a PUT request to ensure that the object was correctly transmitted. This is a best practice that we’ll emphasize more heavily in our documentation to help customers build applications that can handle this situation.

Some developers were surprised that any of this was necessary, expecting TCP/UDP checksums to be sufficient however Stevens points out in TCP/IP Illustrated Vol I:

Takeaways:

1. Not all types of failure are binary - working or not working.
2. Leaving the responsibility of data-safety to software layers further down the stack may not be best.
3. Mechanisms for failure handling must be embedded in APIs.

There are many distributed algorithms and they vary in lots of ways including:

Communication Method: Possibilities include shared memory, point-to-point or broadcast messages etc.

Failure Model: Perhaps the algorithm assumes complete reliability. Perhaps it copes with some types of processor failure (including stop, transient failure or byzantine where the processor behaves arbitrarily). It might cope with problems in it’s communications layers (including message loss and duplication).

Timing Model: The algorithm might require computation and communication to progress in lock-step (synchronous) or it might cope with steps in arbitrary order with arbitrary speed (asynchronous). In between these two extremes exists an area of algorithms that have partial timing information (e.g. processors can access partially synchronised clocks). Asynchronous/Synchronous is independently applied to processors and communication channels.

The easiest to program are the synchronous algorithms. Asynchronous algorithms are harder to program because the order of happenings is uncertain however they have the advantage of needing no consideration of timing. Asynchronous algorithms also present some unique challenges for consensus which can be addressed by means of a failure detector. Many distributed systems provide stronger guarantees in respect of timing than is assumed in the asynchronous model thus we get to the partially synchronous model which perhaps surprisingly is the most difficult to program. Algorithms in this class are potentially efficient and the most realistic but care must be taken to ensure the timing assumptions they make are not violated (perhaps by failing to arrange for some aspect of process behaviour to act within the assumptions).

Such a classification helps us choose algorithms appropriate to our network environment (which should include consideration of how often manual intervention will be required), A popular leader election algorithm simply requires each process to broadcast its UID across the network and maintenance of a lease. If a process doesn’t receive a UID higher than its own it can assume it is the leader. This algorithm works in a synchronous network with no failures. It can also be adapted to work in an asynchronous network with reliable FIFO channels and no failures. However it can fail in the presence of a network partition or packet loss leading to split brain behaviour which would need to be addressed with manual action or additional fault handling in other parts of the system.