1. A distributed system, comprising: a plurality of computing devices configured to implement: a plurality of application instances configured to perform functions of the distributed system, wherein the plurality of application instances includes two or more different types of application instances, each type of application instance configured to perform one or more different functions of the distributed system; and a plurality of discovery and failure detection daemon (DFDD) instances, wherein the plurality of DFDD instances are configured to store operational state information for the plurality of application instances, wherein the state information includes global state information common to all types of application instances and specific state information specific to at least one type of application instance and wherein at least one of the DFDD instances is configured to update the global state information according to a global state machine defining transitions between a plurality of global states including a state indicating the respective application instance is newly online, a state indicating the respective application instance is operating normally, a state indicating the respective application instance has lost communication with a respective DFDD instance, a state indicating the respective application instance has failed, and a state indicating the respective application instance is subject to a network split, according to one or more status reports received from the respective application instance; wherein at least one of the plurality of DFDD instances is configured to repeatedly execute a peer-to-peer, gossip-based synchronization protocol with a peer instance of the DFDD instances, wherein the peer instance is randomly or pseudorandomly selected from among the plurality of DFDD instances, and wherein to execute the protocol, the peer DFDD instances are configured to exchange state information for at least one of the plurality of application instances including both the global state information and the specific state information.