This dissertation desribes selected software issues of mapping tasks onto parallel processing systems that are shown to have a strong effect on performance.  It can be divided into two related categories: (1) parallel mapping studies, and (2) an analysis of dynaic task migration for fault-tolerance, load balancing, and various other administrative reasons.  The first category consists of two application case studies, specifically, the computation of multiple quadratic forms and image correlation.  The goal of this part of the work is to understand the relationship between parallel system features (e.g., mode of parallelism supported, number of processors available, communication speed, computation speed) and parallel algorithm characteristics (e.g., amount of data-parallelism available, amount of functional-parallelism available, amount of scalar computation present).  The knowledge obtained from the parallel mapping studies provided the foundation necessay to investigate the second category, the task migration work.  This research involved developing a method to migrate dynamically a task between a SIMD (single instruction stream - multiple data stream) machine and a SPMD (single program-multiple data stream) machine.  It is assumed that the SIMD and SPMD machines only differ to support the different modes of parallelism, and that the program was coded in a mode-independent programming language.  This area of research targets system that are either a network of different tpes of computers or a single system that can support multiple mods of parallelism.

This dissertation studies the trade-off between route adaptation and persistence.  Our thesis is that adding route persistence to shortest-path routing can enhance network performance, especially under heavy traffic conditions.  Shortest-path routing can cause route oscillation and instability, thereby increasing congestion and reducing the effective throughput of the network. To study the effect of route persistence on network performance, the dissertation inroduces a new class of routing techniques, called semi-persistent techniques, that offer a trade-off between route adaptation and persistence.  Semi-persistent techniques add route persistence to shortest-path computation.  This route persistence reduces oscillation by reducing the number of routes that shift from high-traffic links to low-traffic links.  With various levels of route persistence, semi-persistent techniques exhibit multiple routing behaviors that span a spectrum between shortest-path and static routing. This dissertation offers a promising advance for network routing.  Simulation results show that certain semi-persistent techniques achieve significant throughput increases over shortest-path routing for a majority of the studied topologies and traffic loads.  With further study of the relationship between traffic load and the persistence level of maximal throughput, semi-persistent techniques may be designed to effectively adjust their routing behavior to suit current network conditions.

Recovery methods for replicated database systems should handle both site and network partitioning failures as efficiently as possible.  Techniques are needed that use knowledge about what happened during a failure to reduce the costs of recovery.  Another promising approach is to use information stored at replicated copies to improve the efficiency of recovery.  For such techniques to be applicable to broad classes of replicated copy control algorithms, a correctness model is needed that encompasses different possibilities for object representation and gives correctness conditions for classes of algorithms.  We define a new model for replicated objects in which an object’s representation consists of a set of timestamped values plus a set of histories containing records of operation executions, and we give a criterion for correct transaction processing in terms of this model.  We classify quorum-based recovery methods into four categories, ranging from static to dynamic, and develop correctness conditions for each category.  We describe techniques for reducing the costs of recovery for dynamic quorum methods.  Lastly, we investigate how communication-based recovery that takes advantage of replicated copies can be integrated with quorum methods.

This thesis proposes several mechanisms to deal with recovery and data availability issues in distributed systems. Checkpointing in a distributed system is essential for recovery to a globally consistent state after failure.  We present a checkpointing/rollback recovery algorithm in which each process takes checkpoints independently.  In our approach a number of checkpointing processes, a number of rollback processes, and computations on operational processes can proceed concurrently while tolerating the failure of an arbitrary number of processes.  During recovery after a failure, a process invokes a two phase rollback algorithm.  In the first phase, it collects information about relevant message exchanges in the system and uses it in the second phase to determine both the set of processes that must roll back and the set of checkpoints upto which rollback must occur. We have implemented the checkpointing and rollback recovery algorithm and evaluated its performance in a real processing environment.  The evaluation measures the overhead due to time spent in executing the algorithm and the cost in terms of computational time and message traffic.  We identify the components that make up the execution time of the algorithm and study how each of them contributes to the total execution time. A typed token scheme for managing replicated data in distributed databaasse systems is proposed in this thesis.  Compared to previous schemes, for each object, a set of tokens is used.  Each token represents a specific capability for the allowable operations on the object.  By distributing tokens to different physical copies of the object, the object can be made available for different operations in various partitions of the network failure.  two types of replication for each of these tokens are proposed.  One is based on the semantics of operations and the other is based on the semantics of the object.  When failures are anticipated, tokens can be redistributed to maintain high availability. We present a merge recovery scheme for efficient recovery of database consistency from dynamic partitioning and merge.  In the merge recovery scheme, information needed for recovery is organized in a partition tree so that missing updates can be efficiently carried out when partition merge.  The merge recovery scheme is used to support the typed token scheme for efficient partition merge.  It can also be used to extend some other replica control protocol.

This dissertation demonstrates that inadequately protected wireless LANs are more vulnerable to rogue program attack than traditional LANs.  Wireless LANs not only run the same risks as traditional LANs, but they also run additional risks associated with an open transmission medium.  Intruders can scan radio waves and, given enough time and resources, intercept, analyze, decipher, and reinsert data into the transmission medium. This dissertation describes the development and instantiation of an abstract model of the rogue code insertion process into a DOS-based wireless communications system using Radio Frequency (RF) atmospheric signal transmission.  The model is general enough to be applied to widely used target environments such as UNIX, Macintosh and DOS operating systems.  The methodology and three modules, the prober, activator, and trigger modules, to generate rogue code and insert it into a wireless LAN were developed to illustrate the efficacy of the model. Also incorporated into the model are defense measures against remotely introduced rogue programs and a cost-benefit analysis that determined that such defenses for a specific environment were cost-justified.