Physical Sciences and Mathematics Commons^™

On The Complexity Of Implementing Certain Classes Of Shared Objects, King Yang Tan

Dartmouth College Ph.D Dissertations

We consider shared memory systems in which asynchronous processes cooperate with each other by communicating via shared data objects, such as counters, queues, stacks, and priority queues. The common approach to implementing such shared objects is based on locking: To perform an operation on a shared object, a process obtains a lock, accesses the object, and then releases the lock. Locking, however, has several drawbacks, including convoying, priority inversion, and deadlocks. Furthermore, lock-based implementations are not fault-tolerant: if a process crashes while holding a lock, other processes can end up waiting forever for the lock.

Wait-free linearizable implementations were conceived …

Investigation Of Third Party Rights Service And Shibboleth Modification To Introduce The Service, Sanket Agrawal

Dartmouth College Master’s Theses

Shibboleth is an architecture to support inter-institutional sharing of electronic resources that are subject to access control. Codifying copyright in Shibboleth authorization policies is difficult because of the copyright exceptions which can be highly subjective. Third Party Rights Service is a high-level concept that has been suggested as a solution to approximate the exceptions of copyright law. In this thesis, I investigate the components of the Third Party Rights Service. I design and analyze a modified Shibboleth architecture based on these components. The resulting architecture allows for the phased addition of the resources to make use of the Third Party …

Enhancing Asynchronous Parallel Computing, Elizabeth Anne Hamon

Dartmouth College Undergraduate Theses

In applications using large amounts of data, hiding the latency inherent in accessing data far from the processor is often necessary in order to achieve high performance. Several researchers have observed that one way to address the challenge of latency is by using a common structure: in a series of passes, the program reads in the data, performs various operations on it, and writes out the data. Passes often consist of a pipeline structure composed of different stages. In order to achieve high performance, the stages are frequently overlapped, for example, by using asynchronous threads. Out-of-core parallel programs provide one …

An Evaluation Of The Impact Of Models For Radio Propagation On The Simulation Of 802.11b Wireless Networks, Evan W. Richardson

Dartmouth College Undergraduate Theses

Working with an existing wireless network simulator, we describe the addition of both a method for modeling arbitrary terrain, and for calculating signal attenuation with the Irregular Terrain Model (ITM). We also investigate ITM's effects on upper protocol layer in comparison to the Two-Ray Ground Reflection model. Upon examination, it was found that aside from the terrain between the transmitter and receiver, ITM's various parameters are of little significance in the computed signal attenuation. Further, examination of the behavior of the upper protocol layers revealed that at high traffic levels, choice of propagation model can have significant effects on the …

802.11b Wireless Network Visualization And Radiowave Propagation Modeling, Chris Lentz

Dartmouth College Undergraduate Theses

This paper outlines the methods of creating detailed coverage maps of 802.11b networks, with an emphasis on minimizing the expenses and time involved. The goal of this work is to develop and present a streamlined, reproducible approach to wireless visualization as well as techniques for predicting coverage area before conducting network installations. After evaluating these coverage maps, a repeated series of field measurements will be checked against interpolated values in order to improve techniques for extrapolation of data for unsampled regions. If successful, these extrapolation techniques will provide additional guidelines for, and assist modeling of, new wireless network installations. However, …

Power Conservation In The Network Stack Of Wireless Sensors, Michael De Rosa

Dartmouth College Undergraduate Theses

Wireless sensor networks have recently become an incredibly active research area in the networking community. Much attention has been given to the construction of power-conserving protocols and techniques, as battery life is the one factor that prevents successful wide-scale deployment of such networks. These techniques concentrate on the optimization of network behavior, as the wireless transmission of data is the most expensive operation performed by a sensor node. Very little work has been published on the integration of such techniques, and their suitability to various application domains. This paper presents an exhaustive power consumption analysis of network stacks constructed with …

Spade: Spki/Sdsi For Attribute Release Policies In A Distributed Environment, Sidharth P. Nazareth

Dartmouth College Master’s Theses

