Examples of distributed algorithms


Came across this website where people donate their CPU time to find the prime numbers.
Was curious about how it works.

Does anyone know of any repo/article which talks about taking this kind of problem and implementing a naive solution in three levels using elixir/erlang

  • sequential
  • parallel
  • distributed

Do share your experiences working with such systems.

Primality checking is simple to do in parallel. Imagine that you want to check number n = 2**n - 1:

  1. You generate sequence of primes from 2 to 2**(n/2) - 1 as if number is not prime, then it will have divisor there.
  2. Each machine that want to participate in testing now will request divisor d to test against and will check if n % d == 0
  3. If result is true, then you send result to the central server that this is not prime, if you get false then you send that it is potential prime.
  4. If result was false then you go to the step 2 as long as all potential divisors aren’t tested.
1 Like