Peter Aykroyd and Dakila Clark
Our project is based on a model of distributed computing often referred to as the grid. The commonly used metaphor for a computing grid is the a power grid. In a power grid, every person connected may not only consume power but is also able to sell power to the electric company by producing there own. Similarly, in a computing grid, each user attached to the system may use the resources of other computers and also may offer his own computer for use. In this way, when his machine is not in use locally it can be used by other grid consumers. Therefore, under such a model the computing resources of the world could be maximized.
Obviously, our project will not address the global scale that implementing such a grid would require. Or the social factors that will be necessary to bring the grid to pass. However, the software tools we develop will have some grid-like qualities in that the computers with our clients installed will use offer their idle CPU time to the project server which will then assign them work to be done.
Using the DCOM package available in Windows NT which provides distributed computing functionality, we will write both a client and a server which will be able to exchange information. The specific use of this in relation to our cooperative work with Rich Wolski at UCSD to find Ramsey numbers is that a server will be able to give the client a range of numbers to search. The client will then report back to the server to indicate whether or not a Ramsey number was found.
An important attribute of our software must be politeness with regards to the computerUs user. Therefore, it would not be appropriate for the client to search its range of numbers while the computer is in use. To this end, the client will only be active when it detects that the system is no longer in use. This is of the essence because users must be convinced that if they cooperate with the project by installing a client that it will not hamper than own work. Similarly, the client must be secure. No sane user would want to install software that could potentially put their own files at risk of being accessed due to a security bug. Therefore, we will not only make sure that both the server and client are secure but document it for reassurance of potential users. It is also our desire that the client and server be extendable. This is desirable so that we will be able to use our software to search for more than just Ramsey numbers. Indeed, software tools such as this have application with many scientific endeavors. Our implementation may either take advantage of a plug-in architecture which would allow the compiled client to learn what algorithm to perform on a given data set from it. Or, alternatively, may simply be written with a clear separation between the distributed computing tools and the code necessary for the specific scientific inquiry. Finally, in relation to our Ramsey numbers work, our client must be able to communicate with the UNIX servers running at UCSD which our the heart of that operation. This compatibility may or may not induce to code our own server with similar protocols to those of UCSD server software.
Ramsey numbers is really just an extension of the "pigeonhole principle". The nth Ramsey number Rn is defined as the smallest number k such that all complete bicolored graphs on k nodes possess a monocolored complete subgraph on n nodes. For example, it has already been proven that R3 = 6. To put this is into context, R3 = 6 is the smallest number of people that need to be at a party in order for 3 of the 6 to know each other, or 3 of the six to not know each other. We know this because, using graph theory, we can construct a graph with 6 vertices representing the 6 people and we can construct 3 red triangles and 3 blue triangles out of the 6 vertices. The only question now is whether or not we can do the same thing with less than 6 people. We notice that R3=5 doesn't work because we cannot construct 3 red triangles and 3 blue triangles. Hence we've just shown that 5 < R3 <= 6. Therefore, R3 = 6.
Currently, the first four Ramsey numbers have been proven. The proofs for the others however have eluded mathematicians. For this project, we are concentrating our efforts on finding the 6th Ramsey number, which is known to be somewhere between 102 and 165. It's not feasible to search through all possible bicolored graphs for 102 nodes. However, by finding bicolored complete graphs having no monocolored complete subgraphs of 6 nodes, we can eliminate the existing lower bound and find new lower bounds, thus converging on the value of R6.
Now the implications of finding Ramsey numbers through distributed computer resources appear to make our project extendable to other possible branches of combinatorial mathematics or number theory. For example, we can use distributed computer resources in finding primes (special primes: Mersenne and Twin), perfect numbers, or magic squares, although these are trivial, hackneyed exercises. Another possible venture for our project is to explore certain cryptology systems which are very closely related to number theory.