We introduce a new class of graphs that we call cycletrees. A cycletree includes a basic binary tree and has a unique Hamiltonian cycle. We argue that cycletrees reļ¬ect the communication patterns of several common parallel programming paradigms and can be used in various ļ¬elds…
A robot-building lab and contest was held at the Eleventh National Conference on Artificial Intelligence. Teams of three worked day and night for 72 hours to build tabletop autonomous robots of legos, a small microcontroller board, and sensors. The robots then competed head to head…
In several cryptographic systems, a fixed element g of a group of order N is repeatedly raised to many different powers. In this paper we present a practical method of speeding up such systems, using precomputed values to reduce the number of multiplications needed. In…
We present a method for solving the following problem: Given a set of data points scattered in three dimensions and an initial triangular mesh M0, produce a mesh M, of the same topological type as M0, that fits the data well and has a small…
In this paper, we propose the technique of lazy checkpoint coordination which preserves process autonomy while employing communication-induces checkpoint coordination for bounding rollback propagation. The notion of laziness in introduced to control the coordination frequency and allow a flexible trade-off between the cost of checkpoint…
We describe a simple strictness analyser for purely-functional programs, who how its results are used to improve programs, and provide measurements of the effects of these improvements. These measurements are given both in terms of overall run-time, and in terms of internal operations such as…
Lists are often used as "glue" to connect separate parts of a program together. We propose an automatic technique for improving the efficiency of such programs, by removing many of these intermediate lists, based on a single, simple,Ā local transformation. We have implemented the method in…
The need for automatic speech recognition systems to be robust with respect to changes in their acoustical environment has become more widely appreciated in recent years, as more systems are finding their way into practical applications. Although the issue of environmental robustness has received only…
Reliable messages are delivered in the order they are sent, every message sent is delivered exactly once, and, and an acknowledgement is returned for each delivered message. These properties hold when there is no crash; when there is a crash, messages and acknowledgements may be…
The two-phase commit (2PC) protocol is used to guarantee the serializability of distributed transactions. The message cost of the standard 2PC has led to efforts to optimize the protocol and reduce the number of messages required. The common optimizations require that each cohort of a…
The analysis of charge exchange re-combination spectra represents a very challenging problem due to the presence of many overlapping spectral lines. Conventional approaches are based on iterative least-squares optimisation and suffer from the two difficulties of low speed and the need for a good initial…
This paper examines the use of generational garbage collection techniques for a lazy implementation of a non-strict functional language. Detailed measurements which demonstrate that a generational garbage collector can substantially out-perform non-generational collectors, despite the frequency of write operations in the underlying implementation, are presented.…