Shibboleth is a federated administrated system that supports inter-institutional authentication and authorization for sharing of resources. SPKI/SDSI is a public key infrastructure whose creation was motivated by the perception that X.509 is too complex and flawed. This thesis addresses the problem of how users that are part of a Public Key Infrastructure in a distributed computing system can effectively specify, create, and disseminate their Attribute Release Policies for Shibboleth using SPKI/SDSI. This thesis explores existing privacy mechanims, as well as distributed trust management and policy based systems. My work describes the prototype for a Trust Management Framework called SPADE (SPKI/SDSI …

Electronic Documents And Digital Signatures, Kunal Kain

Dartmouth College Master’s Theses

Often, the main motivation for using PKI in business environments is to streamline workflow, by enabling humans to digitally sign electronic documents, instead of manually signing paper ones. However, this application fails if adversaries can construct electronic documents whose viewed contents can change in useful ways, without invalidating the digital signature. In this paper, we examine the space of such attacks, and describe how many popular electronic document formats and PKI packages permit them.

Discovery, Visualization And Analysis Of Gene Regulatory Sequence Elements In Genomes, Daniel F. Simola

Dartmouth College Undergraduate Theses

The advent of rapid DNA sequencing has produced an explosion in the amount of available sequence information, permitting us to ask many new questions about DNA. There is a pressing need to design algorithms that can provide answers to questions related to the control of gene expression, and thus to the structure, function, and behavior of organisms. Such algorithms must filter through massive amounts of informational noise to identify meaningful conserved regulatory DNA sequence elements. We are approaching these questions with the notion that visualization is a key to exploring data relationships. Understanding the exact nature of these relationships can …

A Progressive Folding Algorithm For Rna Secondary Structure Prediction, Samuel J. Stearns

Dartmouth College Master’s Theses

RNA secondary structure prediction is an area where computational techniques have shown great promise. Most RNA secondary structure prediction algorithms use dynamic programming to compute a secondary structure with minimum free energy. Energy minimization algorithms are less accurate on larger RNA molecules. One potential reason is that larger RNA molecules do not fold instantaneously. Instead, several studies show that RNA molecules fold progressively during transcription. This process could encourage the molecule to fold into a structure that is not at the global lowest energy level. Additionally, dynamic programming algorithms do not allow for a important type of structure called a …

Using Low Level Linear Memory Management For Type-Preserving Mark-Sweep Garbage Collector, Edward Wei

Dartmouth College Undergraduate Theses

Efficient low-level systems such as garbage collectors need more control over memory than safe high-level languages usually provide. Due to this constraint, garbage collectors are typically written in unsafe languages such as C. A collector of this form usually resides as a trusted primitive runtime service outside the model of the programming language. The type safety of these languages depends on the assumption that the garbage collector will not violate any typing invariants. However, no realistic systems provide proof of this assumption. A garbage collector written in a strongly typed language can guarantee not only the safety of the garbage …

An Analysis Of Convergence Properties Of The Border Gateway Protocol Using Discrete Event Simulation, Brian J. Premore

Dartmouth College Ph.D Dissertations

The Internet is an enormous internetwork formed by connecting tens of thousands of independently managed computer networks. Though the Internet has no central authority and is highly heterogeneous, a universally adopted addressing scheme---defined by the Internet Protocol (IP)---makes interaction between the individual networks possible. Complementing IP is the Border Gateway Protocol (BGP), which facilitates communication between parts of the internetwork by determining paths by which data can get from one network to any other. Just as IP is used ubiquitously as an addressing scheme, BGP is used ubiquitously for the purpose of network-to-network routing. Because BGP is universal, its well-being …

Persistence And Prevalence In The Mobility Of Dartmouth Wireless Network Users, Clara Lee

Dartmouth College Undergraduate Theses

Wireless local-area networks (WLANs) are increasing in popularity. As more people use WLANs it is important to understand how these users behave. We analyzed data collected over three months of 2002 to measure the persistence and prevalence of users of the Dartmouth wireless network.

We found that most of the users of Dartmouth's network have short association times and a high rate of mobility. This observation fits with the predominantly student population of Dartmouth College, because students do not have a fixed workplace and are moving to and from classes all day.

Billiards Adviser As A Search In A Continuous Domain With Significant Uncertainty, Thomas Mueller

Dartmouth College Undergraduate Theses

Typical search algorithms are limited to problems in which there is a certain number of moves for any given state, and the effect of each move is well known. In order to overcome this limitation, we consider the problem of determining the optimal shot given the positions of balls on a billiards table. Our solution includes the image recognition necessary to determine each ball's position, the calculation of the optimal shot, and the presentation of that shot to the player. The focus of the paper is on the second part - determining the angle and force with which the player …

Trusted S/Mime Gateways, Mindy J. Pereira

Dartmouth College Undergraduate Theses

The utility of Web-based email clients is clear: a user is able to access their email account from any computer anywhere at any time. However, this option is unavailable to users whose security depends on their key pair being stored either on their local computer or in their browser. Our implementation seeks to solve two problems with secure email services. The first that of mobility: users must have access to their key pairs in order to perform the necessary cryptographic operations. The second is one of transition: initially, users would not want to give up their regular email clients. Keeping …

An Active Learning Approach To Efficiently Ranking Retrieval Engines, Lisa A. Torrey

Dartmouth College Undergraduate Theses

Evaluating retrieval systems, such as those submitted to the annual TREC competition, usually requires a large number of documents to be read and judged for relevance to query topics. Test collections are far too big to be exhaustively judged, so only a subset of documents is selected to form the judgment ``pool.'' The selection method that TREC uses produces pools that are still quite large. Research has indicated that it is possible to rank the retrieval systems correctly using substantially smaller pools. This paper introduces an active learning algorithm whose goal is to reach the correct rankings using the smallest …

Efficient I/O For Computational Grid Applications, Ron A. Oldfield

Dartmouth College Ph.D Dissertations

High-performance computing increasingly occurs on "computational grids" composed of heterogeneous and geographically distributed systems of computers, networks, and storage devices that collectively act as a single "virtual" computer. A key challenge in this environment is to provide efficient access to data distributed across remote data servers. This dissertation explores some of the issues associated with I/O for wide-area distributed computing and describes an I/O system, called Armada, with the following features: a framework to allow application and dataset providers to flexibly compose graphs of processing modules that describe the distribution, application interfaces, and processing required of the dataset before or …

Flexible And Scalable Public Key Security For Ssh, Yasir Ali

Dartmouth College Master’s Theses

A standard tool for secure remote access, the SSH protocol uses public-key cryptography to establish an encrypted and integrity-protected channel with a remote server. However, widely-deployed implementations of the protocol are vulnerable to man-in-the-middle attacks, where an adversary substitutes her public key for the server's. This danger particularly threatens a traveling user Bob borrowing a client machine.

Imposing a traditional X.509 PKI on all SSH servers and clients is neither flexible nor scalable nor (in the foreseeable future) practical. Requiring extensive work or an SSL server at Bob's site is also not practical for many users.

This paper presents our …