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
- Economic models for allocating resources in computer systems
- Towards a Micro-Economic Model for Resource Allocation in Grid Computing Systems
- market-oriented programming and distributed resource allocation
- Microeconomic Theory Applied to Distributed Systems
- Resource Allocation Based on Pricing for Grid
Computing Environments - Neptune: A Dynamic Resource Allocation and Planning System for a Cluster Computing Utility
Comments Off