| Abstract (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Consider a distributed network with nodes arranged in a tree, and each node having a local value. We formulate an aggregation problem as the problem of aggregating values (e.g., summing values) from all nodes to the requesting nodes in the presence of writes. The goal is to minimize the total number of messages exchanged. The key challenges are to define a notion of “acceptable ” aggregate values, and to design algorithms with good performance that are guaranteed to produce such values. We formalize the acceptability of aggregate values in terms of certain consistency guarantees similar to traditional consistency models defined in the distributed shared memory literature. The aggregation problem admits a spectrum of solutions that trade off between consistency and performance. The central question is whether there exists an algorithm in this spectrum that provides strong performance and good consistency guarantees. We propose a lease-based aggregation mechanism, and evaluate algorithms based on this mechanism in terms of consistency and performance. With regard to consistency, we generalize the definitions of strict and causal consistency for the aggregation problem. We show that any lease-based aggregation algorithm provides strict consistency in sequential executions, and causal consistency in concurrent executions. With regard to performance, we | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||