SSS Abstracts  Fall 2003

Presented by Jernej Barbic,

Mesh generation is an important area of computational geometry, with many applications to engineering and computer graphics. Over the last 20 years, a lot of research has been done on the family of Delaunay-based meshes, which now have many real-world users worldwide. This talk aims at answering the following questions: What is a mesh and how are meshes used? What are the requirements for a good meshing algorithm? What are some common solutions? How can Delaunay triangulations help in producing a good mesh?

This talk is in partial fulfillment of the speaking requirement.

Deployment Experience with an Overlay-based Internet Broadcasting System

Friday, October 3^rd, 2003 from 12-1 pm in NSH 1507.

Presented by Yang-hua Chu,

Overlay multicast has been proposed as an alternate architecture for enabling group communication applications over the Internet. In contrast with IP Multicast, overlay multicast implements all multicast functionality at end systems. While an overlay-based solution promises quick deployment, the potential concern is performance, as end systems are unreliable, heterogeneous, and often with limited bandwidth.

In the past few years, researchers have proposed solutions to address these concerns, and evaluated their solutions through simulation and Internet testbeds. However, there is limited experience from real deployment. We ask the questions: Is overlay multicast mature enough to be practically deployable? If not, what are the research challenges?

In this talk, we report our early experiences in building and deploying an operational Internet broadcast system based on overlay multicast. We conducted several broadcast events including distinguished lectures and technical conferences. I summarize our experience and the lessons learned.

This talk is in partial fulfillment of the speaking requirement.

Analysis of cycle stealing with switching cost

Friday, October 24^th, 2003 from 12-1 pm in NSH 1507.

Presented by Takayuki Osogami,

Since the invention of networks of workstations, systems designers have touted the benefits of allowing a user to take advantage of machines other than her own, at times when those machines are idle. This notion is often referred to as cycle stealing. Cycle stealing allows a user, Betty, with multiple jobs to offload one of her jobs to the machine of a different user, Dan, if Dan's machine is idle, giving Betty two machines to process her jobs. When Dan's workload resumes, Betty must return to using only her own machine. Although cycle stealing provides obvious benefits to Betty (the beneficiary), these benefits come at some switching cost to Dan (the donor).

We analyze the mean response time for the donor and beneficiary jobs via a new technique that allows us to reduce the dimensionality of the state space in Markov chains. Our analysis is approximate, but can be made as accurate as desired, and is validated via simulation. Results of the analysis illuminate several interesting principles with respect to the general benefits of cycle stealing and the design of cycle stealing policies.

This talk is in partial fulfillment of the speaking requirement.

Two-level Counterexample Guided Abstraction Refinement

Friday, October 31^st, 2003 from 12-1 pm in NSH 1507.

Presented by Sagar Chaki,

Joint work with: Edmund Clarke, Joel Ouaknine, Karen Yorav.

The state-space explosion problem remains a major practical hurdle towards verifying complex concurrent systems. Two paradigms have been traditionally used to attempt to overcome this obstacle: (i) abstraction and (ii) compositional reasoning. Abstraction involves the generation of simpler models by focusing on the characteristics of a system that are essential for checking the property of interest. Compositional reasoning allows decomposing the verification of a large complex system into smaller and simpler verification tasks for the system components. However, in order to be practicable for real-life systems, both these techniques must be applied automatically, or at least semi-automatically. In this context, an approach called counterexample guided abstraction refinement (CEGAR) has been quite successful for verifying safety property on sequential C programs of industrial complexity. In this talk I will describe some of our research aimed at using CEGAR to verify safety properties for concurrent message-passing C programs. Our approach uses a two-level abstraction scheme and compositionality to reduce the size of state-spaces being handled. We have implemented these ideas in our tool, called MAGIC, and obtained encouraging results. Time permitting, I will describe some extensions of our approach for verifying liveness and branching time properties in addition to safety.

This talk is in partial fulfillment of the speaking requirement.

Expressive Negotiation over Donations to Charities

Friday, November 7^th, 2003 from 12-1 pm in NSH 1507.

Presented by Vincent Conitzer,

When donating money to a (say, charitable) cause, it is possible to use the contemplated donation as negotiating material, to induce other parties interested in the charity to donate more. Such negotiation is usually done in terms of matching offers, where one party promises to pay a certain amount if others pay a certain amount. However, in their current form, matching offers allow for only limited negotiation. This causes economic loss: it may happen that an arrangement that would have made all parties (donors as well as charities) better off cannot be expressed in terms of matching offers, and will therefore not occur.

In this talk, I will propose a generalization of matching offers. I will define the bidding language in which offers can be expressed; define the associated clearing problem (deciding who pays what to which charity), and discuss its computational complexity; discuss the mechanism design problem (motivating donors to report their preferences accurately); and demonstrate our initial web-based implementation.

This talk is in partial fulfillment of the speaking requirement.

Tactics-Based Remote Execution for Mobile Computing

Friday, November 14^th, 2003 from 12-1 pm in NSH 1507.

Presented by Rajesh Balan,

Remote execution can transform the puniest mobile device into a computing giant able to run resource-intensive applications such as natural language translation, speech recognition, face recognition, and augmented reality. However, easily partitioning these applications for remote execution while retaining application-specific information has proven to be a difficult challenge. In this talk, we show that automated dynamic re-partitioning of mobile applications can be reconciled with the need to exploit application-specific knowledge. We show that the useful knowledge about an application relevant to remote execution can be captured in a compact declarative form called tactics. Tactics capture the full range of meaningful partitions of an application and are very small relative to code size. We will present the design of a tactics-based remote execution system, Chroma, that performs comparably to a runtime system that makes perfect partitioning decisions. Furthermore, we show that Chroma can automatically use extra resources in an over-provisioned environment to improve application performance.

This talk is in partial fulfillment of the speaking requirement.

Efficient Planning in Cost-Paired Markov Decision Process Games

Friday, November 21^st, 2003 from 12-1 pm in NSH 1507.

Presented by Brendan McMahan,

Joint work with Geoffrey Gordon and Avrim Blum.

Markov Decision Processes (MDPs) are a general framework for expressing planning problems where some actions have uncertain or probabilistic outcomes. They can be used to model a wide range of planning problems, and efficient planning algorithms exist for both general MDPs and important special cases.

This talk will provide a brief overview of planning in MDPs, and will then introduce new techniques that extend the MDP model to an adversarial setting. In particular, we investigate methods for planning in a MDP where the cost function is chosen by an adversary after we fix our policy. As a running example, we consider a robot path planning problem where costs are influenced by sensors that an adversary places in the environment. We first present two algorithms for the case where the adversary must pick this cost vector from a small fixed set of cost vectors. We then extend one of these algorithms to a two-player game where each player selects a policy in an MDP, and the cost vector in each MDP depends on the policy selected by the other player. These algorithms are efficient in practice (orders of magnitude faster than more naive planners), largely because they capitalize on the existence of fast planning algorithms for traditional MDPs.

This talk is in partial fulfillment of the speaking requirement.

Closet Metric Problems

Friday, December 5^th, 2003 from 12-1 pm in NSH 1507.

Presented by Kedar Dhamdhere,

Closest metric problems arise in many areas. An example includes, finding evolutionary tree in computational biology.

In this talk, we give a brief overview of problems of finding closest metrics. We focus on the problem of finding closest line metric. This problem arises is estimating positions of gene markers on DNA. We give a log(n)-approximation algorithm for finding the closest line metric under L_p norm. This algorithm is based on a new technique. This technique extends to various closest metric problems.

This talk is in partial fulfillment of the speaking requirement.

Web contact: sss+www@cs