Load balanced distributed directories

We present LB-Spiral, a novel distributed directory protocol for shared objects, suitable for large-scale distributed shared memory systems. Each shared object has an owner node that can modify its value. The ownership may change by moving the object from one node to another in response to move requ...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2022-05, Vol.285, p.104700, Article 104700
Main Authors: Rai, Shishir, Sharma, Gokarna, Busch, Costas, Herlihy, Maurice
Format: Article
Language:English
Subjects:
Approximation
Congestion
Directories
Distributed systems
Hierarchical clustering
Load balancing
Processing load
Stretch
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present LB-Spiral, a novel distributed directory protocol for shared objects, suitable for large-scale distributed shared memory systems. Each shared object has an owner node that can modify its value. The ownership may change by moving the object from one node to another in response to move requests. The value of an object can be read by other nodes with lookup requests. The distinctive feature of LB-Spiral is that it balances the processing load on nodes in addition to minimizing the communication cost in general network topologies. In contrast, the existing distributed directory protocols for general network topologies only minimize the communication cost. In particular, LB-Spiral achieves poly-log approximation for both load and communication cost in general networks with respect to the problem parameters. Simulation results show that the established theoretical results translate well in practice.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2021.104700