In wireless sensor and actor networks maintaining inter-actor connectivity is very important in mission-critical applications where actors have to quickly plan optimal coordinated response to detected events. Failure of one or multiple actors may partition the inter-actor network into disjoint segments, and thus hinders the network operation. Autonomous detection and rapid recovery procedures are highly desirable in such a case. This paper presents DCR, a novel distributed partitioning detection and connectivity restoration algorithm to tolerate the failure of actors. DCR proactively identifies actors that are critical to the network connectivity based on local topological information, and designates appropriate, preferably non-critical, backup nodes. Upon failure detection, the backup actor initiates a recovery process that may involve coordinated relocation of multiple actors. We also present an extended version of DCR, named RAM, to handle one possible case of a multi-actor failure. The proposed algorithms strive to avoid procrastination, localize the scope of recovery and minimize the movement overhead. Simulation results validate the performance of the proposed algorithms. © 2011 Elsevier Ltd. All rights reserved.