Volunteer computing is a form of distributed computing in which computing resources are provided by volunteers whose computers are connected to the Internet. Because there are a huge number of PCs in the world, this computing paradigm provides more computing potential than any other form of computing. It also presents various challenges, including recruiting and retaining volunteers, dealing with an ever-changing network as users join and leave, communication bottlenecks, and security issues. Since there are over one hundred groups which rely on volunteer computing to perform their computations, this is an important research area.
I am exploring the use of casual games to supplement traditional volunteer computing efforts. Casual games are those computer games that are designed to be played with a minimal amount of instruction and/or skill and in a small amount of time. There are two main ways of approaching this idea-using casual games to attract a wider participation base and make them perform computation in the background in order to play, or implementing volunteer computing games. A volunteer computing game is a casual game that is an implementation of a volunteer algorithm. Thus, the player is actually solving a real problem as they play the game. In the past few years, Luis von Ahn has successfully used casual games to implement distributed human computing projects. To my knowledge, this approach has not been used elsewhere.
Although volunteer computing draws participants from a very limited demographic, casual games are played by almost everyone. Therefore, using games should attract users from a wider and larger demographic, which should result in more computation being performed. It turns out there may be additional benefits of this approach. I would like to answer the following questions:
With the assistance of two undergraduate students, I recently developed a prototype "game that can solve instances of the Maximum Clique Problem. We presented both the concept and our prototype at FuturePlay 2006. With the feasibility of this approach demonstrated, I am ready to take this project to the next level. There are two main areas of attack as I proceed. First, I need to identify more computational problems which can be solved in a volunteer computing setting, either by adapting existing distributed algorithms or creating new ones. Second, I need to explore ways of creating interesting games based on the volunteer algorithms.
In the future, I will investigate the use of Massively Multiplayer Online Games (MMOs) to implement distributed algorithms. I believe this approach can be successful particularly for problems that can be modeled using graph theory.
I recently started working with Dr. Bekmetjev in the Department of Mathematics on graph pebbling problems.
Pebbling is a process defined on a connected graph. A graph is a set of vertices and edges that connect some of the vertices. A connected graph is a graph where there is a path between any two vertices. Graphs are used to model transportation and communication networks. Pebbles are placed on the vertices of a connected graph and are moved along the edges. A move consists of taking two pebbles from a vertex, placing one on an adjacent vertex, and discarding the other. The objective of pebbling is to put at least one pebble on a designated vertex, called the root. A configuration (that is, a placement of pebbles on the vertices) is called r-solvable if it is possible to move a pebble to a specified vertex r (the root). A configuration is called solvable if it is r-solvable for every vertex r in the graph. The pebbling number of a graph G is the minimum number t such that every configuration of t pebbles is solvable.
We are developing effective algorithms that automatically find pebbling solutions for various families of graphs so we can use these algorithms to study probabilistic models on random pebbling configurations. We are using parallel computing clusters to speed up our computations.