This dissertation presents a new debugging assistant called a Debugging Critic.  As an alternative to an automated debuggin oracle, the debugging critic evaluates hypotheses about fault locations.  If it cannot confirm that the code at the hypothesized location contains a fault, it formulates an alternative hypothesis about the location of a faulty statement or the location of omitted statements.  The debugging critic derives knowledge of possible locations of a fault that manifested itself under a given test case from failure symptoms.  Therefore, it can operate without a line-by-line specification and a knowledge base of faults. A prototype of our debugging critic has been implemented as an extension of an existing debugger, Spyder.  An experiment with Spyder shows that programmers debug two to four times faster on the average with the debugging critic than without it.  Ninety-two percent of the critic’s users recommend the critic as an extension of conventional debuggers. The research iin this dissertation contributes to debugging and critic systems.  In debugging, our experiment shows that an active debugging assistant can effectively improve debugging performance.  Another contribution is our approach to evaluate and formulate hypotheses about fault locations, especially the locations of omitted statements.  In critic systems, our contribution is the use of questions to prevent information and non-insulting criticism.

Traditionally, compilers available to the software developer/tester have only supported two software testing techniques, statement and branch coverage.  However, during compilation, sufficient syntactic and semantic information is available to provide support for additional testing techniques. This dissertation presents an approach to integrate support for program mutation, a well-known and effective software testing technique, directly into a compiler.  The paradigm permits the intermediate states of computation within a machine-executable program to be monitored or modified subsequent to compilation, without recompiling the program.  Program mutations are performed in an efficient manner on native machine-code, and direct support is provided for effective mutant execution on MIMD architectures.  As such, the paradigm provides facilities for the development of practical tools that allow support for program mutation, while improving the cost-effectiveness of both experimental and testing applications. The paradigm is based upon program patch generation and application.  A prototype patch-generating C compiler, and mutation-based software testing environment utilizing this paradigm, have been constructed in order to demonstrate the approach.  The prototype implementation supports the manipulation of separately compiled programs and, therefore, permits potentially large software systems to be tested.  A set of experimental results compares the effectiveness of the compiler-integrated approach, employed by the prototype, to that employed by existing mutation-based software testing environments in providing support for program mutation.

In this thesis, we prove that well designed communication support can make the use of address spaces and high-level interfaces a practical solution to the structuraing problems of complex distributed transaction processing systems.  Such support includes efficient local interrocess communication, transaction-oriented multicasting and naming schemes, and specialized scheduling and synchronization policies.  We take the implementation and experimental approach to prove our thesis.  First, we identify the communication needs in a distributed transaction processing system.  Second, we design a new communication facility that addresses those needs.  Finally, we implement a prototype of the new communication facility and measure its impact on transaction processing. The new communication facility features shared-memory ports, a simple naming scheme, and a transaction-oriented multicasting mechanism,  Local and remote communication is through ports.  Ports can be accessed directly by the kernel and by user-level processes.  The naming schemes used for the application and network levels avoids the use of name-resolution protocols.  The multicasting mechanism is CPU and network efficient.  The new communication facility reduces kernel overhead during transation processing by up to 70%. To conduct some of the experiments in this thesis, we developed a system called Push.  It allows the modification of operating system services at run time.  Push is based on an extension language interpreted within the kernel.  It enables experimentation that would be difficult and time-consuming in current-environments.  The overhead of the Push implementation can be factored out to give a good estimate of the performance of a native kernel implementation.  We have used Push to implement kernel-resident communication services.  A multicasting implementation in Push has an inherent overhead of .32 milliseconds per additional site.  The corresponding overhead for a direct kernel-level implementation is 0.5 milliseconds and for a user-level implementation 0.57 milliseconds.

