Chocolate and Gold Coins

Friday, March 17, 2006

A Plumbing Issue

When I met Ravikiran, one of the things we discussed briefly was an idea I had to teach people economics using game theory. I won’t bore people with the idea again – I posted about that here. Rather, I am interested in knowing if there are people in blogland that know enough about computers and connecting them via the Internet to tell me roughly how difficult linking millions of computers together to play a game would be.

The idea is that many people would be playing a game on the Internet. These people would be sending signals – vectors of data – to each other. This information would then be aggregated and fed back to everyone in aggregate form.

You could think of this as a plumbing issue where the data is water and the problem is transferring the water from residence to residence. It is very definitely a solvable problem and many people have solved similar problems. What I want to know is roughly the amount of the plumbing bill.

Let me give a simple example. Suppose people want to purchase some of commodity. People have preference so it would be straightforward to compute each person’s individual demand curve: for each price we could know the quantity demanded. We could adequately represent the demand curve with a vector of data. Taking the price vector as a known given we would just need the corresponding quantity vector. The aggregate demand curve would come from the summation of these individual demand vectors.

I would know how to program such a problem on a single computer. The problem for me is that the vectors of data are on perhaps a million computers and how does one efficiently collect so much data?

My idea is that each player’s personal computer would be the “slave” to some other “master” computer. There might be 10 slaves per master. The master tells the slave that it should send the information to the master’s address. When the slave has the data ready, it sends the data to the master. The master aggregates and sends it to its master and so on. Eventually all of the data is aggregated on the super-master and this information flows back to whomever needs the information.

There are two issues here that I would like to know about:
1. How difficult is it to use the Internet to hook up computers in this way? Is there off the shelf software that would make this a snap?
2. How long would it take for the signals to propagate all the way up to the super-master? We always assume that the computer computes virtually instantaneously, but that really isn’t true. And sending signals between computers is a cumbersome way to do computation. My feeling is that the propagation delay time here would be non-trivial and may require fancy programming.

So, are there any computer gurus among my readers who would know about this?

Update
I should point out that there is another major issue with the master-slave thing. The computers are not always on and some people might play for a while and then quit. The master must wait for a slave that really is playing but must ignore a slave that abruptly quits. And do you want to use master computers that might occasionally quit also? That throws in another interesting complication.

3 Comments:

  • Many distributed systems solve this (and more general) problems like the one you describe. Google Desktop comes to mind immediately. SETI@home was more complex but along similar lines. There are many distributed games too; check http://en.wikipedia.org/wiki/World_of_warcraft

    But the plumbing bill, so to speak, can be high, depending on what exactly you have in mind. Fancy graphics or web forms? Continuous interactive role-play or like colossal cave?

    By Blogger Eswaran B, at 6:42 PM  

  • Hi Eswaran
    Thanks for this info. I check this out. I really know nothing about linking computers together efficiently.

    By Blogger Michael Higgins, at 6:10 AM  

  • Hmm.. how different is your problem from that of .. say Flickr? In Flickr, you do local computation (the conversion of light to digital information, i.e the image file) and then "manually" upload it to a central server (Flickr.com). Data Aggregation from multiple sources.

    the only difference I see is that you have to replace "manually" with automatically, and in that case you don't need a distributed system at all. (Unless there are other constraints that are not evident from the post).

    So, having a web-site + some program which logs data into your website is all you need. (probably just a website).

    The problem of connectivity shifts to your ISP.

    By Anonymous Vishnu Vyas, at 6:53 AM  

Post a Comment

<< Home