Wireless sensor networks for environmental monitoring and distributed control will be deployed on a large scale in the near future. Due to the low per-node cost, these networks are expected to be both large and dense. However, because of the limited computation, storage, and power available to each node, conventional ad-hoc routing techniques are not feasible in this domain, and more novel routing algorithms are required. Despite the need for a simpler approach, routing in sensor networks still needs to be both robust to failures and secure against compromised and malicious nodes. We propose ARRIVE, a probabilistic algorithm that leverages the high node density and the inherent broadcast medium found in sensor networks to achieve routing robust to both link failures and patterned node failures without resorting to periodic flooding of the network. Our algorithm is based on a tree-like topology rooted at the sink of the network, and nodes use localized observed behavior of the surrounding nodes to make probabilistic decisions for forwarding packets. We have found that ARRIVE adapts to large patterned failures within a relatively short period of time at the cost of only moderate increases in overall power consumption and source-to-sink latency.