The main objective of replication in distributed database systems is to increase data availability.  However, the overhead associated with relication may impair the performance of transaction processing.  Moreover, in the presence of changing failure and transaction characteristcs, static replication schemes are so restrictive that they may actually decrease availability. The purpose of this research is to show how adaptability and data reconfiguration can be used in conjunction with static replcation schemes to achieve and maintain higher levels of availability.  The basis of this research is an integrated study of availability and performance of replication methods.  The integrated study was suggested as a future work in [Pu85}.  The availability analysis part of the study is performed through an analystical model.  The performance evaluation part is conducted on the second version of the RAID distributed database system developed at Purdue. We classify availability into two categories: algorithmic and operational.  While algorithmic availability measures the fault-tolerance provided by replication methods against component failures, operational availability examines the effect of performance failure on the validity of the algorithmic measure.  Performance failure can result from an inefficient implementation of an expensive fault-tolerant replication method.  Algorithmic availability is studied through an analytical model that ecompasses transaction and database parameters, site and communication link failures, and replication methods’ paramters.  Operational availability is examined, experimentally, through near-saturation performance measurements of an actual implementation of replication methods. We implement a variety of replication mechanisms and an infrastructure for adaptability to detected and predicted failures.  The implementation includes off-line relicatin management, a stand-alone replication control server, a quorum-based interface to a library of replication methods, quorum selection heuristics, a surveillance facility, and a dynamic data reconfiguration protocol.  The effectiveness and performance of our implementation, methods, and ideas are tested through experimental measurements of transaction performance.  The experiments use an extended version of the standard DebitCredit benchmark. Using the availability model and the RAID system combined, a series of experiments are conducted.  We study static replication schemes and devlop local policies for their efficient use.  We then examine how to adapt the use of these schemes to perturbations in parameters which includes transaction read/write mix and site and communication link reliabilities.  The experiments give a number of insights about how to adapt replication in order to increase the availability of fault-intolerant replication methods, and reduce performance penalties of methods which are highly fault-tolerant.

The virtual memory abstraction aids in the design and implementation of portable aplications.  Virtual memory allows applications to execute in an arbitrarily large memory space, independent from the physical memory size of the underlying machine. Conventional virtual memory operating systems use magnetic disks for backing storage.  Magnetic disks provide high data transfer rates, large storage capacity, and the ability to randomly access data, making them an appealing backing storage medium.  However, the average seek time of a magnetic disk is several orders of magnitude slower than memory access times.  Recent advances in CPU speeds, network banwidth, and memory sizes have made new types of backing storage with imroved performance and greater functionality feasible. This thesis invesigates a new model for virtual memory in which dedicated, large-memory machines provide backing storage to virtual memory systems executing on a set of client machines in a distributed envionment.  Dedicated memory servers provide clients with a large, shared memory resource.  Each memory server machine is capable of supporting heterogeneous client machines executing a wide variety of operating systems.  Clients that exceed the capacity of their local memory access remote memory servers across a high-speed netowrk to obtain additional storage space.  Clients use a highly efficient, special purpose, reliable, data streaming, network architecture independent communication protocol to transfer data to and from the memory server.  To reduce the delay associated with accessing remote memory, memory servers use efficient algorithms and data structures to retrieve data, on average, in constant time.  In addition to providing a highly-efficient backing store, the model allows data sharing between clients and improves file system performance by offloading the file server. This thesis also describes the design and implementation of a prototype system.  Measurements obtained from the prototype implementation clearly demonstrate the viability of systems based on the model.  The prototype shows that remote memory systems offer performance competitive with, and in some cases better than, existing virtual memory systems.  Moreover, rapid advances in network bandwidth, CPU speeds, and memory sizes make the model an attractive basis for the design of future distributed systems.

The availability of low-cost, high-bandwidth optical fiber will change the technology and use of wide-area networks by allowing lower-cost, higher-speed communication.  Higher transmission rates combined with wide geographical distribution will require new protocols for dynamic resource allocation in wide-area computer networks. This thesis analyzes a scheme to approach the problem of network congestion for high-speed packet switches that provide datagram services. The analyzed algorithm, which has been propose by Yavatkar [Yava89], avoids congestion by restricting excessive traffic at the entry of the network and by operating the network adaptively on a rate basis at the “knee point” of the delay-throughput curve.  At this point a possible increase in throughput is small but would cause a relatively large increase of transmission delay. The algorithm is analyzed by using basic, simple topologies to get an understanding of its stationary and dynamic behavior.  The thesis analyzes the characteristics, problems and compromises of the algorithm.  The congestion avoidance and control mechanism basically trades resource efficiency for a small transmission delay inside the network and higher reliability.  A low signal-to-noise ration of the traffic measurements limites the effectiveness of the rate control. The analysis is based on computer simulation experiments using the simulation language CSIM.

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.