Computer Sciences Commons^™

Lock-Free Scheduling Of Logical Processes In Parallel Simulation, Xiaowen Liu, David M. Nicol, King Tan Dartmouth College

Computer Science Technical Reports

With fixed lookahead information in a simulation model, the overhead of asynchronous conservative parallel simulation lies in the mechanism used for propagating time updates in order for logical processes to safely advance their local simulation clocks. Studies have shown that a good scheduling algorithm should preferentially schedule processes containing events on the critical path. This paper introduces a lock-free algorithm for scheduling logical processes in conservative parallel discrete-event simulation on shared-memory multiprocessor machines. The algorithm uses fetch\&add operations that help avoid inefficiencies associated with using locks. The lock-free algorithm is robust. Experiments show that, compared with the scheduling algorithm using …

Ambiguity-Directed Sampling For Qualitative Analysis Of Sparse Data From Spatially-Distributed Physical Systems, Chris Bailey-Kellogg, Naren Ramakrishnan

Computer Science Technical Reports

A number of important scientific and engineering applications, such as fluid dynamics simulation and aircraft design, require analysis of spatially-distributed data from expensive experiments and complex simulations. In such data-scarce applications, it is advantageous to use models of given sparse data to identify promising regions for additional data collection. This paper presents a principled mechanism for applying domain-specific knowledge to design focused sampling strategies. In particular, our approach uses ambiguities identified in a multi-level qualitative analysis of sparse data to guide iterative data collection. Two case studies demonstrate that this approach leads to highly effective sampling decisions that are also …

A Market-Based Model For Resource Allocation In Agent Systems, Jonathan Bredin, David Kotz, Daniela Rus

Dartmouth Scholarship

In traditional computational systems, resource owners have no incentive to subject themselves to additional risk and congestion associated with providing service to arbitrary agents, but there are applications that benefit from open environments. We argue for the use of markets to regulate agent systems. With market mechanisms, agents have the abilities to assess the cost of their actions, behave responsibly, and coordinate their resource usage both temporally and spatially. \par We discuss our market structure and mechanisms we have developed to foster secure exchange between agents and hosts. Additionally, we believe that certain agent applications encourage repeated interactions that benefit …

Reconstructing Ancient Egyptian Tombs, Hany Farid

Computer Science Technical Reports

From the pyramids of Giza to the tombs of Thebes (modern Luxor), ancient Egypt's glorious history has produced remarkable architecture. Sadly, the nearly four million yearly tourists have taken a heavy toll on many of these ancient structures. Of particular concern are many of the tombs located opposite to Luxor on the western bank of the Nile. Digital reconstruction of these tombs has the potential to help document and preserve these important historical structures. Photographing and reconstruction of these tombs poses new and unique problems that this paper begins to address. Techniques for removing image distortions, recovering 3-D shape, and …

Bayes Optimal Metasearch: A Probabilistic Model For Combining The Results Of Multiple Retrieval Systems, Javed A. Aslam, Mark Montague

Computer Science Technical Reports

We introduce a new, probabilistic model for combining the outputs of an arbitrary number of query retrieval systems. By gathering simple statistics on the average performance of a given set of query retrieval systems, we construct a Bayes optimal mechanism for combining the outputs of these systems. Our construction yields a metasearch strategy whose empirical performance nearly always exceeds the performance of any of the constituent systems. Our construction is also robust in the sense that if ``good'' and ``bad'' systems are combined, the performance of the composite is still on par with, or exceeds, that of the best constituent …

A Survey Of Context-Aware Mobile Computing Research, Guanling Chen, David Kotz

Computer Science Technical Reports

Context-aware computing is a mobile computing paradigm in which applications can discover and take advantage of contextual information (such as user location, time of day, nearby people and devices, and user activity). Since it was proposed about a decade ago, many researchers have studied this topic and built several context-aware applications to demonstrate the usefulness of this new technology. Context-aware applications (or the system infrastructure to support them), however, have never been widely available to everyday users. In this survey of research on context-aware systems and applications, we looked in depth at the types of context used and models of …

Performance Analysis Of Mobile Agents For Filtering Data Streams On Wireless Networks, David Kotz, George Cybenko, Robert S. Gray, Guofei Jiang, Ronald A. Peterson, Martin O. Hofmann, Daria A. Chacon, Kenneth R. Whitebread

Computer Science Technical Reports

Wireless networks are an ideal environment for mobile agents, since their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources that they need to use. Furthermore, client-specific data transformations can be moved across the wireless link and run on a wired gateway server, reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents in a data-filtering application where numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and …

A Formal Semantics For Spki, Jon Howell, David Kotz

Dartmouth Scholarship

