Analysis of distributed token circulation algorithm with faulty random number generator
Analysis of distributed token circulation algorithm with faulty random number generator
复制标题
随机数生成器故障的分布式代币流通算法分析
DOI：
10.1142/s0129626414500029
复制
发表时间：
2014
影响因子：
0.4
通讯作者：
and Toshimitsu Masuzawa
中科院分区：
文献类型：
--
作者：
Shinji Kawai;Fukuhito Ooshita;Hirotsugu Kakugawa;and Toshimitsu Masuzawa
随机化是一种提高分布式计算效率和可计算性的技术。本文研究了分布式计算对随机数生成器故障的容错问题。我们引入了RNG（随机数生成器）故障作为一类新的故障；随机数生成器在rng故障的进程上确定地输出相同的数字。本文首次考虑了分布式计算中随机性的缺陷。我们通过观察rng故障对单向节点环网络上自稳定令牌循环算法性能的影响来研究随机化的作用。在分析中，我们假设存在nf（0≤nf≤n−1）个rng故障节点，并且每个rng故障节点总是向下一个节点传递一个令牌。我们的结果有三个方面：(1)我们导出了在nf= n−1的情况下期望收敛时间的上界。(2)仿真结果表明，当nf= n−1时，期望收敛时间最大。(3)推导出每个nf（0≤nf≤n−1）的期望令牌循环时间。
Randomization is a technique to improve efficiency and computability of distributed computing. In this paper, we investigate fault tolerance of distributed computing against faults of random number generators. We introduce an RNG (Random Number Generator)-fault as a new class of faults; a random number generator on an RNG-faulty process outputs the same number deterministically. This paper is the first work that considers faults of randomness in distributed computing.We investigate the role of randomization by observing the impact of RNG-faults on performance of a self-stabilizing token circulation algorithm on unidirectionaln-node ring networks. In the analysis, we assume there exist nf(0 ≤ nf≤ n−1) RNG-faulty nodes and each RNG-faulty node always transfers a token to the next node. Our results are threefold: (1) We derive the upper bound on the expected convergence time in the case of nf= n − 1. (2) Our simulation result shows that the expected convergence time is maximum when nf= n − 1. (3) We derive the expected token circulation time for each nf(0 ≤ nf≤ n − 1).