  We present two abstractions for designing modular state machine replication
(SMR) protocols: trees and turtles. A tree captures the set of possible state
machine histories, while a turtle represents a subprotocol that tries to find
agreement in this tree. We showcase the applicability of these abstractions by
constructing crash-tolerant SMR protocols out of abstract tree turtles and
providing examples of tree turtle implementations. Tree turtles can also be
extended to be made Byzantine fault-tolerant (BFT). The modularity of tree
turtles allows a generic approach for adding a leader for liveness. We expect
that these abstractions will simplify reasoning and formal verification of SMR
protocols as well as facilitate innovation in protocol designs.