We extend the logic and semantics of authorization due to Abadi, Lampson, et al. to support restricted delegation. Our formal model provides a simple interpretation for the variety of constructs in the Simple Public Key Infrastructure (SPKI), and lends intuition about possible extensions. We discuss both extensions that our semantics supports and extensions that it cautions against.

End-To-End Authorization, Jon Howell, David Kotz

Dartmouth Scholarship

Many boundaries impede the flow of authorization information, forcing applications that span those boundaries into hop-by-hop approaches to authorization. We present a unified approach to authorization. Our approach allows applications that span administrative, network, abstraction, and protocol boundaries to understand the end-to-end authority that justifies any given request. The resulting distributed systems are more secure and easier to audit. \par We describe boundaries that can interfere with end-to-end authorization, and outline our unified approach. We describe the system we built and the applications we adapted to use our unified authorization system, and measure its costs. We conclude that our system …

Reducing Mass Degeneracy In Sar By Ms By Stable Isotopic Labeling, Chris Bailey-Kellogg, John J. Kelley Iii, Cliff Stein, Bruce Randall Donald

Dartmouth Scholarship

Mass spectrometry (MS) promises to be an invaluable tool for functional genomics, by supporting low-cost, high-throughput experiments. However, large-scale MS faces the potential problem of mass degeneracy -- indistinguishable masses for multiple biopolymer fragments (e.g. from a limited proteolytic digest). This paper studies the tasks of planning and interpreting MS experiments that use selective isotopic labeling, thereby substantially reducing potential mass degeneracy. Our algorithms support an experimental-computational protocol called Structure-Activity Relation by Mass Spectrometry (SAR by MS), for elucidating the function of protein-DNA and protein-protein complexes. SAR by MS enzymatically cleaves a crosslinked complex and analyzes the resulting mass spectrum …

Performance Analysis Of Mobile Agents For Filtering Data Streams On Wireless Networks, David Kotz, Guofei Jiang, Robert Gray, George Cybenko, Ronald A. Peterson

Dartmouth Scholarship

Wireless networks are an ideal environment for mobile agents, because their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources they need to use. Furthermore, client-specific data transformations can be moved across the wireless link, and run on a wired gateway server, with the goal of reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents to support a data-filtering application, in which numerous wireless clients filter information from a large data stream arriving across the wired network. We …

Trading Risk In Mobile-Agent Computational Markets, Jonathan Bredin, David Kotz, Daniela Rus

Dartmouth Scholarship

Mobile-agent systems allow user programs to autonomously relocate from one host site to another. This autonomy provides a powerful, flexible architecture on which to build distributed applications. The asynchronous, decentralized nature of mobile-agent systems makes them flexible, but also hinders their deployment. We argue that a market-based approach where agents buy computational resources from their hosts solves many problems faced by mobile-agent systems. \par In our earlier work, we propose a policy for allocating general computational priority among agents posed as a competitive game for which we derive a unique computable Nash equilibrium. Here we improve on our earlier approach …

The Complexity Of Planning With Partially-Observable Markov Decision Processes, Martin Mundhenk

Computer Science Technical Reports

This work surveys results on the complexity of planning under uncertainty. The planning model considered is the partially-observable Markov decision process. The general planning problems are, given such a process, (a) to calculate its performance under a given control policy, (b) to find an optimal or approximate optimal control policy, and (c) to decide whether a good policy exists. The complexity of this and related problems depend on a variety of factors, including the observability of the process state, the compactness of the process representation, the type of policy, or even the number of actions relative to the number of …

Personal Radio, John C. Artz Jr

Dartmouth College Undergraduate Theses

With the development of new technologies that allow the broadcast of digital data over radio signals, there are many possibilities for improving upon the traditional radio station model for content delivery. The idea of Personal Radio is a system that tailors content to meet the needs of each individual. Using Global Positioning System (GPS) technology to play location specific content, the listening history to play content an appropriate number of times, and user feedback to learn personal preferences, the Personal Radio provides the listener with the content that is the most useful/interesting to them. This paper will examine the general …

An Economic Cpu-Time Market For D'Agents, Ezra E.K. Cooper

Dartmouth College Undergraduate Theses

A usable and efficient resource-management system has been created for use with D'Agents. The software dynamically negotiates a price rate for CPU time, using the competitive bids of mobile agents that offer currency in return for fast computation. The system allows mobile agents to plan their expenditures across many hosts while minimizing the time needed for their tasks. The ability to price CPU time opens the door for service owners to be compensated for the computation consumed by agents and provides an incentive for servers to allow anonymous agents. We discuss the theoretical background which makes a CPU market system …

