Towards load balanced distributed transactional memory

We consider the problem of implementing transactional memory in d-dimensional mesh networks. We present and analyze MultiBend, a novel load balanced directory-based protocol, which is designed for the data-flow distributed implementation of software transactional memory. It supports three basic operations, publish, lookup, and move, on a shared object. A pleasing aspect of MultiBend is that it is load balanced (minimizes maximum node and edge utilization) which is achieved by using paths of multiple bends in the mesh. This protocol guarantees an O(d ² log n) approximation for the load and also for the distance stretch of move requests, where n is the number of nodes in the network. For fixed d, both the load and the move stretch are optimal within a constant and a loglog factor, respectively. It also guarantees O(d ²) approximation for lookup requests which is optimal within a constant factor for fixed d. To the best of our knowledge, this is the first distributed directory protocol that is load balanced.