Keith Kong                      Dipak Ghosal
Ph. D. student                  Assistant professor
Elect. and Comp. Eng. Dept.     Comp. Sci. Dept.
Univ. of Calif. at Davis        Univ. of Calif. at Davis
Davis, CA 95616                 Davis, CA 95616
kkong@ece.ucdavis.edu           ghosal@cs.ucdavis.edu


Bartering Cycles and Bits
-------------------------

There are millions of personal computers in the United States, each
operating on the order of a hundred million instructions per second
and equipped with storage space on the order of a billion bytes.  The
aggregate computing resources of so many machines dwarfs even the most
powerful of supercomputers.  Most of it go unused at nights, on
weekends, or simply at other times whenever work activity is low.
There is much to be gained economically if even a small portion of
this waste is put into good use.

Exploiting idle computing resources within a single administrative
domain is not a new idea; it occurs at all levels of a generalized computer
architecture.  At the microprocessor level, ``pipelining,'' a
technique reminiscent of a factory assembly line, is used to harness
the power of otherwise idle components within a processor.  At the
operating system level, multitasking is used to efficiently allocate
computing and i/o resources to different tasks according to their
particular needs.  At the network level, software exists to distribute
load across multiple machines and to exploit valuable but unused
resources such as RAM.

Recently, there has been a resurgence of interest in harnessing the
power of idle resources at the network level.  This is caused by two
factors: 1) the continued phenomenal improvement in the
price/performance of commodity personal computer systems, and 2) the
widespread introduction of low-cost high performance components for
networking computers.  The former has dramatically narrowed the gap
between the performance of traditional supercomputers and personal computers.
The aggregate MIPS of a few high-end personal computer systems today,
for example, exceeds that of a Cray 2, a supercomputer of only a
decade ago.  The latter makes it possible to harness the power of many such
machines, possibly distributed across geographically distant
locations.  This makes it possible to share not only the storage and computing
resources of many small machines, but also to use them in concert as
building blocks for super computers.

Recent projects in academic institutions have concentrated in
developing technologies to harness the power of inexpensive computers
through high speed networks.  Researchers at Berkeley [1] and Illinois
[2], for example,  have successfully made supercomputer-class
computing entities from networks of commodity workstations through
special networks.  Researchers at Virginia are embarking on an even
more ambitious project to build a nation-wide virtual super computer
by building the necessary software components to harness the power of
a number of heterogeneous machines.

The Virginia project, called Legion [3], stands apart from the other
schemes in that it is designed to scale across organizational
boundaries.  Doing so allows for a far greater utilization of
resources.  It also raises the question of how willing users are able
to contribute idle computing time in exchange for being able to have
access to greater computing power when they need it.  What incentives
do individual organizations have to donate resources -- even if these
resources are idle -- to other organizations, and do benefits that
accrue as a result of such donations outweigh the cost?

The exchange of idle resources for the promise of resources when
needed is a form of bartering.  Unlike other forms of bartering, the
cost of ``loaning'' in a networked computing environment is often
negligible: the CPU will continue to execute instructions and the hard
disk will continue to spin regardless of whether it is doing something
useful or not.  Under these circumstances, there is little cost to the
owner of an idle machine to loan computing and storage resources to
other users.

We believe direct experience in such a bartering system on a limited
scale will be instrumental in determining its feasibility.  Towards
this end, our own work on ``pseudo-serving'' [4] can serve as an
excellent basis for prototyping such a system.

Pseudo-serving is a new paradigm for accessing information on a
network in which the users themselves play a central role in making
it possible for other users to bypass network congestion occurring
near the server.  A pseudo-server system consists of two components: a
super server and a set of pseudo-servers. The former grants the latter
access to files in exchange for some amount of network and storage
resources through a contract.  This amount is zero under ``low-demand''
conditions, when the super server functions as a concurrent server and
pseudo-servers function as clients. Under ``high-demand'' conditions,
when the super server's concurrency limit has been reached, it may be
possible to grant immediate access to the pseudo-server in exchange
for temporary usage of its network and storage resources. Under these
circumstances and subject to the condition that the contract is met,
the super server gives the pseudo-server a referral to where the
requested data may be obtained.

Initial simulations based on a simplified model of the Internet show that
a user participating in pseudo-serving reduces the total time
it takes to download a file from a busy site by over an order of
magnitude.  Specifically, under ``flash crowd'' conditions, in which
many requests are made over a short period of time for the same
100,000-byte file on a server, the time it takes to download the
file is reduced from about 25 minutes to less than one minute. [4]

We believe the possibility of such a dramatic reduction in the
download time provides sufficient incentive to individual users to
participate in such a bartering system.  This is especially true when
one considers that the cost to the participant in the exchange, the
network and storage resource that she contributes, turns out to be
simply serving the file she just retrieved to at most two other users
within minutes after retrieving the file.  Moreover, because uploads
can often be done at the same time as downloads without significantly
affecting the download speed, this ``contribution'' is not likely to
be a burden to the participant, whose main interest is speeding up
downloads.

The introduction of pseudo-serving to a loosely cooperative internetwork
such as Internet 2 would be a valuable way to gain experience in a
bartering system.  Such a prototype would be instrumental in providing
facts leading to answers to many questions, some of which include:

1) How much computing resources is actually wasted due to idleness?
2) Do the benefits to the individual participants outweigh the costs so that
   a sufficient number of users will participate in order to make bartering
   a success?
3) How immediate should the benefits be to the user in order for
   her to agree to donate idle resources?
4) How honest are users in fulfilling contracts?
5) How easy is it to detect users dishonesty and to discourage it?

Finally, pseudo-serving can be deployed quickly and at little cost.
Only two pieces of software, the Web client and the Web server, need to be
modified in order to make pseudo-serving work.  The distribution of
such type of software through the current WWW is a demonstrated success.


References

[1] The Berkeley NOW Project
    http://now.cs.berkeley.edu

[2] High Performance Virtual Machines (HPVM) a.k.a. Scalable Clusters
    http://www-csag.cs.uiuc.edu/

[3] "The Legion Vision of a Worldwide Virtual Computer"
    Communications of the ACM January 1997
    http://www.cs.virginia.edu/~legion/

[4] "Pseudo-serving: A User-Responsible Paradigm for Internet Access"
    To be presented in WWW 6 in April 1997 in Santa Clara, CA.
    http://www.ece.ucdavis.edu/~kkong/paper/pseudo_serving.html