## 1 Introduction  
Wireless sensor and actor networks (WSANs) are envisaged to be a promising technology for mission-critical applications that require autonomous and intelligent interaction with the environment. Examples of such applications include fire detection and containment, disaster management, urban search and rescue (USAR), homeland security, battlefield surveillance, space exploration and nuclear, biological and chemical attack detection and prevention. These applications are also regarded as safety-critical applications because an inappropriate action may have catastrophic consequences such as loss of human life, severe injuries, large-scale environmental damage and considerable economical penalties. In these critical applications, WSANs employ a number of sensor nodes that report events of interest to one or multiple actors [1]. The concerned actors receive event notifications, process them and share with peer actors to effectively respond to events such as fires, earthquakes and disasters. Figure 1 illustrates an example of an autonomous WSAN environment. The inherent characteristics of a WSAN require actors to collaborate and coordinate with each other in planning an optimal response and synchronize their operations. For example, in USAR, sensors and actors are deployed in an area damaged by an event such as a fire, earthquake or other disaster. The sensors detect the presence of survivors in the vicinity and report it to the actors. The actors equipped with necessary life support equipment receive the sensors data, process it and share it with peer actors to identify the most appropriate set of actors. These actors are responsible for rescuing survivors immediately or provide them with life saving necessities such as water, oxygen or even some sort of medicine for a short period until the rescue team arrives. The role of actors is extremely crucial for a timely response to this type of events in order to prevent serious consequences. This requires actors to  
Figure 1: An example of autonomous wireless sensor and actor network setup. interact with each other and determine the most appropriate set of actors that will participate in the operation. To enable such interaction, actors must establish and maintain the inter-actor topology that serves as a backbone of the network. The requirement for a fully autonomous WSAN has been realized due to several incidents that cost unbearable lost of lives in situations too difficult or dangerous for humans to operate. For example, during the 9/11 rescue operations, four hundred and seventy-nine rescue workers lost their lives in making the evacuation a success. Similarly, actors operating in hazardous and inhospitable environments are subject to failures. Failure of a critical actor partitions the inter-actor network into disjoint segments besides leaving uncovered regions. This may stop inter-actor interactions altogether and the network becomes incapable of delivering a timely response to serious events. The autonomous, unattended and resource restricted nature of WSAN necessitates self-healing and agile recovery processes that involve reconfiguring the inter-actor topology with minimal overhead. Moreover, criticality of the applications, distributed, dynamic and complex operation of the network demand for rigorous and reliable validation of recovery schemes. Most of the published connectivity restoration schemes are purely reactive [2; 3; 4; 5], triggering the recovery process once the failure of a node is detected. Reactive schemes may not be suitable for mission-critical time-sensitive applications due to procrastination. Moreover, existing recovery schemes lack rigorous validation and entirely rely on non-formal validation _i.e._, simulation. Simulation-based results are useful only for statistical performance analysis and do not guarantee the correctness of the approach that is crucial in safety-critical applications.