论文标题
分布式k回复位置和对现实世界无线网络中虚拟内存的应用
Distributed K-Backup Placement and Applications to Virtual Memory in Real-World Wireless Networks
论文作者
论文摘要
$ \ MATHCAL {COODEST} $分布式设置的网络中的备份位置问题考虑了网络图$ g =（v，e）$，其中每个顶点$ v \ in V $中的每个顶点的目标是选择一个邻居，因此选择了相同顶点的$ V $中最大的V $中的顶点数量最小。以前的备份位置算法遭受了现实世界异质无线网络的主要因素的遗忘。具体而言，不考虑节点内存和存储能力，也没有提及节点具有不同能量容量的情况，因此可以随时离开（或加入）网络。这些参数在无线网络中密切相关，因为网络的不同部分的负载可能很大，因此需要更多的通信，能量，内存和存储。为了适合无线网络的实际属性，此工作解决了原始问题的广义版本，即$ k $ backup放置，其中每个顶点选择$ k $ knighbors，用于正面参数$ k $。我们的$ k $ - 背部放置算法仅在一轮之内就终止了。此外，我们建议使用两种互补算法，它们采用$ k $ backup-placement来获得无线网络的有效虚拟内存方案。第一种算法将每个节点的内存分为许多小部分。每个顶点都被分配了其大部分邻居的记忆。因此，获得了更多的更多顶点的记忆能力，但分散了很多。第二个算法需要更大的圆形复杂性，但为每个顶点产生更大的虚拟记忆而没有任何碎片化。
The Backup Placement problem in networks in the $\mathcal{CONGEST}$ distributed setting considers a network graph $G = (V,E)$, in which the goal of each vertex $v \in V$ is selecting a neighbor, such that the maximum number of vertices in $V$ that select the same vertex is minimized [Halldorsson et al., 2015]. Previous backup placement algorithms suffer from obliviousness to main factors of real-world heterogeneous wireless network. Specifically, there is no consideration of the nodes memory and storage capacities, and no reference to a case in which nodes have different energy capacity, and thus can leave (or join) the network at any time. These parameters are strongly correlated in wireless networks, as the load on different parts of the network can differ greatly, thus requiring more communication, energy, memory and storage. In order to fit the real-world attributes of wireless networks, this work addresses a generalized version of the original problem, namely $K$-Backup Placement, in which each vertex selects $K$ neighbors, for a positive parameter $K$. Our $K$-Backup Placement algorithm terminates within just one round. In addition we suggest two complementary algorithms which employ $K$-Backup-Placement to obtain efficient virtual memory schemes for wireless networks. The first algorithm divides the memory of each node to many small parts. Each vertex is assigned the memories of a large subset of its neighbors. Thus more memory capacity for more vertices is gained, but with much fragmentation. The second algorithm requires greater round-complexity, but produces larger virtual memory for each vertex without any fragmentation.
