A method of providing reliable failure notification in a distributed system operating on a plurality of nodes in an overlay network, the method comprising: creating, by a creator node, a failure notification group comprising the plurality of nodes, wherein the plurality of nodes in the failure notification group are a subset of nodes in the overlay network, wherein creating a failure notification group includes creating a multicast tree by sending a construction message to each node in the failure notification group, and receiving a confirmation message, wherein the construction message is routed to each node in the failure notification group through an overlay routing path, and upon receiving the construction message, each given node in the overlay routing path records a pointer to the node preceding the given node in the overlay routing path, and wherein the confirmation message is routed through the overlay routing path in reverse, and upon receiving the confirmation message, each specific node in the reverse overlay routing path records a pointer to the node preceding the specific node in the reverse overlay routing path, wherein the failure notification group has a unique identifier, and wherein a distributed application is running on some or all of the nodes of the failure notification group; associating a failure handling method of the distributed application with the unique identifier of the failure notification group at each node at which the distributed application is running; and ascertaining a failure on at least one node of the failure notification group, including: ascertaining that a communication link to a node in the overlay network has failed; determining whether the node was a member of the multicast tree; if the node was a member of the multicast tree, signaling a failure notification to adjacent nodes in the multicast tree, wherein the signaling includes failing to respond to a communication request from the adjacent nodes in the multicast tree; and executing the failure handling method at each node at which the distributed application is running. creating, by a creator node, a failure notification group comprising the plurality of nodes, wherein the plurality of nodes in the failure notification group are a subset of nodes in the overlay network, wherein creating a failure notification group includes creating a multicast tree by sending a construction message to each node in the failure notification group, and receiving a confirmation message, wherein the construction message is routed to each node in the failure notification group through an overlay routing path, and upon receiving the construction message, each given node in the overlay routing path records a pointer to the node preceding the given node in the overlay routing path, and wherein the confirmation message is routed through the overlay routing path in reverse, and upon receiving the confirmation message, each specific node in the reverse overlay routing path records a pointer to the node preceding the specific node in the reverse overlay routing path, wherein the failure notification group has a unique identifier, and wherein a distributed application is running on some or all of the nodes of the failure notification group; associating a failure handling method of the distributed application with the unique identifier of the failure notification group at each node at which the distributed application is running; and ascertaining a failure on at least one node of the failure notification group, including: ascertaining that a communication link to a node in the overlay network has failed; determining whether the node was a member of the multicast tree; if the node was a member of the multicast tree, signaling a failure notification to adjacent nodes in the multicast tree, wherein the signaling includes failing to respond to a communication request from the adjacent nodes in the multicast tree; and executing the failure handling method at each node at which the distributed application is running. ascertaining that a communication link to a node in the overlay network has failed; determining whether the node was a member of the multicast tree; if the node was a member of the multicast tree, signaling a failure notification to adjacent nodes in the multicast tree, wherein the signaling includes failing to respond to a communication request from the adjacent nodes in the multicast tree; and executing the failure handling method at each node at which the distributed application is running.