e=-1 color=black>

Contract-Based Load Management in Federated Distributed Systems
Contract-Based Load Management in Federated Distributed Systems Magdalena Balazinska, Hari Balakrishnan, and Mike Stonebraker
MIT Computer Science and Articial Intelligence Lab
http://nms.lcs.mit.edu/projects/medusa/
Abstract
This paper focuses on load management in loosely-
coupled federated distributed systems. We present a dis-
tributed mechanism for moving load between autonomous
participants using bilateral contracts that are negotiated
ofine and that set bounded prices for moving load. We
show that our mechanism has good incentive properties,
efciently redistributes excess load, and has a low over-
head in practice.
Our load management mechanism is especially well-
suited for distributed stream-processing applications, an
emerging class of data-intensive applications that employ
a continuous query processing model. In this model,
streams of data are processed and composed continuously
as they arrive rather than after they are indexed and stored.
We have implemented the mechanism in the Medusa dis-
tributed stream processing system, and we demonstrate its
properties using simulations and experiments.
1
Introduction
Many distributed systems are composed of loosely
coupled autonomous nodes spread across different admin-
istrative domains. Examples of such federated systems
include Web services, cross-company workows where
the end-to-end services require processing by different
organizations [3, 21], and peer-to-peer systems [8, 23,
30, 45]. Other examples are computational grids com-
posed of computers situated in different domains [4, 16,
44], overlay-based computing platforms such as Planet-
lab [35], and data-intensive stream processing systems [1,
2, 5, 6, 7] that can be distributed across different domains
to provide data management services for data streams.
Federated operation offers organizations the opportu-
nity to pool their resources together for common bene-
t. Participants can compose the services they provide
into more complete end-to-end services. Organizations
can also cope with load spikes without individually hav-
ing to maintain and administer the computing, network,
and storage resources required for peak operation. This material is based upon work supported by the National Science
Foundation under Grant No. 0205445. Any opinions, ndings, and con-
clusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reect the views of the National Science
Foundation.
Autonomous participants, however, do not collaborate
for the benet of the whole system, but rather aim to max-
imize their own benet. A natural way to architect a fed-
erated system is thus as a computational economy, where
participants provide resources and perform computing for
each other in exchange for payment.
1
When autonomous participants are also real economic
entities, additional constraints come into play. The pop-
ularity of bilateral agreements between Internet Service
Providers (ISPs) demonstrates that participants value and
even require privacy in their interactions with each other.
They also practice price and service discrimination [24],
where they offer different qualities of service and different
prices to different partners. For this purpose, ISPs estab-
lish bilateral Service Level Agreements, where they de-
ne condential details of the custom SLA and prices that
one partner offers another.
In this paper, we present a distributed mechanism for
managing load in a federated system. Our mechanism is
inspired on the manner in which ISPs collaborate. Unlike
other computational economies that implement global
markets to set resource prices at runtime, our mechanism
is based on private pairwise contracts negotiated ofine
between participants. Contracts set tightly bounded prices
for migrating each unit of load between two participants
and specify the set of tasks that each is willing to execute
on behalf of the other. We envision that contracts will be
extended to contain additional clauses further customiz-
ing the offered services (e.g., performance and availability
guarantees). In contrast to previous proposals, our mecha-
nism (1) provides privacy to all participants regarding the
details of their interactions with others, (2) facilitates ser-
vice customization and price discrimination, (3) provides
a simple and lightweight runtime load management using
price pre-negotiation, and (4) has good system-wide load
balance properties.
With this bounded-price mechanism, runtime load
transfers occur only between participants that have pre-
negotiated contracts, and at a unit price within the con-
tracted range. The load transfer mechanism is simple: a
participant moves load to another if the local processing
cost is larger than the payment it would have to make to
1
Non-payment models, such as bartering, are possible too. See Sec-
tion 2 for details. another participant for processing the same load (plus the
migration cost).
Our work is applicable to a variety of federated sys-
tems, and is especially motivated by distributed stream
processing applications.
In these applications, data
streams are continuously pushed to servers, where they
undergo signicant amounts of processing including l-
tering, aggregation, and correlation. Examples of appli-
cations where this push model for data processing is
appropriate include nancial services (e.g., price feeds),
medical applications (e.g., sensors attached to patients),
infrastructure monitoring (e.g., computer networks, car
trafc), and military applications (e.g., target detection).
Stream processing applications are well-suited to the
computational economy provided by a federated system.
Data sources are often distributed and belong to different
organizations. Data streams can be composed in differ-
ent ways to create various services. Stream processing
applications also operate on large volumes of data, with
rates varying with time and often exceeding tens of thou-
sands of messages per second. Supporting these applica-
tions thus requires dynamic load management. Finally,
because the bulk of the processing required by applica-
tions can be expressed with standard well-dened oper-
ators, load movements between autonomous participants
does not require full-blown process migration.
We have designed and implemented the bounded-price
mechanism in Medusa, a federated distributed stream-
processing system. Using analysis and simulations, we
show that the mechanism provides enough incentives for
selsh participants to handle each others excess load, im-
proving the systems load distribution. We also show that
the mechanism efciently distributes excess load when
the aggregate load both underloads and overloads total
system capacity and that it reacts well to sudden shifts in
load. We show that it is sufcient for contracts to specify
a small price-range in order for the mechanism to produce
acceptable allocations where (1) either no participant op-
erates above its capacity, or (2) if the system as a whole
is overloaded, then all participants operate above their ca-
pacity. We further show that the mechanism works well
even when participants establish heterogeneous contracts
at different unit prices with each other.
We discuss related work in the next section. Section 3
presents the bounded-price load management mechanism
and Section 4 describes its implementation in Medusa.
We present several simulation and experimental results in
Section 5 and conclude in Section 6.
2
Related Work
Cooperative load sharing in distributed systems has
been widely studied (see, e.g., [10, 19, 22, 25, 41]). Ap-
proaches most similar to ours produce optimal or near-
optimal allocations using gradient-descent, where nodes
exchange load among themselves producing successively
less costly allocations. In contrast to these approaches,
we focus on environments where participants are directed
by self-interest and not by the desire to produce a system-
wide optimal allocation.
As recent applications frequently involve indepen-
dently administered entities, more efforts have started to
consider participant selshness.
In mechanism design
(MD) [20, 33], agents reveal their costs to a central en-
tity that computes the optimal allocation and a vector of
compensating payments. Agents seek to maximize their
utility computed as the difference between payment re-
ceived and processing co