Physical Sciences and Mathematics Commons^™

On The Limits And Practice Of Automatically Designing Self-Stabilization, Alex Klinkhamer

Dissertations, Master's Theses and Master's Reports

A protocol is said to be self-stabilizing when the distributed system executing it is guaranteed to recover from any fault that does not cause permanent damage. Designing such protocols is hard since they must recover from all possible states, therefore we investigate how feasible it is to synthesize them automatically. We show that synthesizing stabilization on a fixed topology is NP-complete in the number of system states. When a solution is found, we further show that verifying its correctness on a general topology (with any number of processes) is undecidable, even for very simple unidirectional rings. Despite these negative results, …

Randomized Algorithms For Approximating A Connected Dominating Set In Wireless Sensor Networks, Akshaye Dhawan, Michelle Tanco, Aaron Yeiser

Mathematics and Computer Science Faculty Publications

A Connected Dominating Set (CDS) of a graph representing a Wireless Sensor Network can be used as a virtual backbone for routing through the network. Since the sensors in the network are constrained by limited battery life, we desire a minimal CDS for the network, a known NP-hard problem. In this paper we present three randomized algorithms for constructing a CDS. We evaluate our algorithms using simulations and compare them to the two-hop K2 algorithm and two other greedy algorithms from the literature. After pruning, the randomized algorithms construct a CDS that are generally equivalent in size to those constructed …

Dcamp: Distributed Common Api For Measuring Performance, Alexander Paul Sideropoulos

Master's Theses

Although the nearing end of Moore’s Law has been predicted numerous times in the past, it will eventually come to pass. In forethought of this, many modern computing systems have become increasingly complex, distributed, and parallel. As software is developed on and for these complex systems, a common API is necessary for gathering vital performance related metrics while remaining transparent to the user, both in terms of system impact and ease of use.

Several distributed performance monitoring and testing systems have been proposed and implemented by both research and commercial institutions. However, most of these systems do not meet several …

Keynote: Emerging Era Of Cooperative Empowerment: Grid, Peer-To-Peer, And Community Computing, Dr. Javed I. Khan

International Conference on Information and Communication Technologies

In this paper we discuss an emerging trend in high performance computing-the social or community computing. The emergence of screensaver computing, grid computing, peer-to-peer systems, and their demonstrated ability to garner computing power as potent as the supercomputers seems to be auspicious. In this paper we discuss the new phenomenon of community computing-including their potential applications in solving a new set of grand challenge problems. We also discuss the previously uncharted technological challenges architects of these new paradigms are addressing.

3d Outside Cell Interference Factor For An Air-Ground Cdma ‘Cellular’ System, David W. Matolak

Faculty Publications

We compute the outside-cell interference factor of a code-division multiple-access (CDMA) system for a three-dimensional (3-D) air-to-ground (AG) "cellular-like" network consisting of a set of uniformly distributed ground base stations and airborne mobile users. The CDMA capacity is roughly inversely proportional to the outside-cell interference factor. It is shown that for the nearly free-space propagation environment of these systems, the outside-cell interference factor can be larger than that for terrestrial propagation models (as expected) and depends approximately logarithmically upon both the cell height and cell radius.

Issues In Automated Distribution Of Processes Over The Networks, Alexey Morozov

Honors Theses

The main goal of this paper is t o survey the issues an application developer would have to resolve in producing a system that would be able to spread its computational load across several computers connected by a network. Before this can be done, a brief introduction to distributed and parallel computing is necessary.