期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 67, 期 6, 页码 3623-3644出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3054385
关键词
Load balancing; distributed storage; redundant storage; distributed systems
资金
- National Science Foundation [CIF-1717314]
The study reveals that the load balancing performance in storage schemes of distributed systems exhibits different growth patterns under different conditions, and as the number of storage nodes increases, load balance may increase exponentially or multiplicatively.
To facilitate load balancing, distributed systems store data redundantly. We evaluate the load balancing performance of storage schemes in which each object is stored at d different nodes, and each node stores the same number of objects. In our model, the load offered for the objects is sampled uniformly at random from all the load vectors with a fixed cumulative value. We find that the load balance in a system of n nodes improves multiplicatively with d as long as d = o (log(n)), and improves exponentially once d = Theta(log(n)). We show that the load balance improves in the same way with d when the service choices are created with XOR's of r objects rather than object replicas. In such redundancy schemes, storage overhead is reduced multiplicatively by r. However, recovery of an object requires downloading content from r nodes. At the same time, the load balance increases additively by r. We express the system's load balance in terms of the maximal spacing or maximum of d consecutive spacings between the ordered statistics of uniform random variables. Using this connection and the limit results on the maximal d-spacings, we derive our main results.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据