标题：Fast fault-tolerant sampling via random walk in dynamic networks
作者：Yuan, Yuan ;Li, Feng ;Yu, Dongxiao ;Yu, Jiguo ;Wu, Yu ;Lv, Weifeng ;Cheng, Xiuzhen
作者机构：[Yuan, Yuan ;Li, Feng ;Yu, Dongxiao ;Cheng, Xiuzhen ] School of Computer Science and Technology, Shandong University, China;[Wu, Yu ] Southern Univers 更多
会议名称：39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019
会议日期：7 July 2019 through 9 July 2019
来源：Proceedings - International Conference on Distributed Computing Systems
关键词：Byzantine fault-tolerance; Distributed sampling; Dynamic networks; Random walk
摘要：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(log2 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.