Thesis supervisor: Sukumar Ghosh. Includes bibliographic references (p. 136-140).

Today's distributed systems exist on a scale that was unimaginable only a few decades ago. Distributed systems now can consist of thousands or even millions of computers spread across the entire world. These large systems are often organized into overlay networks - networks composed of virtual links, with each virtual link realized by one or more physical links. Self-stabilizing overlay networks promise that, starting from any weakly-connected configuration, the correct network topology is always built. This area of research is young, and prior examples of self-stabilizing overlay networks have either been for simple topologies, or involved complex algorithms that were difficult to verify and extend. We address these limitations in this thesis. First, we present the Transitive Closure Framework, a generic framework to transform any locally-checkable overlay network into a self-stabilizing network. This simple framework has a running time which is at most a logarithmic number of rounds more than optimal, and in fact is optimal for a particular class of overlay networks. We also prove the only known non-trivial lower bound on the convergence time of any self-stabilizing overlay network. To allow fast and efficient repairs for local faults, we extend the Transitive Closure Framework to the Local Repair Framework. We demonstrate this framework by implementing an efficient algorithm for node joins in the Skip+ graph. Next, we present the Avatar network, which is a generic locally checkable overlay network capable of simulating many other overlay networks. We design a self-stabilizing algorithm for a binary search tree embedded onto the Avatar network, and prove this algorithm requires only a polylogarithmic number of rounds to converge and limits degree increases to within a polylogarithmic factor of optimal. This algorithm is the first to achieve such efficiency, and its modular design makes it easy to extend. Finally, we introduce a technique called network scaffolding, which builds other overlay network topologies using the Avatar network.

Ubiquitous computing has become a widespread phenomenon in today's modern world, with the computing technology integrating with our daily life in an invisible manner. Embedded systems and wireless sensor networks are popular choices to achieve this. Programming embedded and sensor network systems has always been a challenge for the programmers due to the lack of sufficient high-level programming support. To deal with this serious limitation, we have developed DESAL (Dynamic Embedded Sensing and Actuation Language) which is a user-friendly high-level programming language for wireless sensor networks with an integrated middleware, which hides the low-level detail from the programmers. In this thesis we present the design and development of DESAL. We have made DESAL programs rule based. Programs are written in guard-action format defined in terms of the program states. There are established formal correctness proving methods that can work on guard-action formats to mathematically check a program for errors. Also, there is no hidden control context like events or interrupts. Time synchronization has been developed as part of the middleware that lets DESAL programs to coordinate through synchronized actions throughout the network. This facilitates classic coordination algorithms like clock synchronization, spanning tree construction and consensus. Also, synchronized wake up saves energy. Neighborhood management, including node discovery and monitoring, is also provided by the middleware. DESAL programs communicate via state sharing. There is no network programming required. The middleware provides that automatically. Combining all these features DESAL provides major network management services, and yet presents the users with a simple high-level programming interface. We implemented the DESAL compiler to convert DESAL programs to NesC on TinyOS and to Java. Another novel feature we have introduced in DESAL is a variable of type 'token'. The concept of token is commonly used in mutual exclusion algorithms. One of the case studies we have done uses the token variable to achieve increased lifetime of sensors in a ring topology. The working of token is hidden from the user. The token mechanism developed achieves self-stabilization in the system. Another case study with tokens involves selective activation of RFID tags in a scenario where among the three RFID tags present only one can work at a time. Struct is a new data structure introduced in DESAL. Sometimes we need to group together two or more variables. It is important to receive them at the same time. Hence, it is important to send these grouped data over the radio together. Struct does that. Function is another newly added feature to DESAL. Function is added to group together repeated statements in a program. The unique feature of function is that, it uses only global variables. No new local variable is declared. This can significantly reduce the stack overhead of the program, thus saving memory and running time. Case studies have been done to illustrate the features of DESAL and to find scope for improvement.

There are many variants of leader election algorithm in distributed networks. In this research, an agent based approach to leader election in distributed networks is investigated. Agents have shown to be useful in several ways. In the theoretical perspective, agents sometime help in reducing the message complexity of the system and sometimes help in lowering time complexity. In a more practical sense, agents perform operations independent of the processors, thereby lending a more flexible algorithm supporting different types of networks.

