A Greedy-Based Approach of Fast Transaction Broadcasting in Bitcoin Networks
In this paper,we premeditate the problem of designing a model of information propagation with solving the bifurcation problem of the blockchain system.We define a new diffusion mode with spreading information through the designated seed nodes in the network for the whole system which selects the nodes based on a specific problem.Therefore,we derive a novel influence time minimization(ITM)problem which is that how to choose a group of seed nodes as the source of information dissemination process so that the time required for the entire network to be infected is the smallest.We prove that the problem is NP-hard.A greedy-based algorithm is also proposed.We further propose a provable approximation guarantee for the solution of the algorithm based on the analysis of the monotone submodular function.Experiment results show that the new propagation mode can significantly reduce the propagation time in Bitcoin network compared with the traditional method,which further illustrate that greedy-based algorithm can provide a solution with better performance for ITM problem.Moreover,we find the new program has certain practical significance for improving not only the speed of information propagation but operating efficiency of Bitcoin network.
Bitcoin network information propagation greedy-algorithm approximation guarantee
Haonan Zhang Chen Feng Xinbing Wang
Shanghai Jiao Tong University
国际会议
2019国图灵大会(ACM Turing Celebration conference-China 2019 )
成都
英文
493-497
2019-05-17（万方平台首次上网日期，不代表论文的发表时间）