Registration Of Images With Dissimilar Contrast Using A Hybrid Method Employing Correlation And Mutual Information, Karolyn A. Abram

Dartmouth College Undergraduate Theses

The problem of fitting one image into another is commonly called "registration." Finding the best possible translation and rotation necessary to align two images is one approach to solving this problem. Registration is a crucial component of many remote sensing and medical image interpretation applications. Image alignment techniques aid in volumetric estimations of complicated structures and allow radiologists to accurately identify changes between sequential images. Radiologists require image alignment capabilities to correct for patient motion and/or content displacement between images. Numerous image registration techniques exist for correcting the alignment problems mentioned above. Unfortunately, most of these techniques, such as Correlation, …

Depth From Flash, David B. Martin

Dartmouth College Undergraduate Theses

Digital camera technology has recently seen substantial improvements in image quality while lower prices have made it affordable to the average consumer. Camera manufacturers, however, are not taking full advantage of this new medium for image capture. By filtering the already digitized image produced by these cameras through on-board image processing algorithms we can dramatically increase the power of digital cameras. For example, according to experts in the photographic industry, most people simply take bad pictures. Classic examples of this phenomenon are photographs taken indoors with a point-and-shoot style camera using its built-in flash. The subjects of these photographs often …

Naming And Sharing Resources Across Administrative Boundaries, Jonathan R. Howell

Dartmouth College Ph.D Dissertations

I tackle the problem of naming and sharing resources across administrative boundaries. Conventional systems manifest the hierarchy of typical administrative structure in the structure of their own mechanism. While natural for communication that follows hierarchical patterns, such systems interfere with naming and sharing that cross administrative boundaries, and therefore cause headaches for both users and administrators. I propose to organize resource naming and security, not around administrative domains, but around the sharing patterns of users.

The dissertation is organized into four main parts. First, I discuss the challenges and tradeoffs involved in naming resources and consider a variety of existing …

Approximation Algorithms For The Minimum Bends Traveling Salesman Problem, Cliff Stein, David P. Wagner

Computer Science Technical Reports

The problem of traversing a set of points in the order that minimizes the total distance traveled (traveling salesman problem) is one of the most famous and well-studied problems in combinatorial optimization. It has many applications, and has been a testbed for many of the must useful ideas in algorithm design and analysis. The usual metric, minimizing the total distance traveled, is an important one, but many other metrics are of interest. In this paper, we introduce the metric of minimizing the number of turns in the tour, given that the input points are in the Euclidean plane. To our …

Performance Analysis Of Mobile Agents For Filtering Data Streams On Wireless Networks, David Kotz, Guofei Jiang, Robert Gray, George Cybenko, Ronald A. Peterson

Computer Science Technical Reports

Wireless networks are an ideal environment for mobile agents, because their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources they need to use. Furthermore, client-specific data transformations can be moved across the wireless link, and run on a wired gateway server, with the goal of reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents to support a data-filtering application, in which numerous wireless clients filter information from a large data stream arriving across the wired network. We …

An Infrastructure For A Mobile-Agent System That Provides Personalized Services To Mobile Devices, Debbie O. Chyi

Dartmouth College Undergraduate Theses

In this paper, we present the design of a mobile-agent system that provides a mobile user with a personalized information retrieval service and we describe the implementation of the infrastructure for such a system. This "Personal Agent System" gathers information from the Internet and uses context-aware mechanisms to manage the information according to a mobile user's needs and preferences. The user's schedule and location are the context indicators in this system. These indicators are critical in ensuring that users obtain only the information they want, receive information in a form that is most useful for viewing on their mobile device, …

A Simulation Of Auroral Absorption, Eric Michael Greenberg

Dartmouth College Undergraduate Theses

HF radio transmissions propagate long distances by reflecting off the ionosphere. At high latitudes radio propagation is strongly affected by the northern lights (aurora borealis), which causes ionization at low altitudes and hence the absorption of radio waves. Models of this process are still in a primitive state. A simulation of radio wave propagation was created in order to test Foppiano and Bradley's empirical model of auroral absorption. The simulation attempts to predict the net absorption of signals at a receiver by simulating a large number of transmitters, even though the exact sources of the signals are unknown. Although the …

The Noesy Jigsaw: Automated Protein Secondary Structure And Main-Chain Assignment From Sparse, Unassigned Nmr Data, Chris Bailey-Kellogg, Alik Widge, John J. Kelley Iii, Marcelo J. Berardi, John H. Bushweller, Bruce Randall Donald

Dartmouth Scholarship

