Premium
On the number of active nodes in a multicomputer system
Author(s) -
Barak Am,
Drezner Zvi,
Gurevich Yuri
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160304
Subject(s) - computer science , node (physics) , probabilistic logic , routing (electronic design automation) , distributed computing , fraction (chemistry) , active networking , computer network , artificial intelligence , chemistry , structural engineering , organic chemistry , engineering
In this article we develop probabilistic algorithms for estimating the number of active nodes in a multicomputer system which consists of independent computers that are interconnected by a communication network. The algorithms are based on routine exchange of messages among the nodes of the multicomputer, using random routing. We show that each active node can find an ϵ‐estimate of the fraction λ of active nodes in the system in time that depends only on ϵ and λ. The underlying approach can be used for finding various global properties of distributed systems with decentralized control.