| dc.description.abstract | Since computers are widespread and interconnected, the study of computing has expanded
to encompass problems arising from concurrency and the need for coordinated effort between
different computing entities. Essential among those problems is providing efficient means for
multiple, distributed processes to operate on the same data, while guaranteeing that the results of
their actions make sense and are useful. In this dissertation, we explore a method of improving the
efficiency of operations on shared data.
The method we explore in this work is relaxation of a data type. Intuitively, relaxation consists
of adding a limited amount of non-determinism to the specification of a data type. This allows
multiple legal actions from a particular state. In some cases, we can associate these different actions
with concurrent operations on shared data, allowing multiple processes to act without coordinating
at that step. Since communication between different physical locations is relatively expensive
reducing the need for coordinating communication can significantly increase the rate at which
processes can execute operations on shared data.
After giving practical definitions of a few specific relaxations from the literature, we proceed in
three steps. First, we provide implementations and analysis of algorithms for FIFO queues under
several of these relaxations, showing the performance benefits relaxation provides. We then analyze
the computational power of relaxed queues, to understand what we have given up to achieve
improved performance. Finally, we compare the relaxation model to the study of weakened consistency conditions, a common approach in the literature. We show a partial correspondence between the models, allowing us to use existing tools to analyze relaxations.
To conclude, we step away from relaxations and provide a set of heuristics for determining
the consensus number of a data type, which is a measure of its computational strength. While
it is an undecidable problem in general, in specific cases our tools may allow system designers
to recognize whether or not a specific type provides the strength they need for their particular
distributed application. | en |
