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⁴. 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⁵.

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 $m$ sub domains. How many times $n$ do we need to solve an incoming job with random parameters that specify a sub domain $i$ ( $1\leq{i\leq{m}}$) of our task, to receive at least an answer from each sub domain?