This paper presents an in-depth performance analysis and validation of a correlation based stereo vision system being used as part of the ongoing 2003 Mars Exploration Rover flight mission. Our analysis includes the effects of correlation window size, pyramidal image down-sampling, vertical misalignment, focus, maximum disparity, stereo baseline, and range ripples. A key element of validation is to determine the stereo localization error both analytically and experimentally. We study both down-range and cross-range error and verify that while camera calibration inaccuracy contributes to both, stereo correlation error affects only the former. Error contributions of subpixel interpolation, vertical misalignment, and foreshortening on stereo correlation are examined carefully. A novel method using bricks with reflective metrology targets and a mast-mounted stereo camera system enabled experimental measurements of the stereo disparity error. The standard deviation of the down-range disparity error was measured at sigma=0.32 pixel for high-resolution 1024times768 camera images. The result is critical in evaluating accurate rover navigation and instrument placement within given error budgets

The traditional assumption about memory is that a read returns the value written by the most recent write. However, in a shared memory multiprocessor several processes independently and simultaneously submit reads and writes resulting in a partial order of memory operations. In this partial order, the definition of most recent write may be ambiguous. Memory consistency models have been developed to specify what values may be returned by a read given that memory operations may only be partially ordered. Before this work, consistency models were defined independently. Each model followed a set of rules which was separate from the rules of every other model. In our work, we have defined a set of four consistency properties. Any subset of the four properties yields a set of rules which constitute a consistency model. Every consistency model previously described in the literature can be defined based on our four properties. Therefore, we present these properties as a unfied theory of shared memory consistency.Our unified theory provides several benefits. First, we claim that these four properties capture the underlying structure of memory consistency. That is, the goal of memory consistency is to ensure certain declarative properties which can be intuitively understood by a programmer, and hence allow him or her to write a correct program. Our unified theory provides a uniform, formal definition of all previously described consistency models, and in addition some combinations of properties produce new models that have not yet been described. We believe these new models will prove to be useful because they are based on declarative properties which programmers desire to be enforced. Finally, we introduce the idea of selecting a consistency model as an on-line activity. Before our work, a shared memory program would run start to finish under a single consistency model. Our unified theory allows the consistency model to change as the program runs while maintaining a consistent definition of what values may be returned by each read.

We present a family of epidemic algorithms for maintaining replicated database systems. The algorithms are based on the causal delivery of log records where each record corresponds to one transaction instead of one operation. The first algorithm in this family is a pessimistic protocol that ensures serializability and guarantees strict executions. Since we expect the epidemic algorithms to be used in environments with low probability of conflicts among transactions, we develop a variant of the pessimistic algorithm which is optimistic in that transactions commit as soon as they terminate locally and inconsistencies are detected asynchronously as the effects of committed transactions propagate through the system. The last member of the family of epidemic algorithms is pessimistic and uses voting with quorums to resolve conflicts and improve transaction response time. A simulation study evaluates the performance of the protocols.

A memory consistency model specifies certain aspects of the behavior of a memory system. Stronger consistency models are easier for programmers to use, but provide less flexibility for optimizing the memory implementation. More relaxed consistency models are just the opposite. The goal of our work is to develop a framework that captures the relationships among existing models, and maps the territory of possible models that have not yet been discovered. This work is based on the idea of orthogonal consistency properties. hypothesize that all consistency models can be represented by different combinations of a few primitive properties. The work comes from examining the PRAM, cache, processor, and causal consistency models. Processor is a combination of PRAM and cache, and causal is a combination of PRAM plus an additional requirement. These factors suggest an underlying structure to the models.