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.

Landscape and forest structure at moose mortality sites on Isle Royale National Park. A LiDAR based assessment

Landscape structure and heterogeneity play a potentially important, but little understood role in predator-prey interactions and behaviourally-mediated habitat selection. For example, habitat complexity may either reduce or enhance the efficiency of a predator's efforts to search, track, capture, kill and consume prey. For prey, structural heterogeneity may affect predator detection, avoidance and defense, escape tactics, and the ability to exploit refuges. This study, investigates whether and how vegetation and topographic structure influence the spatial patterns and distribution of moose (Alces alces) mortality due to predation and malnutrition at the local and landscape levels on Isle Royale National Park. 230 locations where wolves (Canis lupus) killed moose during the winters between 2002 and 2010, and 182 moose starvation death sites for the period 1996-2010, were selected from the extensive Isle Royale Wolf-Moose Project carcass database. A variety of LiDAR-derived metrics were generated and used in an algorithm model (Random Forest) to identify, characterize, and classify three-dimensional variables significant to each of the mortality classes. Furthermore, spatial models to predict and assess the likelihood at the landscape scale of moose mortality were developed. This research found that the patterns of moose mortality by predation and malnutrition across the landscape are non-random, have a high degree of spatial variability, and that both mechanisms operate in contexts of comparable physiographic and vegetation structure. Wolf winter hunting locations on Isle Royale are more likely to be a result of its prey habitat selection, although they seem to prioritize the overall areas with higher moose density in the winter. Furthermore, the findings suggest that the distribution of moose mortality by predation is habitat-specific to moose, and not to wolves. In addition, moose sex, age, and health condition also affect mortality site selection, as revealed by subtle differences between sites in vegetation heights, vegetation density, and topography. Vegetation density in particular appears to differentiate mortality locations for distinct classes of moose. The results also emphasize the significance of fine-scale landscape and habitat features when addressing predator-prey interactions. These finer scale findings would be easily missed if analyses were limited to the broader landscape scale alone.

COMPUTATIONAL STUDY OF MICROSTRUCTURE-PROPERTYMECHANISM RELATIONS IN FERROIC COMPOSITES

Ferroic materials, as notable members of smart materials, have been widely used in applications that perform sensing, actuation and control. The macroscopic property change of ferroic materials may become remarkably large during ferroic phase transition, leading to the fact that the macroscopic properties can be tuned by carefully applying a suitable external field (electric, magnetic, stress). To obtain an enhancement in physical and/or mechanical properties, different kinds of ferroic composites have been fabricated. The properties of a ferroic composite are determined not only by the properties and relative amounts of the constituent phases, but also by the microstructure of individual phase such as the phase connectivity, phase size, shape and spatial arrangement. This dissertation mainly focuses on the computational study of microstructure – property – mechanism relations in two representative ferroic composites, i.e., two-phase particulate magnetoelectric (ME) composite and polymer matrix ferroelectric composite. The former is a great example of ferroic composite exhibiting a new property and functionality that neither of the constituent phases possesses individually. The latter well represents the kind of ferroic composites having property combinations that are better than the existing materials. Phase field modeling was employed as the computing tool, and the required models for ferroic composites were developed based on existing models for monolithic materials. Extensive computational simulations were performed to investigate the microstructure-property relations and the underlying mechanism in ferroic composites. In particulate, it is found that for ME composite 0-3 connectivity (isolated magnetostrictive phase) is necessary to exhibit ME effect, and small but finite electrical conductivity of isolated magnetic phase can beneficially enhance ME effect. It is revealed that longitudinal and transverse ME coefficients of isotropic 0-3 particulate composites can be effectively tailored by controlling magnetic domain structures without resort to anisotropic two-phase microstructures. Simulations also show that the macroscopic properties of the ferroelectricpolymer composites critically depend on the ferroelectric phase connectivity while are not sensitive to the sizes and internal grain structures of the ceramic particles. Texturing is found critical to exploit the paraelectric«ferroelectric phase transition and nonlinear polarization behavior in paraelectric polycrystal and its polymer matrix composite. Additionally, a Diffuse Interface Field model was developed to simulate packing and motion in liquid phase which is promising for studying the fabrication of particulatepolymer composites.

GENERATING PLANS IN CONCURRENT, PROBABILISTIC, OVER-SUBSCRIBED DOMAINS

Planning in realistic domains typically involves reasoning under uncertainty, operating under time and resource constraints, and finding the optimal subset of goals to work on. Creating optimal plans that consider all of these features is a computationally complex, challenging problem. This dissertation develops an AO* search based planner named CPOAO* (Concurrent, Probabilistic, Over-subscription AO*) which incorporates durative actions, time and resource constraints, concurrent execution, over-subscribed goals, and probabilistic actions. To handle concurrent actions, action combinations rather than individual actions are taken as plan steps. Plan optimization is explored by adding two novel aspects to plans. First, parallel steps that serve the same goal are used to increase the plan’s probability of success. Traditionally, only parallel steps that serve different goals are used to reduce plan execution time. Second, actions that are executing but are no longer useful can be terminated to save resources and time. Conventional planners assume that all actions that were started will be carried out to completion. To reduce the size of the search space, several domain independent heuristic functions and pruning techniques were developed. The key ideas are to exploit dominance relations for candidate action sets and to develop relaxed planning graphs to estimate the expected rewards of states. This thesis contributes (1) an AO* based planner to generate parallel plans, (2) domain independent heuristics to increase planner efficiency, and (3) the ability to execute redundant actions and to terminate useless actions to increase plan efficiency.