Fast fault-tolerant sampling via random walk in dynamic networks

Yuan, Yuan1; Li, Feng1; Yu, Dongxiao1; Yu, Jiguo2; Wu, Yu3; Lv, Weifeng4; Cheng, Xiuzhen1

10.1109/ICDCS.2019.00060

2019

1063-6927

978-1-7281-2520-6

39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019

2019-July

536-544

7-10 July 2019

Richardson, TX, United states

10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA

Institute of Electrical and Electronics Engineers Inc.

We study the fundamental problem of fault-tolerant distributed sampling towards uniform probabilistic distribution in dynamic multi-hop wireless networks. Whereas uniform sampling has been extensively studied without concerning fault tolerance, only quite few proposals investigate how the uniform sampling algorithm tolerate Byzantine faults on dynamic networks with very special topologies, e.g., regular graphs with constant node degree. Therefore, designing fault-tolerant uniform sampling algorithms for more general graphs is still an open problem. To this end, we propose a fast and highly fault-tolerate randomized algorithm, such that nearly-uniform sampling is achieved in O(log² n) rounds, while up to O(√n/(polylog(n)⋅ Δ)) Byzantine nodes can be tolerated, where Δ is the maximum degree of the network. Moreover, the proposed algorithm is also communication efficient in the sense that only O(log n) bits need to be exchanged on each link in every round. To show the power of distributed uniform sampling, we apply the proposed algorithm in designing polylogarithmic time distributed algorithms for two typical fundamental issues, i.e., to achieve agreement or data aggregation in Byzantine dynamic networks.
© 2019 IEEE.

Random walk, distributed sampling, Byzantine fault-tolerance, dynamic networks

其他

英语

EI ; CPCI-S

Natural Science Foundation of Shandong Province[] ; National Natural Science Foundation of China[61832012]

Computer Science

Computer Science, Hardware & Architecture ; Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods

WOS:000565234200051

20194607685762

Fault tolerance ; Fault tolerant computer systems ; Graph theory ; Learning algorithms ; Probability distributions ; Random processes

Digital Computers and Systems:722.4 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Probability Theory:922.1

EV Compendex

1.School of Computer Science and Technology, Shandong University, China
2.School of Computer Science and Technology, Qilu University of Technology, Shandong Academy of Sciences, China
3.Southern University of Science and Technology, Shenzhen, China
4.School of Computer Science and Engineering, Beihang Univeresity, China

Yuan, Yuan,Li, Feng,Yu, Dongxiao,et al. Fast fault-tolerant sampling via random walk in dynamic networks[C]. 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA:Institute of Electrical and Electronics Engineers Inc.,2019:536-544.