Terrestrial robots must be capable of negotiating rough terrain if they are to become autonomous outside of the lab. Although the control mechanism offered by wheels is attractive in its simplicity, any wheeled system is confined to relatively flat terrain. Wheels will also only ever be useful for rolling, while limbs observed in nature are highly multimodal. The robust locomotive utility of legs is evidenced by the many animals that walk, run, jump, swim, and climb in a world full of challenging terrain. On the other hand, legs with multiple degrees of freedom (DoF) require much more complex control and precise sensing than wheels. Legged robotic systems are easily hampered by sensor noise and bulky control loops that prohibit the high-speed adaptation to external perturbations necessary for dynamic stability in real time. Low sensor bandwidth can limit the system’s reaction time to external perturbations. It is also often necessary to filter sensor data, which introduces significant delays in the control loop. In addition, state estimation is often relied upon in order to compute active stabilizing responses. State estimation requires accurate sensor data, often involving filtering, and can involve additional nontrivial computation such as the pseudo-inversion of fullbody Jacobians. This perception portion of the control burden is all incurred before a response can be planned and executed. These delays can prevent a system from executing a corrective response before instability leads to failure. The present work presents an approach to legged system design and control that reduces both the perception and planning aspects of the online control burden. A commonly accepted design goal in robotics is to accomplish a task with the fewest possible DoF in order to tighten the control loop and avoid the curse of dimensionality. However, animals control many DoF in a manner that adapts to external perturbations faster than can be explained by efferent neural control. The passive mechanics of segmented animal limbs are capable of rejecting unexpected disturbances without the supervision of an active controller. By simulating biomimetic limbs, we can learn more about this preflexive response, how the properties of segmented biological limbs foster self-stable passive mechanics, and how the control burden can be mitigated in robotic legged systems. The contribution of this body of work is to reduce the control burden of legged locomotion for robots by drawing on self-stabilizing mechanical design and control principles observed in animal locomotion. To that end, minimal templates such as Sensory-Coupled Action Switching Modules (SCASM), Central Pattern Generators (CPGs), and the Spring-Loaded Inverted Pendulum (SLIP) model are used to learn more about the essential components of legged locomotion. The motivation behind this work lies largely in the study of how internal, predictive models and the intrinsic mechanical properties of biological limbs help animals self-stabilize in real time. Robotic systems have already begun to demonstrate the benefits of these biological design primitives in an engineering context, such as reduced cost of transportation and an immediate mechanical response that does not need to wait for sensor feedback or planning. The original research presented here explores the extent to which these principles can be utilized in order to encourage stable legged locomotion over uneven terrain with as little sensory information as possible. A method for generating feedforward, terrain-adaptive control primitives based on a compliant limb architecture is developed. Offline analysis of system dynamics is used to develop clock-driven patterns of leg stiffness and attack angle control during late swing with which passive stance phase dynamics will produce the desired apex height and stride period to within 0.1 mm and 50 μs, respectively. A feedforward method of energy modulation is incorporated that regulates velocity to within 10−5 m/s. Preservation of a constant stride period eliminates the need for detection of the apex event. Precise predictive controls based on thorough offline dynamic modeling reduce the system’s reliance on state and environmental data, even in rough terrain. These offline models of system dynamics are used to generate a controller that predicts the dynamics of running over uneven terrain using an internal clock signal. Real-time state estimation is a non-trivial bottleneck in the control of mobile systems, legged and wheeled alike. The present work significantly reduces this burden by generating predictive models that eliminate the need for state estimation within the control loop, even in the presence of damping. The resulting system achieves not only self-stable legged running, but direct control of height, speed, and stride period without inertial sensing or force feedback. Through this work, the controller dependency on accurate and rapid sensing of the body height and velocity, apex event, and ground variation was eliminated. This was done by harnessing physics-based models of leg dynamics, used to generate predictive controls that exploit the passive mechanics of the compliant limb to their full potential. While no real world system is entirely deterministic, such a predictive model may serve as the base layer for a lightweight control architecture capable of stable robotic limb control, as in animal locomotion.

