Technical Reports

The ICICS/CS Reading Room

2003 UBC CS Technical Report Abstracts

TR-2003-01 Giving a Compass to a Robot - Probabilistic Techniques for Simultaneous Localisation and Map Building (SLAM) in Mobile Robotics, December 20, 2002 R. W. v. L. Wenzel, 6 pages

An important feature of an autonomous mobile robotic system is its ability to accurately localize itself while simultaneously constructing a map of its environment. This problem is complicated because of its chicken-and-egg nature: in order to determine its location the robot needs to know the map, and in order to build an accurate map the robot must know where it is. In addition, a robust system must account for the noise in odometry and sensor readings. This project explores the probabilistic methods of solving the SLAM problem using Rao-Blackwellisation.

TR-2003-02 The Boolean Functions Computed by Random Boolean Formulas OR, January 30, 2003 Alex Brodsky and Nicholas Pippenger

How to Grow the Right Function probabilistic amplification, random Boolean functions were used for constructing reliable networks from unreliable components, and deriving complexity bounds of various classes of functions. Hence, determining the initial conditions for such processes is an important and challenging problem. In this paper we characterize growth processes by their initial conditions and derive conditions under which results such as Valiant's (Valiant, 1984) hold. First, we completely characterize growth processes that use linear connectives. Second, by extending Savick\'y's (Savick\'y, 1990) analysis, via ``Restriction Lemmas'', we characterize growth processes that use monotone connectives, and show that our technique is applicable to growth processes that use other connectives as well.

TR-2003-03 On the Complexity of Buffer Allocation in Message Passing Systems, January 30, 2003 Alex Brodsky, Jan B. Pedersen and Alan Wagner, 35 pages

Message passing programs commonly use buffers to avoid unnecessary synchronizations and to improve performance by overlapping communication with computation. Unfortunately, using buffers makes the program no longer portable, potentially unable to complete on systems without a sufficient number of buffers. Effective buffer use entails that the minimum number needed for a safe execution be allocated. We explore a variety of problems related to buffer allocation for safe and efficient execution of message passing programs. We show that determining the minimum number of buffers or verifying a buffer assignment are intractable problems. However, we give a polynomial time algorithm to determine the minimum number of buffers needed to allow for asynchronous execution. We extend these results to several different buffering schemes, which in some cases make the problems tractable.

TR-2003-04 Flexible and Local Isosurfaces - Using Topology for Exploratory Visualization, February 10, 2003 Hamish Carr and Jack Snoeyink, 18 pages

The contour tree is a topological abstraction of a scalar field, used to accelerate isosurface extraction and to represent the topology of the scalar field visually. We simplify the minimal seed sets of van Kreveld et al. by extracting isosurface seeds directly from the contour tree at run-time, and by guaranteeing that no redundant seeds are generated. We then extend the contour spectrum of Bajaj et al. as an interface for flexible isosurfaces, in which individual contour surfaces with different isovalues can be displayed, manipulated and annotated. Finally, we show that the largest contour segmentation of Manders et al., in which separate surfaces are generated for each local maximum of the field, is in fact a special case of the flexible isosurface.

TR-2003-05 Bayesian Models for Massive Multimedia Databases: A New Frontier, February 18, 2003 Nando de Freitas, Eric Brochu, Kobus Barnard, Pinar Duygulu and David Forsyth, 12 pages

Modelling the increasing number of digital databases (the web, photo-libraries, music collections, news archives, medical databases) is one of the greatest challenges of statisticians in the new century. Despite the large amounts of data, the models are so large that they motivate the use of Bayesian models. In particular, the Bayesian perspective allows us to perform automatic regularisation to obtain sparse and coherent models. It also enables us to encode a priori knowledge, such as word, music and image preferences. The learned models can be used for browsing digital databases, information retrieval with image, music and/or text queries, image annotation (adding words to an image), text illustration (adding images to a text), and object recognition.

TR-2003-06 A Study of Program Evolution Involving Scattered Concerns, March 26, 2003 Martin P Robillard and Gail C. Murphy, 11 pages

Before making a change to a system, software developers typically explore the source code to find and understand the subset relevant to their task. Software changes often involve code addressing different conceptually-related segments of the implementation (concerns), which can be scattered across multiple modules. These scattered concerns make it difficult to reason about the code relevant to a change. We carried out a study to investigate how developers discover and manage scattered concerns during a software evolution task, and the role that structural queries play during the investigation. The task we studied consists of a developer adding a feature to a 65kloc Java code base. The study involved eight subjects: four who were not briefed about scattered concerns, and four who were trained to use a concern-oriented investigation tool. Analysis of the navigation among the different program elements examined by the subjects during the task shows evidence that, independent of whether concern-oriented tool support was available, the most successful subjects focused on specific concerns when planning their task, and used a high proportion of structural queries to investigate the code. In addition to the study results, this paper introduces two novel analyses: navigation graphs, which support the analysis of a subject's behavior when investigating source code, and variant analysis, which is used for evaluating the results of a program evolution task.

TR-2003-09 Motion Doodles: : A Sketching Interface for Character Animation, April 17, 2003 Matthew Thorne, David Burke and Michiel van de Panne, 11 pages

We present a novel system which allows a character to be sketched and animated within a minute and with a limited amount of training. The process involves two steps. First, a character is sketched by drawing the links representing the torso, head, arms, and legs. An articulated skeleton and mass distribution is then inferred from the sketched links. Further annotations can be added to the skeleton sketch and are automatically bound to the underlying links. Second, the desired animated motion is sketched using a series of arcs and loops that are interpreted as an appropriate sequence of steps, leaps, jumps, and flips. The motion synthesis process then ensures that the animated motion mirrors key features extracted from the input sketch. For example, the height, distance, and timing of an arc that represents a jump are all reflected in the resulting animated motion. The current prototype allows for walking, walking with a stomp, tip-toeing, leaps, jumps, in-place stomps, front flips, and back flips, including the backwards versions of all these motions.

TR-2003-10 MayaJala: A Framework for Multiparty Communication, September 12, 2003 Chamath Keppitiyagama and Norman C. Hutchinson, 12 pages

The availability of higher bandwidth at the end-points has resulted in the proliferation of distributed applications with diverse communication needs. Programmers have to express the communication needs of such applications in terms of a set of point-to-point communication primitives. Such an approach has several disadvantages. These include the increase in development time, the difficulty in getting the complex communication structure right and the redundancy in several developers doing the same work to achieve the same communication pattern. If common communication patterns are available as well defined communication types these problems can be avoided. A similar approach has already been used in the parallel programming domain; message passing parallel programs use collective communication primitives to express communication patterns instead of composing them with point-to-point communication primitives. This is not the case for distributed programs in general. In this paper we discuss different multiparty communication types and also a framework to implement and make them available to distributed programs.

TR-2003-11 Mammoth: A Peer-to-Peer File System, June 14, 2002 Dmitry Brodsky, Shihao Gong, Alex Brodsky, Michael J. Feeley and Norman C. Hutchinson, 15 pages

Peer-to-peer storage systems organize a collection of symmetric nodes to store data without the use of centralized data structures or operations. As a result, they can scale to many thousands of nodes and can be formed directly by clients. This paper describes the design and implementation Mammoth, which implements a traditional UNIX-like hierarchical file system in a peer-to-peer fashion. Each Mammoth node stores a potentially arbitrary collection of directories and files that may be replicated on multiple nodes. The only thing that links these nodes together is that each metadata object encodes the network addresses of the nodes that store it. Data is replicated by a background process whose operation is simplified by the fact that files are stored as journals of immutable versions. An optimistic replication technique is used to allow nodes to read and write whatever version of data they can access, while also ensuring consistency when nodes are connected. In the event of temporary failure, eventual consistency is achieved by ensuring that every replica of a directory or file metadata object receives all updates to the object, irrespective of delivery order. While an update is being propagated every node that receives it cooperates to ensure that the update is delivered, even if the original sender fails. Our prototype is implemented as a user-level NFS server. Its performance is comparable to a standard NFS server and it will be publicly available soon.

TR-2003-12 RAPPID SYNCHRONIZATION, September 08, 2003 Satyajit Chakrabarti and Sukanta Pramanik, 8 pages

This paper proposes a solution to the synchronization issue in RAPPID that has prevented it from being used in synchronous processors like the Pentium family of processors, in spite of its higher average case throughput. Our first approach explores the possibility of using an early count of the number of instructions pending in the decoder. If the availability of these instructions can be predicted within a bounded time then the execution unit can carry on upto that point without error. Our second approach moves the possibility of metastability from the data path to the control path. The data is placed in the path before the control signal which ensures a stable data when the control is stable or metastable. If the metastability in control signal is not resolved within a single clock-cycle it is re-sampled and the re-sampled signal overwrites the previous signal, thereby ensuring a worst case latency of one clock-cycle.

TR-2003-13 Multiparty Communication Types for Distributed Applications, September 25, 2003 Chamath Keppitiyagama and Norman C. Hutchinson, 6 pages

Communication is an important and complex component of distributed applications. It requires considerable effort and expertise to implement communication patterns in distributed applications. Therefore, it is prudent to separate the two tasks of implementing the communication and implementing the application's main functionality which needs the communication. Traditionally this separation is achieved through a standard interface. A good example is the Message Passing Interface (MPI) for message-passing parallel programs. It takes considerable experience, effort and general agreement in the community to define such an interface. However, a standard interface is not flexible enough for the rapidly changing requirements of distributed applications. We propose that the separation of communication and application specific functionality should be achieved through the abstraction of communication types. In this paper we present a communication type system for multiparty communication. The type system can be used to express the communication requirements of an application, describe an implementation of a communication type, and make a match between these two. Our type system is only a single component of a framework for multiparty communication that we are developing.

TR-2003-14 Implementing a Connected Dominating Set Algorithm for Clustering Mobile Ad Hoc Networks, October 20, 2003 Kan Cai, Suprio Ray, Michael J. Feeley and Norman C. Hutchinson, 14 pages

Advances in network technology have tremendously changed the way people communicate. The relatively recent introduction of wireless networking technology has the potential to play an even more influential role in our daily lives. However, the nature of wireless technology makes it a more difficult platform on which to build useful systems. Some particularly troubling aspects of wireless networks include high mobility, frequent failures, limited power, and low bandwidth. A core component of a networked system is its routing protocol. Several ad-hoc wireless routing protocols have been proposed which depend on a flood-and-cache design. However, these algorithms suffer from scalability problems whenever the hit rate in the cache is low, such as when most connections are short-lived. This paper describes the design and implementation of a Deployable Connected Dominating Set (DCDS) algorithm. As in other CDS algorithms, DCDS provides a scalable routing scheme by constructing and maintaining a backbone across the network. To make our CDS algorithm truly deployable in an IEEE 802.11 network, we eliminate three unrealistic assumptions on which previous designs are based: reliable broadcast, accurate neighbouring information, and a static setup phase. We have implemented the DCDS algorithm and simulated it using Glomosim. The evaluations show that DCDS has significantly better scalability than AODV. We also show that our algorithm can maintain an effective backbone which appropriately balances setup time and size.

TR-2003-15 Policy Driven Replication, October 7, 2003 Dmitry Brodsky, Alex Brodsky, Michael J. Feeley and Norman C. Hutchinson, 14 pages

The increasingly commodity nature of storage and our insatiable tendency to produce, store, and use large amounts of data exacerbates the problem of ensuring data survivability. The advent of large robust networks has gained the idea of replicating data on remote hosts wide-spread acceptance. Unfortunately, the growth of network bandwidth is far outstripped by both the growth of both storage capacity~\cite{patterson03jimgray} and our ability to fill it. Thus, most replication systems, which traditionally replicate data blindly, fail under the onslaught of this lopsided mismatch. We propose a Policy Driven Replication (PDR) system that prioritizes the replication of data, based on user-defined policies that specify which data is to be protected, from which failures, and to what extent. By prioritizing which data is replicated, our system conserves limited resources and ensures that data which is deemed most important to and by the user is protected from failures that are deemed most likely to occur.

TR-2003-16 Apostle: A Simple Incremental Weaver for a Dynamic Aspect Language, October 22, 2003 Brian de Alwis and Gregor Kiczales, 9 pages

This paper describes the incremental weaving implementation of Apostle, an aspect-oriented language extension to Smalltalk modelled on AspectJ. Apostle implements incremental weaving in order to make aspect-oriented programming (AOP) a natural extension of the incremental edit-run-debug cycle of Smalltalk environments. The paper analyzes build dependencies for aspect declarations, and shows that two simple dependency table structures are sufficient to produce reasonable re-weaving efficiency. The resulting incremental weaver provides re-weaving performance proportional to the change in the program.

TR-2003-17 Energy Efficient Peer-to-Peer Storage, November 10, 2003 Geoffrey Lefebvre and Michael J. Feeley, 6 pages

This paper describes key issues for building an energy efficient peer-to-peer (P2P) storage system. Current P2P systems waste large amounts of energy because of the false assumption that participating nodes' resources are free. Environmentally and economically, this is not true. Instead this paper argues that idle nodes in a P2P system should sleep to save energy. We derive an upper bound on the time an idle node can sleep without affecting the durability of the data stored in the system. This upper bound is parameterized by the replication factor and expected failure rates. We also outline a protocol for failure detection in an environment where only a small fraction of the nodes are alive at any time.

TR-2003-18 A Bayesian Network Model of a Collaborative Interactive Tabletop Display, December 09, 2003 Mark S. Hancock, 8 pages

In this paper, I explore the use of Bayesian Networks to model the use of an interactive tabletop display in a collaborative environment. Specifically, this model is intended to extract user-profile information for each user including their location at the table as well as their handedness. The network uses input from a six-degrees-of-freedom stylus device as its source of observable information. This paper introduces a first attempt at a model to support these requirements as well as a preliminary evaluation of the model. Results show that the model is sufficiently accurate to obtain a user profile in real time in a Tabletop Display environment.

TR-2003-20 Aspect Weaving with C# and .NET, December 19, 2003 Michael A. Blackstock, 9 pages

Since current object oriented programming languages donít have existing support for aspects, aspects are often supported through language extensions. Another approach is to use the existing language to encapsulate aspect behaviors, and provide an additional language to express cross cutting statements. Finally, other systems including the one described in this paper use features of the existing language to specify aspect behavior and cross cutting. This paper presents a prototype weaver called AOP.NET that demonstrates the feasibility of supporting aspect oriented programming in C# without the need for language extensions, or a cross cutting statement file. All of the information related to supporting AOP including the cross cutting statements is contained in the aspect declaration. The cross cutting statements are expressed using a language feature called attributes which are used to annotate methods, fields and classes with meta data in languages targeting the Common Language Runtime (CLR) such as C#. Since attributes are supported in all CLR languages it should be possible to maintain .NET language independence with this approach. AOP.NET demonstrates the feasibility of static and transparent dynamic weaving in .NET. Unlike other .NET dynamic weavers, no changes are required to the source code of clients of functional components for dynamic weaving, the same weaving engine is used in both a static tool and dynamic weaving run time host, and it is implemented completely in C#.

If you have any questions or comments regarding this page please send mail to