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.

DESIGN OF EFFICIENT IN-NETWORK DATA PROCESSING AND DISSEMINATION FOR VANETS

By providing vehicle-to-vehicle and vehicle-to-infrastructure wireless communications, vehicular ad hoc networks (VANETs), also known as the “networks on wheels”, can greatly enhance traffic safety, traffic efficiency and driving experience for intelligent transportation system (ITS). However, the unique features of VANETs, such as high mobility and uneven distribution of vehicular nodes, impose critical challenges of high efficiency and reliability for the implementation of VANETs. This dissertation is motivated by the great application potentials of VANETs in the design of efficient in-network data processing and dissemination. Considering the significance of message aggregation, data dissemination and data collection, this dissertation research targets at enhancing the traffic safety and traffic efficiency, as well as developing novel commercial applications, based on VANETs, following four aspects: 1) accurate and efficient message aggregation to detect on-road safety relevant events, 2) reliable data dissemination to reliably notify remote vehicles, 3) efficient and reliable spatial data collection from vehicular sensors, and 4) novel promising applications to exploit the commercial potentials of VANETs. Specifically, to enable cooperative detection of safety relevant events on the roads, the structure-less message aggregation (SLMA) scheme is proposed to improve communication efficiency and message accuracy. The scheme of relative position based message dissemination (RPB-MD) is proposed to reliably and efficiently disseminate messages to all intended vehicles in the zone-of-relevance in varying traffic density. Due to numerous vehicular sensor data available based on VANETs, the scheme of compressive sampling based data collection (CS-DC) is proposed to efficiently collect the spatial relevance data in a large scale, especially in the dense traffic. In addition, with novel and efficient solutions proposed for the application specific issues of data dissemination and data collection, several appealing value-added applications for VANETs are developed to exploit the commercial potentials of VANETs, namely general purpose automatic survey (GPAS), VANET-based ambient ad dissemination (VAAD) and VANET based vehicle performance monitoring and analysis (VehicleView). Thus, by improving the efficiency and reliability in in-network data processing and dissemination, including message aggregation, data dissemination and data collection, together with the development of novel promising applications, this dissertation will help push VANETs further to the stage of massive deployment.

Evaluating stress patterns for Plio-Quaternary brittle deformation along the Calama-Olacapato-El Toro fault zone, Central Andes

Understanding the geometry and kinematics of the major structures of an orogen is important to elucidate its style of deformation, as well as its tectonic evolution. We describe the temporal and spatial changes in the state of stress of the trans-orogen area of the Calama-Olacapato-El Toro (COT) Fault Zone in the Central Andes, at about 24°S within the northern portion of the Puna Plateau between the Argentina-Chile border. The importance of the COT derives principally from the Quaternary-Holocene activity recognized on some segments, which may shed new light on its possible control on Quaternary volcanism and on the seismic hazard evaluation of the area. Field geological surveys along with kinematic analysis and numerical inversion of ∼140 new fault-slip measurements have revealed that this portion of the COT zone, previously considered a continuous, long-lived lineament, in reality has been subjected to three different kinematic regimes: 1) a Miocene transpressional phase with the maximum principal stress (σ1) chiefly trending NNE-SSW; 2) an extensional phase that started by 9 Ma, with a horizontal NW-SE-striking minimum principal stress (σ3) – permutations between σ2 and σ3 axes have been recognized at two sites – and 3) a left-lateral strike-slip phase with a horizontal ∼E-W &sigma1 and ∼N-S σ3 dating to the Late Pliocene-Quaternary. Spatially, in the Quaternary, the left-lateral component decreases toward the westernmost tip of the COT, where it transitions to extension; this produced to a N-S horst and graben structure. Hence, even if transcurrence is still active in the eastern portion of the COT, as focal mechanisms of crustal earthquakes indicate, our study demonstrates that extension is becoming the predominant structural style of deformation, at least in the western region. These major temporal and spatial changes in the tectonic regimes are attributed in part to changes in the magnitude of the boundary forces due to subduction processes. The overall orogen-perpendicular extension might be the result of vertical stress larger than both the horizontal stresses induced by gravitational effect of a thickened crust.

FAULT MORPHOLOGY WITHIN THE SOUTHERN KENYAN PORTION OF THE EAST AFRICAN RIFT VALLEY

Faults form quickly, geologically speaking, with sharp, crisp step-like profiles. Logic dictates that erosion wears away this "sharpness" or angularity creating more rounded features. As erosion occurs, debris accumulates at the base of the scarp slope. The stable end point of this process is when the scarp slope approaches an ideal sigmoid shape. This theory of fault end process, in combination with a new method developed in this report for fault profile delineation, has the potential to enable observation and categorization of fault profiles over large, diverse swaths of fault formation-- in remote areas such as the Southern Kenyan Rift Valley. This up-to date method uses remote sensing data and the digitizer tool in Global Mapper to create shape files of fault segments. This method can provide further evidence to support the notion that sigmoidal- shaped profiles represent a natural endpoint of the erosional process of fault scarps. Over time, faults of many different ages would exist in this similar shape over a wide region. However, keeping in mind that other processes can be at work on scarps-- most notably drainage patterns, when anomalies in profiles are observed, reactivation in some form possibly has occurred.