A sensor is a battery-operated small computer with an antenna and a sensing board that can sense magnetism, sound, heat, etc. Sensors in a network communicate and cooperate with other sensors to perform given tasks. A sensor network is exposed to various dynamic factors and faults, such as topology changes, energy saving features, unreliable communication, and hardware/software failures. Thus, protocols in this sensor network should be able to adapt to dynamic factors and recover from faults. In this dissertation, we focus on designing and analyzing a class of sensor network protocols, called self-stabilizing protocols. A self-stabilizing protocol is guaranteed to return to a state where it performs its intended function correctly, when some dynamic factors or faults corrupt the state of the protocol arbitrarily. Therefore, in order to make a sensor network resilient to dynamic factors and faults, each protocol in the sensor network should be self-stabilizing. We first develop a state-based model that can be used to formally specify sensor network protocols. This model accommodates several unique characteristics of sensor networks, such as unavoidable local broadcast, probabilistic message transmission, asymmetric communication, message collision, and timeout actions and randomization steps. Second, we present analysis methods for verifying and analyzing the correctness and self-stabilization properties of sensor network protocols specified in this model. Third, using the state-based model and analysis methods, we design three self-stabilizing sensor network protocols, prove their self-stabilization properties, and estimate their performance. These three self-stabilizing protocols are a sentry-sleeper protocol that elects a sentry from a group of sensors at the beginning of each time period, a logical grid routing protocol that builds a routing tree whose root is the base station, and a family of flood sequencing protocols that distinguish between fresh and redundant flood messages using sequence numbers. / text

There are many variants of leader election algorithm in distributed networks. In this research, an agent based approach to leader election in distributed networks is investigated. Agents have shown to be useful in several ways. In the theoretical perspective, agents sometime help in reducing the message complexity of the system and sometimes help in lowering time complexity. In a more practical sense, agents perform operations independent of the processors, thereby lending a more flexible algorithm supporting different types of networks.

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

No description available.

Self-stabilizing system is a concept of fault-tolerance in distributed computing. A distributed algorithm is self-stabilizing if, starting from an arbitrary state, it is guaranteed to converge to a legal state in a finite number of states and remains in a legal set of states thereafter. The property of self-stabilization enables a distributed algorithm to recover from a transient fault regardless of its objective. Moreover, a self-stabilizing algorithm does not have to be initialized as it eventually starts to behave correctly. In this thesis, we focus on extensions and refinements of self-stabilization by studying two non-traditional aspects of self-stabilization. In traditional self-stabilizing distributed systems [13], the inherent assumption is that all processes run predefined programs mandated by an external agency which is the owner or the administrator of the entire system. The model works fine for solving problems when processes cooperate with one another, with a global goal. In modern times it is quite common to have a distributed system spanning over multiple administrative domains, and processes have selfish motives to optimize their own pay- off. Maximizing individual payoffs under the umbrella of stabilization characterizes the notion of selfish stabilization . We investigate the impact of selfishness on the existence and the complexity of stabilizing solutions to specific problems in this thesis. Our model of selfishness centers on a graph where the set of nodes is divided into subsets of distinct colors, each having their own unique perception of the edge costs. We study the problems of constructing a rooted shortest path tree and a maximum flow tree on this model, and demonstrate that when processes are selfish, there is no guarantee that a solution will exist. We demonstrate that the complexity of determining the existence of a stabilizing solution is NP-complete, carefully characterize a fraction of such cases, and propose the construction of stabilizing solutions wherever such solutions are feasible. Fault containment and system availability are important issues in today's distributed systems. In this thesis, we show how fault-containment can be added to weakly stabilizing distributed systems. We present solutions using a randomized scheduler, and illustrate techniques to bias the random schedules so that the system recovers from all single faults in a time independent of the size of the system, and the effect of the failure is contained within constant distance from the faulty node with high probability (this probability can be controlled by a user defined tuning parameter). Using this technique, we solve two problems: one is the persistent-bit problem, and the other is the leader election problem.