Amazon.com, Inc.
Mechanism to protect a distributed replicated state machine

Abstract:

A database server (e.g., a replica) generates a local checksum from a sequence of database operations and contributes the sequence of operations and the local checksum to a shared log of a distributed database. Additional database servers, similarly, generate local checksums. A checksum replica agent determines a first ordering of database operations of a first database server of a database, determines a second ordering of database operations of a second database server of the database; determines whether a third ordering of database operations that is based at least in part on the first ordering and the second ordering is valid. In an embodiment, a checksum replica agent generates a global checksum over the third ordering. Checksums, in an embodiment, are digitally signed and/or encrypted.