Distributed Backup K-Placement and Applications to Virtual Memory in Wireless Networks

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


The Backup Placement problem in networks in the distributed setting considers a network graph G = (V, E), in which the goal of each vertex v g V is selecting a neighbor, such that the maximum number of vertices in V that select the same vertex is minimized [9]. Previous backup placement algorithms suffer from obliviousness to main factors of 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 attributes of wireless networks, this work addresses a generalized version of the original problem, namely Backup K-Placement, in which each vertex selects K neighbors, for a positive parameter K. Our Backup K-Placement algorithm terminates within just one round. In addition we suggest two complementary algorithms which employ Backup K-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.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفICDCN 2021 - Adjunct Proceedings of the 2021 International Conference on Distributed Computing and Networking
ناشرAssociation for Computing Machinery
عدد الصفحات6
رقم المعيار الدولي للكتب (الإلكتروني)9781450381840
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 5 يناير 2021
الحدث22nd International Conference on Distributed Computing and Networking, ICDCN 2021 - Virtual, Online, اليابان
المدة: ٥ يناير ٢٠٢١٨ يناير ٢٠٢١

سلسلة المنشورات

الاسمACM International Conference Proceeding Series


!!Conference22nd International Conference on Distributed Computing and Networking, ICDCN 2021
المدينةVirtual, Online

ملاحظة ببليوغرافية

Funding Information:
The authors would like to thank Harel Levin for his fruitful comments and extensive evaluation of this work. This work was supported by the Lynn and William Frankel Center for Computer Science, the Open University of Israel’s Research Fund, and ISF grant 724/15.

Publisher Copyright:
© 2021 ACM.


أدرس بدقة موضوعات البحث “Distributed Backup K-Placement and Applications to Virtual Memory in Wireless Networks'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا