The new economy of computation.
By Jeff Sidell
While sitting in a café, you decide to check your stock portfolio. Your request passes through the Internet to a stock quote server in New York. At the same time, someone next to you is watching live coverage of a Senate hearing, and a couple hundred brokers around the country are checking their portfolios using the same quote server in New York. You're competing with these other people for resources: Net bandwidth, the quote server's disk, and processing time. As the Net makes available more and more resources that must be shared by more and more people, allocating these resources equitably becomes difficult.
Resource management for one computer - even one shared by many users - is relatively easy: the computer's operating system keeps track of all the users and their programs and hands out the computer's resources in some manner it deems fair. But there isn't an operating system for the Internet to make sure all the users are happy (or at least equally unhappy). First of all, the machines are managed by different organizations: Citibank, for example, isn't about to let anyone manage its machines to help evenly distribute the network load. Also, there are some fundamental problems - exponential growth, the high overhead of collecting distributed information, and the impossibility of predicting resource usage - that doom a traditional, centralized approach.
An alternative is to decentralize the decisionmaking and information gathering. This is the approach taken by agoric systems. Agoric comes from agora, the Greek word for marketplace. The programs and computers in these systems become buyers and sellers of resources, much like a real-life marketplace. Buyers compete against one another for scarce resources and try to get the best price they can, while sellers attempt to maximize their profit.
The term agoric systems was first used in 1988 by Mark Miller and Eric Drexler in a paper they co-authored. Miller then went on to cofound Agorics Inc. (www.webcom.com /agorics/) in Los Altos, California. His company applies a market-based system to bandwidth allocation in a computer network. With most networking protocols such as Ethernet, a user watching Independence Day can hog the bandwidth and keep everyone's email from getting through, even though the mail is more valuable and should get through at the cost of dropping a frame or two of video, which would be undetectable. A centralized, systemwide solution to this problem would be like trying to manage all the traffic in Manhattan by sending a police car to each intersection every few minutes to report the situation back to headquarters. The extra traffic would quickly bring the system to its knees. Alternately, setting aside bandwidth for video and data would be like reserving a lane at all times for police traffic - wasteful, since if there's no data traffic, the video should use all the available bandwidth. The Agorics solution allows applications to compete for available bandwidth. Each network switch awards bandwidth to the application willing to pay the highest price - the one that needs it most.
A much more complex and ambitious agoric system is a distributed database management system called Mariposa (epoch.cs.berkeley.edu:8000/mariposa), being developed at UC Berkeley by Michael Stonebraker. Each Mariposa server has buyer and seller processes running on it. A buyer negotiates with a seller at another site to perform work on its behalf. To get prices for the stocks in his portfolio, a user in San Francisco would submit the appropriate query to a Mariposa server just as in a regular database system. But along with the query, the user sets a limit on the price and time the system can take to run the query - for instance, US$15 for an answer in 30 seconds, and nothing if it takes longer than five minutes. The query and other information is passed to a buyer process, which breaks the query into pieces and sends them to seller processors running at various sites. Each seller responds to the buyer's request with the price it will charge to perform the work and an estimate of the time it will take.
For example, the buyer may ask quote servers in New York and San Francisco to bid on reading the database file and picking out the entries in the user's portfolio. The buyer may ask other Mariposa sites to perform other work, such as sorting the entries. The computer in New York may charge $10 and send the answer back in 10 seconds, while the San Francisco site may charge only $5 but take 10 minutes. The buyer collects all the bids and then notifies the winning sellers to begin work. While this bidding process involves some communication overhead, in most cases it is vastly outweighed by the time it takes to perform the work.
In addition to buying and selling computing power and network bandwidth, a Mariposa server can purchase database tables or copies of tables from other sites. If a Mariposa server in Chicago noticed that a lot of local users were accessing stock prices, it could try to buy a copy of the entire stock table from New York or San Francisco. The Chicago site would have to pay for the table as well as for updates when stock prices changed.
Unlike many of today's agoric systems, Mariposa doesn't distinguish between buyers and sellers. For example, a seller that has been asked to submit a bid for some work can subcontract all or part of that work to another site, making the seller a buyer as well. In one experiment, Mariposa researchers simulated a corporation with offices around the world. As the business day began at each office, Mariposa buyers compared how much they were paying remote sellers with how much it would cost to buy the necessary data. As a result, heavily used tables moved from office to office with the rising and setting of the sun, and overall system performance improved.
Agoric systems are not the answer to all the world's distributed computing needs. Just as in a capitalist economy, where not every worker is an independent contractor, computing also has a need for cooperation and centralized organization. But the agoric approach is likely to become important for wide-area distributed systems with many thousands of machines, such as the Internet.
Jeff Sidell (firstname.lastname@example.org) is a graduate student at UC Berkeley.