Universally Accessible Distributed Computing on Public, Heterogeneous Networks,
Applied to the Search for Mersenne Primes
Appendix B: Processing Resource Applet
Appendix C: Control Server Source Code
Implementation
There are three basic components in our implementation: a control server, a database, and one or more processing resources. The high-level logical flow of the system is shown in this flowchart, and the more detailed descriptions of the components follow.
Flowchart
Control Server
The control server coordinates the work of the processing resources, and handles the implicit (and indirect) interaction between the resources and the database. When a resource requests work, the control server checks the database for pending work, and assigns an appropriate task to the resource. This functionality is implemented as a Python CGI script that receives XML-RPC requests from processing resources, reads and writes the database via calls to SQL stored procedures, and returns XML-RPC responses to the processing resources.
The control server publishes five functions as XML-RPC methods that are invoked by the processing resources:
- request_work
- This method checks for untested seed primes in the database, and assigns a trial division or Lucas-Lehmer task (as appropriate) if any exist; otherwise, a sieve task (to generate new seed primes) is assigned. The assignment details are sent back to the processing resource in the XML-RPC response, along with a 16-byte Universally Unique Identifier (UUID) used as a job key.
- post_sieved_primes
- This method takes a set of primes (encoded as a bit set) resulting from a sieve task and stores them in the database.
- post_trial_division_result
- This method receives the result of a trial division (indicating either that the candidate Mersenne number is composite, or that it may be – but isn't necessarily – prime) and updates the database accordingly.
- post_lucas_lehmer_result
- This method receives the result of a Lucas-Lehmer test (indicating either that the candidate Mersenne number is prime, or that it's composite) and updates the database accordingly.
- post_lucas_lehmer_status
- This method receives the in-process state of an ongoing Lucas-Lehmer test and updates the database accordingly – including extending the expiry time for the job key previously generated. If processing by the resource is terminated unexpectedly, or the connection fails, this information will be used to resume the task (probably with a different resource) at some later moment.
Some of the tasks assigned to resources can be very long-running – but of course, consumer-grade computers and Internet connections can't guarantee uptime. So our implementation includes features to detect and recover from interrupted processing and failed connections. If a processing resource doesn't update the control server with its status at regular intervals, a job will eventually expire. When a job expires, the job key is removed from the database, and the given job can be reassigned to another resource. After that point, even if the original resource attempts to report the outcome of the job, it will be ignored.
Database
In our implementation, a database is used to store seed primes, test results, and information about active tasks. The control server consults and updates the database when assigning tasks; it also updates the database on the completion of tasks. We implemented this functionality using MySQL, with key portions of the persistence logic written as SQL stored procedures, and maintained directly in the database.
The following stored procedures are called by the control server, to retrieve, update, and close tasks:
- assign_lucas_lehmer_task
- This procedure searches for the lowest seed prime which has already been tested by trial division (and not eliminated as composite), but is not currently assigned to a resource for processing the Lucas-Lehmer task. If one is found, a job record is created for it, and the details (the job key and seed prime, and previous state information, if this seed has been partially tested) are returned to the control server; otherwise, a null record is returned.
- assign_trial_division_task
- This procedure searches for the lowest seed prime which has not yet been tested by trial division, and is not currently assigned to a resource for trial division. If one is found, a job record is created for it, and the details (the job key and seed prime) are returned to the control server; otherwise, a null record is returned.
- assign_sieve_task
- This procedure searches a segment of numbers for which a set of seed primes has not yet been recorded in the database. This might be a previously defined segment that was assigned to a processing resource, but the resource didn't send the primes to the server (for whatever reason); or, it could be a new segment, extending the range of seed primes in the database. In either case, a job record is created, and the details (the job key, and the upper and lower bounds of the segment) are returned to the control server.
- confirm_mersenne_prime
- This procedure is called by the control server when a processing resource reports the results of the Lucas-Lehmer test on a given candidate. If the candidate is prime, the seed prime is added to the table of primes confirmed to produce Mersenne primes; otherwise, the seed prime is removed from the database altogether.
- update_lucas_lehmer_status
- This procedure is called by the control server when a processing resource reports the in-process status of an ongoing Lucas-Lehmer test on a given candidate. The number of iterations completed, and the value of the current term in the s sequence (see Model) are recorded in the database; they can be used to resume the job if the resource currently processing it fails to complete it.
- confirm_possible_prime
- This procedure is called by the control server when a processing resource reports the results of trial division on a given candidate. If the candidate is composite, the seed prime us removed from the database; otherwise it remains in the database, and a resource will be assigned the task of testing the candidate with the Lucas-Lehmer test at some future moment.
- add_sieved_primes
- This procedure is used to add all of the seed primes in a segment (as computed by a processing resource) to the database. Once in the database, trial division and Lucas-Lehmer tests on the Mersenne numbers generated by the new seed primes can be assigned to processing resources.
Processing Resource
The processing resource code is written in Java, and packaged as an applet, so that it can be embedded in a web page and executed by Java-enabled browsers. As long as the user keeps our web page open in the browser (and assuming that the network connection remains intact), the applet is a participant in our distributed processing network: it requests a task from the control server, completes the task, sends the results back to the server – and then starts the cycle again.
Each of the three processing tasks performed by the applet is implemented as a separate class, and all three are subclasses of the standard Java Thread class; this approach allows the applet to continue processing long-running tasks in their own threads, with minimal impact on browser responsiveness.
The key methods in these three classes, and the methods that communicate with the control server and instantiate processing tasks to carry out assignments received from the server, are as follows:
- Applet.next
- Applet.dispatch
- These two methods contact the control server to get the next assignment, and create an instance of one of the three task processing classes to carry out that assignment, respectively.
- LucasLehmer.process
-
This is the workhorse of the processing resource: it executes the Lucas-Lehmer test for primality of Mersenne numbers, and calls the Applet.iterationPerformed and Applet.testComplete methods at the end of each iteration and when the test is completed, respectively.
To improve the efficiency of the mod operation in our implementation, we take advantage of the equivalency:[8]
k ≡ (k mod 2n) + ⌊k/2n⌋ (mod 2n - 1)
This is the same equivalency that lets us add the digits of a decimal number together, and then do the same with the result, repeating until we have a single digit; if the result is 9, then the original number is evenly divisible by 9; if it isn't, then the number we have left is equal to the remainder we get when we divide the original number by 9. In this case, we're using a base of 2n, and applying the same technique to find the remainder when divided by 2n - 1.
There are other numerical optimizations possible (especially for multiplying large numbers together), which are used in the GIMPS software (for example), but we haven't implemented them.
- TrialDivision.process
-
This method performs a number of trial divisions of the Mersenne number, using trial divisors of the form 2kp + 1, where (2kp + 1) mod 8 = ± 1 (see Model). It also uses a simple wheel sieve to filter out trial divisors that can easily be shown not to be prime themselves.
Except in the cases of the first dozen or two candidates, our trial division isn't exhaustive (in fact, if we tried to make it exhaustive, it would soon take much more processing time than the Lucas-Lehmer test). So if we don't find a trial divisor that divides the Mersenne number evenly, it doesn't necessarily mean that the Mersenne number is prime; it only means we have to test it further, with Lucas-Lehmer. But if we do find a trial divisor that divides the Mersenne number evenly, it means that the Mersenne number is definitely not prime.
When the trial division is complete (whatever the result), this method calls Applet.trialDivisionComplete.
- Sieve.process
This method uses the Sieve of Eratosthenes, or the segmented variation, to find a set of seed primes, and calls Applet.sieveComplete when it's done.
- Applet.iterationPerformed
- Applet.testComplete
- Applet.trialDivisionComplete
- Applet.sieveComplete
-
Each of these methods is used to send results and status information back to the control server, calling the following XML-RPC methods respectively: