Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2007-08-28
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
A Black Hole is an harmful host in a network that destroys incoming agents without leaving any trace of such event. The problem of locating the black hole in a network through a team of agent coordinated by a common protocol is usually referred in literature as the Black Hole Search problem (or BHS for brevity) and it is a consolidated research topic in the area of distributed algorithms. The aim of this paper is to extend the results for BHS by considering more general (and hence harder) classes of dangerous host. In particular we introduce rB-hole as a probabilistic generalization of the Black Hole, in which the destruction of an incoming agent is a purely random event happening with some fixed probability (like flipping a biased coin). The main result we present is that if we tolerate an arbitrarily small error probability in the result then the rB-hole Search problem, or RBS, is not harder than the usual BHS. We establish this result in two different communication model, specifically both in presence or absence of whiteboards non-located at the homebase. The core of our methods is a general reduction tool for transforming algorithms for the black hole into algorithms for the rB-hole.
Nitto Igor
Venturini Rossano
No associations
LandOfFree
Searching for a dangerous host: randomized vs. deterministic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Searching for a dangerous host: randomized vs. deterministic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Searching for a dangerous host: randomized vs. deterministic will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-362933