Any remote machine running a Java compatible browser may participate into the process of solving such problems. To this end, the remote machine (a client, in Java terminology) downloads suitable problem solving software, embedded in a Java applet, together with the specification of the subproblem to be solved. The Java applet communicates with the "problem solving server" (a Java application running on the same machine hosting the centralized problem repository) in order to handle normal termination as well as any exceptional conditions that may arise during the solution process. The server collects the results provided by the client(s) and manages them locally.
The protocol sketched above is of Master-Slave type, with the Master distributing basic computational tasks to - and collecting solutions from - the Slaves via Internet. In Java terminology, the Master-Slave protocol can be viewed essentially as a Client-Server type of interaction with the roles interchanged, i.e., it is the Client which provides services (i.e., CPU time) to the Server.
The Server - a Java application - maintains a list of problems to be solved (or being solved). For each problem, the internal description includes a (static) decomposition into a number of subproblems, which are the basic computational tasks to be assigned to the Clients. When appropriately `combined' by the server, the solutions to the subproblems give the solution to the original problem.
By connecting to the machine which hosts the Server, the Client automatically fetches a subproblem and starts solving it. Upon termination, it sends the solution back to the Server and the protocol starts again.
While the above protocol does not require any supervision at the Client's side, the interested user may obtain some basic information on the nature of the problem (s)he is contributing to solve through a graphical interface.
In order to handle more general problems, we are currently working to incorporate more structured algorithmic paradigms, in which dynamic subproblem generation and `combine' steps alternate, thus leading to computation trees of arbitrary depth.
The Master maintains a set of problems instances, or problems for short, in the Problem Pool. Each problem is divided into subproblems, which can be solved independently and whose solutions make it possible to compute the global solution with little additional effort.
The most important data structure, among those shared by all problem types, is the Status, which stores the status of the subproblems (available, submitted or solved ). When a www browser (Java enabled) requests the access to a specific html page (on the same host that runs Master), the Slave applet is loaded from the host and starts running in the Java virtual machine provided by the browser, as shown below.
During the first interaction, the Slave sends the Master some information about the machine it is running on, i.e., the supported Java version, the available memory, the hardware architecture and the operating system.
The Master, possibly driven by the information received from the Slave, chooses an available subproblem in the Problem Pool and sends code and data to the Slave, which starts a new thread for solving the subproblem, as shown below.
The Master turns the subproblem status to submitted, the connection is closed, and the thread ends.
The Master maintains information on the time at which each subproblem has been submitted. If a subproblem solution timeouts, the corresponding status is reverted to available, to account for a possibly undetected abortion.
The graphical interface of the Slave conveys information about the advancement of computations, the number of subproblems locally solved and makes it possible to stop the Slave. Through the Slave interface, the user can also detect which Problem (s)he is contributing to solve.
After having solved the subproblem, the Slave establishes a new connection with the Master, identifies itself, sends the results and closes the connection.
The Slave can also establish connections to the Master before termination, to send partial results, e.g., when local memory is scarce.
After the solution has been sent, the Slave connects again to the Master, asking for another subproblem to solve. This process continues until Slave is stopped or no more subproblems are available from the Master.
Upon receipt of results from any Slave, the Master turns the subproblem status to solved and behaves according to the Problem type. Several action are possible. Basically the Master stores the subproblem result on disk, for future computations. The result corresponding to the solution of a subproblem can also let the Master know that the solution of the remaining subproblems is not necessary, and that it can proceed to compute the solution of the problem locally. This feature is useful in a number of search problems, e.g., when the goal is to find a certificate that proves that a certain property is true.
When the Master has received all the results corresponding to the subproblems of a Problem (or an early termination condition, as in the above case of search problems), it can postprocess the results locally, and either obtain the solution to the Problem or add to the Pool a new Problem (of different kind), that will take care of the postprocessing in a distributed fashion.
The Master is a Java application without graphical interface, suitable to run in background. Graphical interface to the Master activities is provided by a set of applets, globally called the Manager, which allow one to remotely control the Master. Using the Manager it is possible to add problems to the Problem Pool or display/save/load/backup its status.
The Framework is a part of the Java code independent of the actual code for solving Problems. The Framework mainly governs Master-Slave interactions, Problem Pool management, and User interface.
The programmer is responsible for the code for Problems, both in Master and Slave environment. To this extent, the Framework defines a number of Java interface's which the classes for each Problem must implement.
The above description is taken from the article
B. Codenotti, M. Leoncini and G. Resta,
A Java Framework for Internet Distributed Computations, in: E. N.
Houstis, J. R. Rice, E. Gallopoulos and R. Bramley, Enabling
Technologies for Computational Science: Frameworks, Middleware and
Environments, Kluwer Academic Publishers, (2000)
Distributed computing demo page
Back to IMC home page