Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

2002

University of Massachusetts Amherst

Articles 1 - 16 of 16

Full-Text Articles in Physical Sciences and Mathematics

Cooperative Leases: Scalable Consistency Maintenance In Content Distribution Networks, Anoop Ninan, Purushottam Kulkarni, Prashant Shenoy, Krithi Ramamritham, Renu Tewari Jan 2002

Cooperative Leases: Scalable Consistency Maintenance In Content Distribution Networks, Anoop Ninan, Purushottam Kulkarni, Prashant Shenoy, Krithi Ramamritham, Renu Tewari

Computer Science Department Faculty Publication Series

In this paper, we argue that cache consistency mechanisms designed for stand-alone proxies do not scale to the large number of proxies in a content distribution network and are not flexible enough to allow consistency guarantees to be tailored to object needs. To meet the twin challenges of scalability and flexibility, we introduce the notion of cooperative consistency along with a mechanism, called cooperative leases, to achieve it. By supporting ∆-consistency semantics and by using a single lease for multiple proxies, cooperative leases allows the notion of leases to be applied in a flexible, scalable manner to CDNs. Further, the …

Go to article

A Secure Routing Protocol For Ad Hoc Networks, Kimaya Sanzgiri, Bridget Dahill, Brian Neil Levine, Clay Shields, Elizabeth M. Belding-Royer Jan 2002

A Secure Routing Protocol For Ad Hoc Networks, Kimaya Sanzgiri, Bridget Dahill, Brian Neil Levine, Clay Shields, Elizabeth M. Belding-Royer

Computer Science Department Faculty Publication Series

Most recent ad hoc network research has focused on providing routing services without considering security. In this paper, we detail security threats against ad hoc routing protocols, specifically examining AODV and DSR. In light of these threats, we identify three different environments with distinct security requirements. We propose a solution to one, the managed-open scenario where no network infrastructure is pre-deployed, but a small amount of prior security coordination is expected. Our protocol, ARAN, is based on certificates and successfully defeats all identified attacks.

Go to article

Data Mining In Social Networks, David Jensen Jan 2002

Data Mining In Social Networks, David Jensen

Computer Science Department Faculty Publication Series

No abstract provided.

Go to article

Coordinated Teams Of Reactive Mobile Platforms, J. Sweeney Jan 2002

Coordinated Teams Of Reactive Mobile Platforms, J. Sweeney

Computer Science Department Faculty Publication Series

This paper presents techniques for exploiting redundancy in teams of mobile robots. In particular, we address tasks involving the kinematic coordination of several commu- nicating robots. Teams are modeled as highly redundant spatial mechanisms for which multi-objective, concurrent controllers are constructed using a generalization of null- space control. The goal is to develop a methodology in which the robustness and error suppression in a control theoretic substrate can be used to preserve critical prop- erties in teams of reactive robots. The resulting “safe” control options can then be explored while guarantee- ing global compliance with system specifications. The proposed architecture …

Go to article

The Predecessor Attack: An Analysis Of A Threat To Anonymous Communications Systems, Matthew K. Wright, Micah Adler, Brian Neil Levine, Clay Sheilds Jan 2002

The Predecessor Attack: An Analysis Of A Threat To Anonymous Communications Systems, Matthew K. Wright, Micah Adler, Brian Neil Levine, Clay Sheilds

Computer Science Department Faculty Publication Series

There have been a number of protocols proposed for anonymous network communication. In this paper we investigate attacks by corrupt group members that degrade the anonymity of each protocol over time. We prove that when a particular initiator continues communication with a particular responder across path reformations, existing protocols are subject to the attack. We use this result to place an upper bound on how long existing protocols, including Crowds, Onion Routing, Hordes, Web Mixes, and DC-Net, can maintain anonymity in the face of the attacks described. This provides a basis for comparing these protocols against each other. Our results …

Go to article

