Distributed computing + Economics

Most of my reading recently are focused on economics related to the distributed computing world. I’ll present here some interesting results.

A paper from Jim Gray concludes that with 1 dollar you can buy:

= 1 $
≈ 1 GB sent over the WAN
≈ 10 Tops (tera cpu operations)
≈ 8 hours of cpu time
≈ 1 GB disk space
≈ 10 M database accesses
≈ 10 TB of disk bandwidth
≈ 10 TB of LAN bandwidth

In their paper called Economic Models for Resource Management and Scheduling the authors present several economy-based resource management systems.

System name Economy Model Plateform
Mariposa Bidding (tendering/contract-net). Pricing based on load and historical information Distributed database
Mungi Commodity market (renting storage space that increases as available storage runs low, forcing users to release unneeded storage) Storage servers
Nimrod-G It supports economy models such as commodity market, spot market and contract-net for price establishment A Grid of distributed computers (PCs, workstations and clusters)
Popcorn Auction (highest bidder gets access to resource and it transfers credits from buyer to the seller account) Web browsers (Popcorn parallel code runs within a browser of CPU cycles seller)
JavaMarket Quality of service (QoS) based computational market (the resource owner receives f (j, t) award for completing f in time t ) Web browsers (JavaMarket runs standard Java Applets within a browser)
Enhanced MOSIX Commodity market (resource cost of each node is known) Clusters of computers (Linux PCs)
JaWS Bidding (tendering) Web browsers
Xenoservers Bidding (proportional resource sharing) Single computer
D’Agents Bidding (proportional resource sharing) Single computer or Mobile Agents
Rexec/Anemone Bidding/auction (for proportional resource sharing) Clusters (A market-based cluster batch queue system)
Mojo Nation A credit-based partnership and/or bartering model (contributors earn credits by sharing storage and spend them when required) Network storage
Spawn Second-price auction (uses sponsorship model for funding money to each task depending on some requirements) Network on workstations. Each workstation executes a single task per time slice
Supercomputing Centre Commodity market and priority-based model (they charge for CPU, memory, storage and human support services) MPPs, Crays and Clusters, and storage servers

This paper defines 4 different types of model:

  • Commodity-market model:
    Nimgrod-G, Mungi, and Enhanced MOSIX fall into this category.
    Nimrod-G claimed that it supported multiple economic models, but its implementation
    focused on commodity-market model. Nimrod-G assumed that exogenous,
    predefined and static prices exists for resources and that the length of run
    time of a program can be accurately estimated which maybe unrealistic in practice.
    In Mungi, which is a single address space operating system, applications
    obtain bank accounts from which rent is collected for the storage occupied by
    objects. Rent automatically increases as available storage runs low, forcing users
    to release unneeded storage. Its main concern is garbage collection. Enhanced
    MOSIX deployed in cluster environment uses opportunity cost method which
    converts the usage of several heterogeneous resources in a machine to a single
    homogeneous cost. It does not take the prices that consumers can afford into
    account.
  • Auction model:
    This class includes Spawn, Rexec/Anemone, and JaWS. Spawn employs
    Vickrey Auction–second-price sealed auction–to allocate resources among
    618 M. Chen, G. Yang, and X. Liu
    bidders. Bidders receive periodical funding and use balance of fund to bid for
    hierarchical resources. Task-farming master program spans and withdraws subtasks
    depending on its relative balance to its counterparts. It doesn’t consider
    heterogenous resources and is mainly targeted for Monte Carlo simulation applications.
    Rexec/Anemone implements proportional resource sharing in clusters.
    Users assign utility value to their applications and system allocates resources
    proportionally. Cost requirement is not its consideration. In JaWS (Java Webcomputing
    System), machines are assigned to applications via auction process
    in which highest bidder wins out. These above solutions doesn’t make use of
    continuous double auction.
  • Credit-based model:
    Mojo-Nation and Samsara are all kind of this type. In Mojo-Nation and
    Samsara, storage contributors earn some kind of credits or claims by providing
    storage space and spend them when needed. It is a bartering methodology.
  • Theoretical analysis:
    “Agent-Human Interactions in the
    Continuous Double Auction” explored the interaction between human objects and software bidding agents
    using strategies based on extensions of the Gjerstad-Dickhaut and Zero-
    Intelligence-Plus algorithms in a continuous double auction process. Gains
    of human objects and software agents and trading equilibrium are its main concern.
    “Analyzing Market-Based Resource Allocation Strategies for the Computational Grid” measured the efficiency of resource allocation under two different market
    conditions–commodities markets and auctions–in terms of price stability,
    market equilibrium, consumer efficiency, and producer efficiency using hypothetical
    mathematical model.

Resource allocation