Automated design of self-stabilization

Self-stabilization is a property of a distributed system such that, regardless of the legitimacy of its current state, the system behavior shall eventually reach a legitimate state and shall remain legitimate thereafter. The elegance of self-stabilization stems from the fact that it distinguishes distributed systems by a strong fault tolerance property against arbitrary state perturbations. The difficulty of designing and reasoning about self-stabilization has been witnessed by many researchers; most of the existing techniques for the verification and design of self-stabilization are either brute-force, or adopt manual approaches non-amenable to automation. In this dissertation, we first investigate the possibility of automatically designing self-stabilization through global state space exploration. In particular, we develop a set of heuristics for automating the addition of recovery actions to distributed protocols on various network topologies. Our heuristics equally exploit the computational power of a single workstation and the available parallelism on computer clusters. We obtain existing and new stabilizing solutions for classical protocols like maximal matching, ring coloring, mutual exclusion, leader election and agreement. Second, we consider a foundation for local reasoning about self-stabilization; i.e., study the global behavior of the distributed system by exploring the state space of just one of its components. It turns out that local reasoning about deadlocks and livelocks is possible for an interesting class of protocols whose proof of stabilization is otherwise complex. In particular, we provide necessary and sufficient conditions – verifiable in the local state space of every process – for global deadlock- and livelock-freedom of protocols on ring topologies. Local reasoning potentially circumvents two fundamental problems that complicate the automated design and verification of distributed protocols: (1) state explosion and (2) partial state information. Moreover, local proofs of convergence are independent of the number of processes in the network, thereby enabling our assertions about deadlocks and livelocks to apply on rings of arbitrary sizes without worrying about state explosion.

ANKLE IMPEDANCE AND ANKLE ANGLES DURING STEP TURN AND STRAIGHT WALK: IMPLICATIONS FOR THE DESIGN OF A STEERABLE ANKLE-FOOT PROSTHETIC ROBOT

During locomotion, turning is a common and recurring event which is largely neglected in the current state-of-the-art ankle-foot prostheses, forcing amputees to use different steering mechanisms for turning, compared to non-amputees. A better understanding of the complexities surrounding lower limb prostheses will lead to increased health and well-being of amputees. The aim of this research is to develop a steerable ankle-foot prosthesis that mimics the human ankle mechanical properties. Experiments were developed to estimate the mechanical impedance of the ankle and the ankles angles during straight walk and step turn. Next, this information was used in the design of a prototype, powered steerable ankle-foot prosthesis with two controllable degrees of freedom. One of the possible approaches in design of the prosthetic robots is to use the human joints’ parameters, especially their impedance. A series of experiments were conducted to estimate the stochastic mechanical impedance of the human ankle when muscles were fully relaxed and co-contracting antagonistically. A rehabilitation robot for the ankle, Anklebot, was employed to provide torque perturbations to the ankle. The experiments were performed in two different configurations, one with relaxed muscles, and one with 10% of maximum voluntary contraction (MVC). Surface electromyography (sEMG) was used to monitor muscle activation levels and these sEMG signals were displayed to subjects who attempted to maintain them constant. Time histories of ankle torques and angles in the lateral/medial (LM) directions, inversion-eversion (IE), and dorsiflexionplantarflexion (DP) were recorded. Linear time-invariant transfer functions between the measured torques and angles were estimated providing an estimate of ankle mechanical impedance. High coherence was observed over a frequency range up to 30 Hz. The main effect of muscle activation was to increase the magnitude of ankle mechanical impedance in all degrees of freedom of the ankle. Another experiment compared the three-dimensional angles of the ankle during step turn and straight walking. These angles were measured to be used for developing the control strategy of the ankle-foot prosthesis. An infrared camera system was used to track the trajectories and angles of the foot and leg. The combined phases of heel strike and loading response, mid stance, and terminal stance and pre-swing were determined and used to measure the average angles at each combined phase. The Range of motion (ROM) in IE increased during turning while ML rotation decreased and DP changed the least. During the turning step, ankle displacement in DP started with similar angles to straight walk and progressively showed less plantarflexion. In IE, the ankle showed increased inversion leaning the body toward the inside of the turn. ML rotation initiated with an increased medial rotation during the step turn relative to the straight walk transitioning to increased lateral rotation at the toe off. A prototype ankle-foot prosthesis capable of controlling both DP and IE using a cable driven mechanism was developed and assessed as part of a feasibility study. The design is capable of reproducing the angles required for straight walk and step turn; generates 712N of lifting force in plantarflexion, and shows passive stiffness comparable to a nonload bearing ankle impedance. To evaluate the performance of the ankle-foot prosthesis, a circular treadmill was developed to mimic human gait during steering. Preliminary results show that the device can appropriately simulate human gait with loading and unloading the ankle joint during the gait in circular paths.