Method and system for providing message communications with failure detection and recovery are disclosed. At a respective node of a non-static collection of nodes forming a linear communication orbit: the node identifies, from among the non-static collection of nodes, a set of forward contacts distributed in a forward direction along the linear communication orbit; the node monitors a propagation state of a first query that has departed from the respective node to travel in the forward direction along the linear communication orbit; and upon detecting a propagation failure of the first query based on the monitoring, the node sends the first query directly to a first forward contact among the set of forward contacts to initiate a failure recovery process within at least part of a segment of the linear communication orbit between the respective node and the first forward contact of the respective node.