** Next:** Throwing N stones into
** Up:** Theoretical considerations
** Previous:** Theoretical considerations
** Contents**

##

Randomized algorithms

To implement plugins and frontends in the proposed framework, it is first important
to recognize that the entire network does not provide any guarantees of
availability. Computing nodes might go down in the middle of a job for
several reasons like power failure, network congestion or just because the
computer is shut down by the user. This is a crucial difference, compared to
the `MPI` [1,8] or the `OpenMP`[1] library, where the developer decides *a priori* how many
nodes will compute.

A second issue, at least as serious as the first, involves the nature of
Gnutella: all packets sent to the connected computers will be exactly the
same. Each computing node will get the same arguments to start the
computation, although they may compute different results. In a similar
way, all file sharing programs may get the same request for a particular song's
author, but are able to answer with different files they host, all from the
same author.
Notice that this issue is intrinsic in the Gnutella network: each node knows
only its neighborhood^{4}. We do not
have topology information and therefore we cannot split our computation in
pieces of different length. Moreover, the entire network
topology changes rapidly. So, there is no way to pass
particular arguments to particular nodes.
To solve the issue,
we propose several solutions that all involve some use of randomness.

Special randomized algorithms can alleviate our concerns. For
some categories of problems, Monte Carlo methods produce reasonable
results. In this category, we can place the plugins that solve Pi and the
partial differential equations with the Feynman-Kac formula [1] (`pi.dll,
pde.dll, pde3d.dll`). Most Monte Carlo methods are not suitable to get an
exact solution though they provide good approximations.

Genetic algorithms, and genetic algorithms with neural networks might be
suitable for the framework: however, frontends will be charged with additional
management tasks.

Some brute-force tasks can be randomized using mathematical properties of the
problem. As an example the discrete logarithm problem can be solved using the
*Pollard-Rho* algorithm^{5}.
As further brute-force tasks, we mention here
the Search for Golomb Rulers and attacks on encrypted codes.

All brute-force tasks, where a big range of possible solutions is searched,
can be randomized; We split our search space into sub domains. How
many times do we need to solve an incoming job with random parameters
that specify a sub domain (
) of our task, to receive at least an answer from each sub domain?

** Next:** Throwing N stones into
** Up:** Theoretical considerations
** Previous:** Theoretical considerations
** Contents**
Tiziano Mengotti
2004-03-27