An Unsupervised Algorithm For Segmenting Categorical Timeseries Into Episodes, Paul Cohen, Brent Heeringa, Niall Adams Jan 2002

An Unsupervised Algorithm For Segmenting Categorical Timeseries Into Episodes, Paul Cohen, Brent Heeringa, Niall Adams

Computer Science Department Faculty Publication Series

This paper describes an unsupervised algorithm for segmenting categorical time series into episodes. The Voting-Experts algorithm first collects statistics about the frequency and boundary entropy of ngrams, then passes a window over the series and has two “expert methods” decide where in the window boundaries should be drawn. The algorithm successfully segments text into words in four languages. The algorithm also segments time series of robot sensor data into subsequences that represent episodes in the life of the robot. We claim that Voting-Experts finds meaningful episodes in categorical time series because it exploits two statistical characteristics of meaningful episodes.

Go to article

Maintaining Coherency Of Dynamic Data In Cooperating Repositories, Shetal Shah Jan 2002

Maintaining Coherency Of Dynamic Data In Cooperating Repositories, Shetal Shah

Computer Science Department Faculty Publication Series

In this paper, we consider techniques for disseminating dynamic data—such as stock prices and real-time weather information—from sources to a set of repositories. We focus on the problem of maintaining coherency of dynamic data items in a network of cooperating repositories. We show that cooperation among repositories— where each repository pushes updates of data items to other repositories—helps reduce system-wide communication and computation overheads for coherency maintenance. However, contrary to intuition, we also show that increasing the degree of cooperation beyond a certain point can, in fact, be detrimental to the goal of maintaining coherency at low communication and computational …

Go to article

Optimal Proxy Cache Allocation For Efficient Streaming Media Distribution, Bing Wang, Subhabrata Sen, Micah Adler, Don Towsley Jan 2002

Optimal Proxy Cache Allocation For Efficient Streaming Media Distribution, Bing Wang, Subhabrata Sen, Micah Adler, Don Towsley

Computer Science Department Faculty Publication Series

In this paper, we address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We develop a technique to analytically determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional serverbased reactive transmission schemes such as batching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache …

Go to article

Basic-Block Instruction Scheduling Using Reinforcement Learning And Rollouts, Amy Mcgovern, Eliot Moss, Andrew G. Barto Jan 2002

Basic-Block Instruction Scheduling Using Reinforcement Learning And Rollouts, Amy Mcgovern, Eliot Moss, Andrew G. Barto

Computer Science Department Faculty Publication Series

The execution order of a block of computer instructions on a pipelined machine can make a difference in its running time by a factor of two or more. In order to achieve the best possible speed, compilers use heuristic schedulers appropriate to each specific architecture implementation. However, these heuristic schedulers are time-consuming and expensive to build. We present empirical results using both rollouts and reinforcement learning to construct heuristics for scheduling basic blocks. In simulation, both the rollout scheduler and the reinforcement learning scheduler outperformed a commercial scheduler on several applications.

Go to article

Problems Of Music Information Retrieval In The Real World, Donald Byrd Jan 2002

Problems Of Music Information Retrieval In The Real World, Donald Byrd

Computer Science Department Faculty Publication Series

Although a substantial number of research projects have addressed music information retrieval over the past three decades, the field is still very immature. Few of these projects involve complex (polyphonic) music; methods for evaluation are at a very primitive stage of development; none of the projects tackles the problem of realistically large-scale databases. Many problems to be faced are due to the nature of music itself. Among these are issues in human perception and cognition of music, especially as they concern the recognizability of a musical phrase. This paper considers some of the most fundamental problems in music information retrieval, …

Go to article

Polyphonic Score Retrieval Using Polyphonic Audio Queries: A Harmonic Modeling Approach, Jeremy Pickens Jan 2002

Polyphonic Score Retrieval Using Polyphonic Audio Queries: A Harmonic Modeling Approach, Jeremy Pickens

Computer Science Department Faculty Publication Series

