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.

THE THREE DIMENSIONAL SHAPE AND ROUGHNESS OF MINERAL DUST

Mineral dust shape and roughness are important for a multitude of processes; it is known for aspherical shape but the true measurements in three dimensions are rare. Atomic Force Microscope was used for determine both 3D shape and roughness for two dust which are commonly used in laboratory experiments – Arizona Test Dust (ATD) and Kaolinite. We determined both of them are rather flat and round; an oblate spheroid would be a good model. Loess Filter was used to smooth the particles' surface and correlation analysis was used to examine the surfaces' properties of the dust; we found no features under 100nm scales. Also, our particles' surface area result is very similar to BET surface area.

Nitrogen oxides in the firn air at Summit, Greenland

Measurements of NOx within the snowpack at Summit, Greenland were carried out from June 2008 to July 2010, using a novel system to sample firn air with minimal disruption of the snowpack. These long-term measurements were motivated by the need of improving the representation of air-snow interactions in global models. Results indicated that the NOx budget within the snowpack was on the order of 550 pptv as maximum, and was constituted primarily for NO2. NOx production was observed within the first 50 cm of the snowpack during the sunlight season between February and August. Presence of NOx at larger depths was attributed to high speed wind and vertical transport processes. Production of NO correlated with the seasonal incoming radiation profile, while NO2 maximum was observed in April. These measurements constitute the larger data set of NOx within the firn and will improve the representation of processes driving snow photochemistry at Summit.