Chill Out: A Study on the Relationship Between Relaxation and Accuracy Loss and the Implication Thereof

Linearization is the main paradigm by which we implement distributed objects, though it incurs a high synchronization cost. Relaxation can mitigate the synchronization cost of a distributed object. Currently, we lack methods for determining which applications would most benefit from relaxation. We investigate a specific case of relaxation to clarity to this problem. We examine a relaxed priority queue used in Dijkstra's solution to the single-source shortest path problem. We focus on percent correctness of the resulting paths as a measure of accuracy, examining the trend of accuracy loss with a standard benchmarking problem. We find that accuracy loss is not directly correlated with level of relaxation, implying further study is warranted in order to quantify the relationship between relaxation and accuracy loss so as to be more useful in application