This paper extends the familiar “query by humming” music retrieval framework into the polyphonic realm. As humming in multiple voices is quite difficult, the task is more accurately described as “query by audio example”, onto a collection of scores. To our knowledge, we are the first to use polyphonic audio queries to retrieve from polyphonic symbolic collections. Furthermore, as our results will show, we will not only use an audio query to retrieve a knownitem symbolic piece, but we will use it to retrieve an entire set of realworld composed variations on that piece, also in the symbolic format. The …

Go to article

Estimation Of Congestion Price Using Probabilistic Packet Marking, Micah Adler, Jin-Yi Cai, Jonathan K. Shapiro, Don Towsley Jan 2002

Estimation Of Congestion Price Using Probabilistic Packet Marking, Micah Adler, Jin-Yi Cai, Jonathan K. Shapiro, Don Towsley

Computer Science Department Faculty Publication Series

One key component of recent pricing-based congestion control schemes is an algorithm for probabilistically setting the Explicit Congestion Notification bit at routers so that a receiver can estimate the sum of link congestion prices along a path. We consider two such algorithms—a well-known algorithm called Random Exponential Marking (REM) and a novel algorithm called Random Additive Marking (RAM). We show that if link prices are unbounded, a class of REM-like algorithms are the only ones possible. Unfortunately, REM computes a biased estimate of total price and requires setting a parameter for which no uniformly good choice exists in a network …

Go to article

Explicit Transport Error Notification (Eten) For Error-Prone Wireless And Satellite Networks, Rajesh Krishnan Jan 2002

Explicit Transport Error Notification (Eten) For Error-Prone Wireless And Satellite Networks, Rajesh Krishnan

Computer Science Department Faculty Publication Series

Wireless and satellite networks often have non-negligible packet corruption rates that can significantly degrade TCP performance. This is due to TCP’s assumption that every packet loss is an indication of network congestion (causing TCP to reduce the transmission rate). This problem has received much attention in the literature. In this paper, we take a broad look at the problem of enhancing TCP performance under corruption losses, and include a discussion of the key issues. The main contributions of this paper are: (i) a confirmation of previous studies that show the reduction of TCP performance in the face of corruption loss, …

Go to article

Learning Visual Features To Predict Hand Orientations, Justus H. Piater Jan 2002

Learning Visual Features To Predict Hand Orientations, Justus H. Piater

Computer Science Department Faculty Publication Series

This paper is a preliminary account of current work on a visual system that learns to aid in robotic grasping and manipulation tasks. Localized features are learned of the visual scene that correlate reliably with the orientation of a dextrous robotic hand during haptically guided grasps. On the basis of these features, hand orientations are recommended for future gasping operations. The learning process is instancebased, on-line and incremental, and the interaction between visual and haptic systems is loosely anthropomorphic. It is conjectured that critical spatial information can be learned on the basis of features of visual appearance, without explicit geometric …

Go to article

Harmonic Models For Polyphonic Music Retrieval, Jeremy Pickens Jan 2002

Harmonic Models For Polyphonic Music Retrieval, Jeremy Pickens

Computer Science Department Faculty Publication Series

No abstract provided.

Go to article

Framework For Analyzing Garbage Collection, Matthew Hertz, Neil Immerman, J. Eliot B. Moss Jan 2002

Framework For Analyzing Garbage Collection, Matthew Hertz, Neil Immerman, J. Eliot B. Moss

Computer Science Department Faculty Publication Series

While the design of garbage collection algorithms has come of age, the analysis of these algorithms is still in its infancy. Current analyses are limited to merely documenting costs of individual collector executions; conclusive results, measuring across entire programs, require a theoretical foundation from which proofs can be offered. A theoretical foundation also allows abstract examination of garbage collection, enabling new designs without worrying about implementation details. We propose a theoretical framework for analyzing garbage collection algorithms and show how our framework could compute the efficiency (time cost) of garbage collectors. The central novelty of our proposed framework is its …

Go to article