Towards load balanced distributed transactional memory

Gokarna Sharma, Costas Busch

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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 2 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 2) 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.

Original languageEnglish (US)
Title of host publicationParallel Processing - 18th International Conference, Euro-Par 2012, Proceedings
Pages403-414
Number of pages12
DOIs
StatePublished - 2012
Externally publishedYes
Event18th International Conference on Parallel Processing, Euro-Par 2012 - Rhodes Island, Greece
Duration: Aug 27 2012Aug 31 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7484 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Parallel Processing, Euro-Par 2012
Country/TerritoryGreece
CityRhodes Island
Period8/27/128/31/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Towards load balanced distributed transactional memory'. Together they form a unique fingerprint.

Cite this