A method (100; 1200) of resolving a failure in a distributed database (200; 300; 400; 500; 700; 800; 900), the distributed database including a plurality of nodes (TE1, TE2, TE3, SM1, SM2), each node in the plurality of nodes directly connected to each other node in the plurality of nodes, the method comprising, in response to detecting the failure: at a first node in the plurality of nodes: identifying (102; 1202, 1210) a suspicious node in the plurality of nodes, the suspicious node being a node in the plurality of nodes that is no longer connected to the first node as a result of the failure; broadcasting (104; 1230) a first list of suspicious nodes to neighbor nodes in the plurality of nodes, the first list of suspicious nodes including the suspicious node, the neighbor nodes being nodes in the plurality of nodes that remain directly connected to the first node after the failure; receiving a second list of suspicious nodes from at least one of the neighbor nodes; determining (106; 1240) connectivity information for the plurality of nodes based at least in part on the first list of suspicious nodes and the second list of suspicious nodes; determining (110; 1260) whether the first node is in a winning fully connected component (204'; 304' 404'; 704'; 904') of the distributed database based on the connectivity information, wherein the winning fully connected component includes more than half of the nodes in the plurality of nodes and each node in the winning fully connected component node is directly connected to each other node in the winning fully connected component node; in response to determining that the first node is in the winning fully connected component of the plurality of nodes, continuing to operate (114; 1201) the first node; and in response to determining that the first node is not in the winning fully connected component of the plurality of nodes, failing (112; 1299) the first node to resolve the failure. identifying (102; 1202, 1210) a suspicious node in the plurality of nodes, the suspicious node being a node in the plurality of nodes that is no longer connected to the first node as a result of the failure; broadcasting (104; 1230) a first list of suspicious nodes to neighbor nodes in the plurality of nodes, the first list of suspicious nodes including the suspicious node, the neighbor nodes being nodes in the plurality of nodes that remain directly connected to the first node after the failure; receiving a second list of suspicious nodes from at least one of the neighbor nodes; determining (106; 1240) connectivity information for the plurality of nodes based at least in part on the first list of suspicious nodes and the second list of suspicious nodes; determining (110; 1260) whether the first node is in a winning fully connected component (204'; 304' 404'; 704'; 904') of the distributed database based on the connectivity information, wherein the winning fully connected component includes more than half of the nodes in the plurality of nodes and each node in the winning fully connected component node is directly connected to each other node in the winning fully connected component node; in response to determining that the first node is in the winning fully connected component of the plurality of nodes, continuing to operate (114; 1201) the first node; and in response to determining that the first node is not in the winning fully connected component of the plurality of nodes, failing (112; 1299) the first node to resolve the failure.