High-throughput, data-directed computational protocols for Structural Genomics (or Proteomics) are required in order to evaluate the protein products of genes for structure and function at rates comparable to current gene-sequencing technology. This paper presents the Jigsaw algorithm, a novel high-throughput, automated approach to protein structure characterization with nuclear magnetic resonance (NMR). Jigsaw consists of two main components: (1) graph-based secondary structure pattern identification in unassigned heteronuclear NMR data, and (2) assignment of spectral peaks by probabilistic alignment of identified secondary structure elements against the primary sequence. Jigsaw's deferment of assignment until after secondary structure identification differs greatly from traditional approaches, …

Restricted Delegation: Seamlessly Spanning Administrative Boundaries, Jon Howell, David Kotz

Dartmouth Scholarship

Historically and currently, access control and authentication is managed through ACLs. Examples include:

• the list of users in /etc/password, the NIS passwd map, or an NT domain

• permissions on Unix files or ACLs on NT objects

• a list of known hosts in .ssh/known hosts

• a list of IP addresses in .rhosts (for rsh) or .htaccess (http)

The limitations of ACLs always cause problems when spanning administrative domains (and often even inside administrative domains). The best example is the inability to express transitive sharing. Alice shares read access to object X with Bob (but not access to …

A Formal Semantics For Spki, Jon Howell, David Kotz

Computer Science Technical Reports

We extend the logic and semantics of authorization due to Abadi, Lampson, et al. to support restricted delegation. Our formal model provides a simple interpretation for the variety of constructs in the Simple Public Key Infrastructure (SPKI), and lends intuition about possible extensions. We discuss both extensions that our semantics supports and extensions that it cautions against.

Landmarks For Absolute Localization, Jon Howell, Keith Kotay

Computer Science Technical Reports

For certain experiments in mobile robotics, it is convenient to eliminate positional estimation error in the interest of analyzing other parts of the experiment. We designed and implemented a simple, accurate scheme for encoding and recovering absolute position information. The encoding is a two-dimensional image printed on the plane of the floor, and the absolute position information is recovered using a downward-looking video camera mounted on a mobile robot.

Mobile Agents: Motivations And State-Of-The-Art Systems, Robert S. Gray, George Cybenko, David Kotz, Daniela Rus

Dartmouth Scholarship

A mobile agent is an executing program that can migrate, at times of its own choosing, from machine to machine in a heterogeneous network. On each machine, the agent interacts with stationary service agents and other resources to accomplish its task. In this chapter, we first make the case for mobile agents, discussing six strengths of mobile agents and the applications that benefit from these strengths. Although none of these strengths are unique to mobile agents, no competing technique shares all six. In other words, a mobile-agent system provides a single general framework in which a wide range of distributed …

An Access-Control Calculus For Spanning Administrative Domains, Jon Howell, David Kotz

Computer Science Technical Reports

In our quest to give users uniform access to resources unimpeded by administrative boundaries, we discovered that we needed transitive sharing among users, with the possibility of restricted access along each sharing link. To achieve that goal, we extend Lampson et al.'s calculus for access control to support restricted delegations. We discuss the advantages of our extension, including the simplification of constructs like ACLs and statement expiration. We also apply our extension to model the Simple Public Key Infrastructure and make suggestions about its future development. Our extended calculus exposes some surprising consequences in such systems that use restricted delegation.

Sar By Ms For Functional Genomics (Structure-Activity Relation By Mass Spectrometry), Bruce Randall Donald, Chris Bailey-Kellogg, John J. Kelley Iii, Cliff Stein

Computer Science Technical Reports

Large-scale functional genomics will require fast, high-throughput experimental techniques, coupled with sophisticated computer algorithms for data analysis and experiment planning. In this paper, we introduce a combined experimental-computational protocol called Structure-Activity Relation by Mass Spectrometry (SAR by MS), which can be used to elucidate the function of protein-DNA or protein-protein complexes. We present algorithms for SAR by MS and analyze their complexity. Carefully-designed Matrix-Assisted Laser Desorption/Ionization Time-Of-Flight (MALDI TOF) and Electrospray Ionization (ESI) assays require only femtomolar samples, take only microseconds per spectrum to record, enjoy a resolution of up to one dalton in $10^6$, and (in the case of …

A Game-Theoretic Formulation Of Multi-Agent Resource Allocation, Jonathan Bredin, Rajiv T. Maheswaran, Cagri Imer, Tamer Basar, David Kotz, Daniela Rus

Computer Science Technical Reports

This paper considers resource allocation in a network with mobile agents competing for computational priority. We formulate this problem as a multi-agent game with the players being agents purchasing service from a common server. We show that there exists a computable Nash equilibrium when agents have perfect information into the future. We simulate a network of hosts and agents using our strategy to show that our resource-allocation mechanism effectively prioritizes agents according to their endowments.