Analysis of Distributed Token Circulation Algorithm with Faulty Random Number Generator

摘要

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 unidirectional n-node ring networks. In the analysis, we assume there exist nf (0 ≤ n_f ≤ 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 n_f = n-1. (2) Our simulation result shows that the expected convergence time is maximum when n_f = n - 1. (3) We derive the expected token circulation time for each nf (0 ≤ n_f ≤ n - 1).