Method, apparatus and computer program product for fault recovery in a distributed stateful publish-subscribe system. The system includes the capability of recovering from failures that may occur when a stateful publish-subscribe service is implemented on an overlay network. Such failures may include, for example, temporary crashes of broker machines, and network errors causing messages to possibly be lost, duplicated or delivered out of order. The system requires stable storage logging only when a published event enters the system, and requires that logged messages be retrieved from stable storage only in the event all brokers between a failed link or broker and the publishing sites have failed. The publish-subscribe system of the present invention does not require that broker-to-broker connections use reliable FIFO protocols, such as TCP/IP, but may advantageously use faster, less reliable protocols.