A Micro-Economic Approach to Conflict Resolution in Mobile Computing

A Micro-Economic Approach to Conflict Resolution
in Mobile Computing
Licia Capra, Wolfgang Emmerich and Cecilia Mascolo
Dept. of Computer Science
University College London
Gower Street, London WC1E 6BT, UK
{L.Capra|W.Emmerich|C.Mascolo}@cs.ucl.ac.uk
ABSTRACT
gained wide-spread popularity. These devices will increasingly be
Mobile devices, such as mobile phones and personal digital as-
networked and software development kits are available that can be
sistants, have gained wide-spread popularity. These devices will
used by third parties to develop distributed mobile applications.
increasingly be networked, thus enabling the construction of dis-
Even though devices and networking capabilities are becoming
increasingly powerful, the design of mobile applications will con-
tributed mobile applications. These have to adapt to changes in
context, such as variations in network bandwidth, exhaustion of
tinue to be constrained by physical limitations. Mobile devices will
battery power or reachability of services on other devices. We
continue to be battery driven and users will be reluctant to carry
show how the construction of adaptive and context-aware mobile
heavy-weight devices. Wide-area networking capabilities will con-
applications can be supported using a reflective middleware. The
tinue to be based on communication with base stations, with fluc-
middleware provides software engineers with primitives to describe
tuations in bandwidth depending on physical location. In order to
provide acceptable quality of service to their users, applications
how context changes are handled using policies. These policies
may conflict. In this paper, we classify the different types of con-
have to be context-aware and be able to adapt to context changes,
flicts that may arise in mobile computing. We argue that conflicts
such as variations in network bandwidth, exhaustion of battery
cannot be resolved statically at the time applications are designed,
power or reachability of services on other devices. Context aware-
but, rather, need to be resolved at execution time. We demonstrate a
ness implies new requirements for the middleware that is deployed
method by which these policy conflicts can be treated. This method
in such a mobile setting.
The aim of middleware in general is to resolve heterogeneity and
uses a micro-economic approach that relies on a particular type of
sealed-bid auction.
distribution in order to simplify the construction of distributed sys-
tems [8]. These problems also need to be overcome in mobile com-
Categories and Subject Descriptors
puting. There are many different computing devices and applica-
tion designers aim to build applications that are portable and in-
D.2.1 [Software Engineering]: Requirements/Specifications—Lan-
teroperable across device types. The resolution of distribution and
guages; D.3.1 [Programming Languages]: Formal Definitions
the provision of high-level interaction primitives are also important
and Theory—Semantics, syntax; C.2.4 [Computer - Communica-
in a mobile setting [20]. While middleware for fixed distributed
tion Networks]: Distributed Systems—Distributed applications,
systems is largely based on the notion of transparency (i.e., distri-
network operating systems
bution is hidden from both users and software engineers), it is less
appropriate in a dynamic and constrained setting, such as mobile
General Terms
computing. It is largely agreed that different forms of middleware
are needed for this scenario [17].
Design, economics, languages
In [4], we have presented a mobile middleware model that sup-
ports context-aware interactions among distributed system compo-
Keywords
nents, based on the principles of reflection and meta-data. The
Conflict resolution, game theory, context-awareness, mobile com-
middleware provides application designers with ‘application pro-
puting, middleware, reflection
files’ that describe how the middleware realises interactions in cer-
tain contexts. Because of the highly dynamic nature of context
1.
INTRODUCTION
in mobile setting, unforeseen context configurations may be en-
tered; moreover, user’s goals may vary and require different be-
Mobile computing devices, such as palmtop computers, mobile
haviours at different times. By changing, through reflection, the
phones, personal digital assistants (PDA) and digital cameras have
meta-information contained in the profiles, application designers
can dynamically adapt the middleware behaviour, so as to deliver
different quality of service in different context, and according to
Permission to make digital or hard copies of all or part of this work for
different application needs. While doing so, however, designers can
personal or classroom use is granted without fee provided that copies are
create profiles that contain ambiguities, contradictions and other
not made or distributed for profit or commercial advantage and that copies
logical inconsistencies.
We refer to these inconsistencies as
bear this notice and the full citation on the first page. To copy otherwise, to
conflicts.
republish, to post on servers or to redistribute to lists, requires prior specific
The novel contribution of this paper is the design and formali-
permission and/or a fee.
SIGSOFT 2002/FSE-10, November 18–22, 2002, Charleston, SC, USA.
sation of a microeconomic approach for conflict resolution that re-
Copyright 2002 ACM 1-58113-514-9/02/0011 ...$5.00.
31

---

lies on a particular type of sealed-bid auctions. In particular, our
to decompose requirements and formalises them using a tempo-
game theory-based approach treats applications as strategic players
ral logic. Conflicts are detected by reasoning about the temporal
that have been programmed by different entities to pursue different
logic formulae and conflict resolution strategies [22] can be applied
goals. In order to achieve coordination under these circumstances,
so that requirement conflicts are not come down to design. Other
a mutually accepted auction protocol is established that allows ap-
requirements engineering approaches [13] leave inconsistencies in
plications to come to an agreement. According to this protocol,
specifications and use an appropriate logic to continue reasoning,
the mobile computing middleware plays the role of an auction-
even in the presence of an inconsistency. These approaches, how-
eer, collecting bids from applications and carrying on interactions
ever, are of limited use in a mobile setting where the nature of con-
(i.e., solving conflicts) adhering to the principle that maximises so-
flicts is such that they cannot be detected statically at the time an
cial welfare, rather than individual utility. Although we present
application is designed but, instead, they can only be detected and
our conflict resolution approach in the setting of (a simplified ver-
resolved at run-time. Also, they must be resolved, otherwise appli-
sion of) our reflective middleware, the problem we are addressing
cations cannot execute.
is general and applies to the design of applications that execute in
Our work is more closely related to approaches that monitor re-
highly dynamic settings, where adaptation, auto-configuration or
quirements and assumptions during the execution of systems.
self-healing become mandatory to achieve reasonable quality-of-
Fickas and Feather’s approach towards requirements monitoring
service.
[11] uses a Formal Language for Expressing Assumptions (FLEA).
The remainder of the paper is structured as follows. In Section 2,
FLEA is supported by a CLISP-based run-time environment, which
we indicate the origins of this research and discuss our position
can alert requirement violations to the user. For mobile systems,
compared to related work. In Section 3 we describe the core char-
however, this is insufficient and a more proactive approach to re-
acteristics of our reflective mobile middleware and in Section 4 we
solving conflicts is required. Robinson and Pawlowski [19] have
provide a classification of the types of conflict that may arise in
developed a so-called “requirements dialog meta-model”, which
a mobile setting. Section 5 formalises the microeconomic mecha-
supports not only the definition and monitoring of goals, but also
nism we propose to solve these conflicts and Section 6 provides a
the re-establishment of a dialog goal in case of a goal failure. Goal
comprehensive example that clarifies how our approach effectively
monitoring is performed actively, so that violations are detected im-
works. Section 7 describes and evaluates our current implementa-
mediately; however, this requires a consumption of resources that
tion, and, finally, Section 8 concludes the paper and identifies some
hand-held devices cannot bear.
future work.
In the Distributed Artificial Intelligence (DAI) community, game
theory [1] has been extensively applied to treat negotiation issues.
2.
RELATED WORK
Negotiation mechanisms have been used both to assign tasks to
agents, to allocate resources, and to decide which problem solv-
The problem of resolving conflicts is a general one and different
ing tasks to undertake (e.g., [25] [24]). These scenarios typically
research strands have investigated it over the years.
involve a group of agents operating in a shared environment. Each
The operating systems community has studied the issue of con-
agent has its own private goal; a negotiation process is put in place
flicts in a distributed environment, where conflicts manifest as pro-
that, through a sequence of offers and counter-offers, explores the
cesses competing for shared resources. Microeconomic techniques,
chance for agents of achieving their (possibly conflicting) goals, at
and auctions in particular, have been explored; in [15], a market-
the lowest cost. Despite similarities with our scenario, there are a
like bidding mechanism is described which assigns tasks to proces-
number of assumptions that differentiate our work from previous
sors that have given the lowest estimated completion time; similar
results obtained in the DAI community. In particular, in DAI the
techniques have been used to manage network traffic [21] and allo-
quality of the result is valued much more than the cost to achieve
cation of storage space [10]. We assess that game theory [1] tools
it; as a consequence, negotiation mechanisms are usually iterative
can be successfully used to resolve conflicts that arise in the mobile
processes which proceed until an (optimal) agreement is found. In
setting too; however, rather than dealing with resource conflicts, we
a mobile setting, instead, resource constraints call for simple con-
are interested into quality-of-service conflicts in service provision.
flict resolution mechanisms that do not waste the (scarce) resources
Despite the extensive research that has been carried out within
applications need to achieve their goals. Moreover, the nature of
the mobile middleware community, the issue of conflicts has at-
goals is fundamentally different. In DAI, a goal can be seen as
tracted little attention. On one hand, many systems do not sup-
a task composed of atomic operations that the negotiation mecha-
port dynamic adaptation of middleware behaviour, and thus they
nism is able to assign to different agents; in our setting, goals are
avoid the problem of conflicts a priori. On the other hand, sys-
rather indivisible units that suggest the middleware the quality of
tems which exploit reflection to improve flexibility and allow dy-
service levels that applications are willing to achieve.
namic reconfigurability of the middleware [14, 2] generally target
Also relevant to our work is the research on quality of service
a stationary distributed environment, where context changes (and,
provision in a mobile computing environment [5]. QoS require-
consequently, adaptation of middleware behaviour) are much less
ments are defined by all applications and a negotiation mechanism
frequent than in a mobile setting, so that the problem of conflicts is
is put in place to reach an agreement between all parties; as a result
less pressing.
of context changes, a dynamic renegotiation of the contract may be
The software engineering community has investigated the is-
necessary. The approaches we have analysed usually target a spe-
sue of conflicts too. Software development environments [9, 7]
cific domain (e.g., multimedia applications over broadband cellular
have devised mechanisms for specifying consistency constraints
networks), mainly focusing on bandwidth allocation [3]. Moreover,
between artifacts. They are able to detect static violations of these
applications have a rather limited way of influencing the policies
constraints and resolve them automatically (e.g., by propagating
that are chosen to meet QoS requirements. Our middleware aims
changes to dependent documents). Inconsistencies are often found
at being general and uses reflection to give applications the power
in requirements documents, indicating conflicts between the dif-
to influence the way adaptation is achieved. This may lead to dis-
ferent stakeholders involved. Requirements management methods
agreements among applications to reach the quality-of-service level
and tools therefore include inconsistency detection and resolution
they wish.
mechanisms. The KAOS method [6] uses a goal-oriented approach
32

---

In this paper, we show how middleware can use microeconomic
determine which policy can be applied in the current context. Our
techniques effectively in order to solve conflicts that arise in the
model assumes that, at each time, the behaviour of the middleware
mobile setting, where new issues (e.g., dynamic adaptation to con-
with respect to a particular service is determined by one and only
text changes) and constraints (e.g., resource-scarce devices and low-
one policy, that is, a service cannot be delivered using a combina-
quality network connection) have to be considered.
tion of different policies. If different policies need to be combined,
a new name must be assigned to the combined policy, and this name
must be used in the profile. For example, the display of an image
3.
THE REFLECTIVE MODEL
can be done using a ‘B&W-Low’ policy, that is a combination of
The reflective middleware model we have developed (see [4] for
‘Black&White’ and ‘LowResolution’.
a full discussion) assumes a single user for each mobile device,
As both the needs of the user and the context change quite fre-
though there may be many applications running simultaneously on
quently (e.g., due to movement of the device to a different location),
that device, hence, on the same middleware instance. This assump-
we cannot expect application designers to foresee all possible con-
tion is reasonable for PDAs, mobile phones and digital cameras.
figurations. Here is where reflection comes into play. A reflective
Applications need to be aware of their execution context, in order
API is available that gives applications dynamic access to their own
to adapt to frequent and unannounced changes in the environment.
profile, so that changes in this information immediately translate
By context, we mean everything that can influence the behaviour of
into changes in the middleware behaviour.
an application, from resources internal to the device, such as mem-
ory, battery power, screen size and processing power, to resources
4.
DEALING WITH CONFLICTS
outside the physical device, such as bandwidth, network connec-
tion, location and other hosts within reach. The middleware is in
The model presented above allows applications to control the
charge of maintaining a valid representation of the execution con-
behaviour of the middleware based on current context. This is
text, by directly interacting with the underlying network operating
achieved by means of application profiles that can be dynamically
system.
changed through reflection. Although a middleware based on this
Applications may require some services to be delivered in dif-
model supports the development of context-aware applications, it
ferent ways (using different policies) when requested in different
also opens the door to conflicts. In our model, a conflict exists
context. For example, an image processing application may wish
when different policies can be used in the same context to deliver a
to display pictures in black and white when battery power is low,
service, so that the middleware does not know which one to apply
using full-size, full-colour pictures when battery power permits. In
(recall that we made the assumption that a service can be deliv-
our model, the middleware provides applications with a general
ered using only one policy at a time). Reflection gives applications
mechanism that enables dynamic customisation of service delivery.
the ‘intelligence’ that transparency takes away from them in tra-
The customisation takes place by means of what we call application
ditional middleware systems. Applications, however, may not be
profiles; Figure 1 shows their abstract syntax. Each application pro-
smart enough to cope with the new power, and may produce pro-
file defines associations between the services that the middleware
files that lead to conflicts. In particular, when setting up application
customises, the policies that can be applied to deliver the services,
profiles, the following two kinds of conflict may be generated.
and the context configurations that must hold in order for a policy
to be applied. In the example above, an association is defined be-
Intra-profile conflict: a conflict exists inside the profile of an ap-
tween the service ‘Display Picture’, the ‘Black&White’ policy, and
plication running on a particular device. This class identifies con-
a context where the resource ‘Battery Power’ is low, and another
flicts that are local to a middleware instance. Let us assume that
one between the same service ‘Display Picture’, the ‘FullColor’
we are running the image processing application described in Sec-
policy, and a context where ‘Battery Power’ is high. Profiles are
tion 3. The application may instruct the middleware to display an
passed down to the middleware; each time a service is invoked, the
image in black and white when the battery power on the device is
middleware consults the profile of the application that requests it to
low, and to load and display only fragments of the picture when
memory is low. What happens when, suddenly, both battery and
memory fall below the values specified in the profile? The middle-
ware checks which policy should be applied and determines that
serviceList
::= service serviceList | ε
more than one policy suits the current context. As we made the
service
::= sname policyList
assumption that each service is delivered using one and only one
policyList
::= policy policyList | policy
policy at a time, the middleware is stuck, unable to choose which
of the context-suitable policies to apply. This is an example of
policy
::= pname contextList
intra-profile conflict.
contextList
::= context contextList | context
context
::= resourceList
Inter-profile conflict: a conflict exists between the profiles of ap-
resourceList
::= resource resourceList | ε
plications running on different devices. This class identifies con-
resource
::= rname oname valueList
flicts that are distributed among various middleware instances. As
valueList
::= value valueList | ε
a particular example of inter-profile conflict, we consider the case
in which a conflict arises between applications running on two dif-
ferent devices. This scenario is typical of a mobile setting, where
Figure 1: Application profile’s abstract syntax. sname ∈ S,
interactions take place between peers. Let us assume that we are
pname ∈ P, rname ∈ R, being S, P, R ⊂ Σ∗, respectively, the
running an instance of a calendaring application on our PDA; when
sets of all valid service/policy/resource names over our alphabet
meeting a colleague who is running the same application on his/her
Σ. value ∈ V, being V the set of all possible values of resources
PDA, we want to synchronise our diary entries. However, the appli-
in R (e.g., IP addresses for hosts in reach, etc.); oname ∈ O,
cation profiles on the two hosts may conflict in the following way.
being O the set of all valid operator names that can be applied
While one of the two application instances may wish to synchronise
to values of monitorable resources (e.g., equals, lessThan).
data with its peer bidirectionally, regardless of the current execution
33

---

context, the other one may prefer to communicate its updates to the
on the basis of private state, revealing only offers and acceptance
peer, without getting the peer updates back, when memory avail-
of the offers made by others. Applications may vary greatly in their
ability is scarce. If the two hosts meet when the memory available
preferences and decision processes. An auction permits greater de-
on the second device is less than the amount specified in the pro-
grees of heterogeneity than simpler schemes.
file, they will not agree on which protocol to use to synchronise
The question we have to answer next is which auction protocol
their data. We call this situation an inter-profile conflict. A par-
to use. This is known in microeconomic theory as a mechanism
ticular case of inter-profile conflict happens when applications run
design problem [16]. A protocol, or mechanism, consists of a set
on the same device (i.e., on the same middleware instance); we re-
of rules that govern interactions, and by which agents (i.e., our ap-
fer to this situation as an N-on-1 (i.e., N applications on 1 device)
plications) will come to an agreement. It constraints the deals that
conflict.
can be made, as well as the offers that are allowed. We contend that
the auction protocol we have designed can be successfully applied
None of these conflicts can be detected and resolved statically,
in a mobile setting, where the requirements listed in Section 4 must
that is, at the time the profile is written by the application and
be satisfied.
passed down to the middleware. A possible static approach would
In the remainder of this section, we describe the details of the
require us to check whether there is any intersection between the
auctioning mechanism we propose to resolve conflicts in a mobile
different contexts of the policies associated with each service. Due
environment, and discuss why this mechanism achieves the require-
to the complex nature of context (the number of monitored re-
ments listed before.
sources may be large), a static conflict analysis would produce an
explosion in the number of contexts that must be checked, and
5.1
The Protocol
would require a consumption of resources (especially in terms of
The rules of our auction are very simple: given a setting with N
battery, memory and processing power) that portable devices can-
agents that must make a collective choice from a set of P possible
not bear. As for inter-profile conflicts, the situation is even worse;
alternatives, each agent submits a single sealed bid for each element
mobile devices connect opportunistically and sporadically. We can-
in P . The auctioneer collects the bids and selects the alternative in
not foresee which devices are going to be encountered and, even so,
P that maximises social welfare, that is, the alternative with the
we cannot assume that all of them will be connected and in reach at
highest sum of bids received. Each agent then pays the auctioneer
the time a profile is modified; that is, the middleware cannot check
an amount of money that is proportional to the bid they placed on
whether the new configuration is conflict-free.
the winning alternative.
As a consequence, a dynamic solution is needed: conflicts may
In our scenario, the role of the auctioneer is played by the mid-
exist inside or among profiles, but both applications and middle-
dleware, which we assume is a trusted entity whose code and be-
ware can live with these conflicts until a service which incorpo-
haviour cannot be interfered with. Applications are the agents, and
rates a conflict is invoked. When this happens, the middleware
the good they are competing for is the application of the policy they
has to resolve the conflict using an appropriate mechanism. This
value most, among a set of alternatives that correspond to the poli-
mechanism must be simple, that is, only a low computation and
cies that can be applied in a particular context to deliver a service.
communication overhead should be imposed, as hand-held devices
As previously said, the aim of the middleware is not to select the
have limited resources that cannot be wasted by our conflict resolu-
policy that received the highest bid (i.e., the one that maximises the
tion mechanism. Moreover, it must be customisable, that is, it must
selling price), but rather the policy that satisfies the largest num-
be possible for the applications to influence the conflict resolution
ber of applications involved in the conflict. This is due to the fact
mechanism, and determine which policy is applied and which oth-
that we are considering scenarios where applications are participat-
ers are discarded.
ing in the delivery of the same service, rather than competing for
In the following section, we formally describe a conflict resolu-
it (i.e., the service will be delivered to all of them, not only to one
tion mechanism that meets these requirements.
or some of them). In these collaborative, or at least compromise,
scenarios, a solution that satisfies on average all the applications is
5.
MICROECONOMIC MECHANISM
preferred to one that maximises the revenue of a single one.
When applications that participate in the delivery of a service
Our auction has been inspired by traditional sealed bid auctions
do not agree on which policy must be applied, a conflict resolu-
(e.g., first-price and second-price sealed bid auction [23]). Unlike
tion scheme is necessary to resolve the dispute. The conflict res-
ascending bid auctions, such as the standard English auction [18],
olution mechanism we propose is based on microeconomic tech-
where the auctioneer continuously raises the price of the good un-
niques. The motivating idea is that a mobile distributed system
til only one bidder is willing to meet the price called, sealed bid
can be seen as an economy, where a set of consumers must make
auctions consist of a one-step bid that cuts down the computation
a collective choice over a set of alternative goods. Goods rep-
and communication costs when the auction is distributed over space
resent the various policies that can be used to deliver a service
and time, as in our mobile setting. This meets our requirement of
(not the resources needed to apply a policy); for example, policies
simplicity. We will show in Section 5.2 how customisation is met
‘Black&White’, ‘FullColor’ and ‘LowResolution’ are the goods as-
by our auctioning mechanism.
sociated to service ‘DisplayPicture’. Consumers are applications
In the following, we provide the details of how our auctioning
seeking to achieve their own goals, that is, to have the middleware
mechanism works in a mobile distributed setting. To avoid confu-
delivering a service using the policy that achieves the best quality
sion between an application (which may exist on different devices)
of service, according to application-specific preferences.
and an application instance (which runs on a particular device), we
Simple schemes include, for example, priority assignment or per
will identify an application instance and the device it is executing
capita distribution. However, those do not suit situations where par-
on as a ‘peer’1. Peers are partners in the communication process.
ticipation in exchange of goods is voluntary on the part of all parties
We call PEERS the set of all possible peers. Under these assump-
(i.e., the applications), so that action requires a consensus and mu-
tions, the auctioning process can be formalised as follows.
tual perception of benefit. A better scheme would use an auction
protocol. Auctions allow parties to make decisions independently,
1We do not refer here to the characteristics of peers in P2P networks.
34

---

how much each peer valued the use of each agreed policy:
Initialisation
B∗ = B[|{p
As part of an initialisation process, for every peer peer
1, . . . , pm}|]{peer1,...,peern}
i, i ∈ [1, N ],
a utility function u
+
i : P →
that represents the user’s goals
being B the semantic function shown in Figure 4.
Ê
(e.g., minimisation of consumption of resources, maximisation of
quality of service, etc.) can be determined. Peers use their utility
Election of the Winner
functions to find out how much to value the use of a policy pj ∈ P
From the set B∗, middleware instances participating in the conflict
during an auction, that is, ui(pj) = ui,j. Each peer is also as-
resolution process select the winning policy p˜ as the one with the
signed a quota qi by its middleware. The quota qi represents the
highest sum of the bids placed:
maximum amount of money that peeri can bid during a bidding
p
process, that is, the bid placed by peer peer
˜
 = W [|B∗|]
i on policy pj is a num-
ber bi,j = min{ui,j , qi}.
being W the semantic function defined in Figure 5. As shown,
before policy p˜ is actually applied, each peer pays an amount of
Service Request
money that is proportional to the ‘added’ benefit obtained by ap-
Whenever an application asks the middleware to execute a service,
plying the winning policy over the other peers. To understand how
a command like the one illustrated below is issued:
payment is split, let us consider three peers x, y and z, who bid
respectively bx < by < bz on a winning policy p. Applying p
command
::= sname peerList
gives an equal benefit of bx to each peer; moreover, y and z share
peerList
::= peer peerList | peer
an added benefit of by − bx over x, and z enjoys an extra ben-
efit equal to bz − by over both x and y. Our payment scheme
being sname ∈ S the name of the requested service, and peerList
demands that x, y and z pay respectively 0, (by − bx)/2, and
the set of peers involved in the service execution.
(by − bx)/2 + (bz − by)/1. Note that, if the winning policy is
Assuming that service sname requires the cooperation of n ≤
the one that has been valued most by all peers, then no payment
N peers, each peer (or, better, the middleware instance operating
is demanded, as there was no real conflict to be solved. Note also
on the device of the peer) computes Pi as the set of policies that
that, in case of intra-profile conflicts, the payment is always zero,
the above running application instance Ai has associated to service
as the winning policy is never ‘imposed’ on anyone, that is, there
sname in its profile, and that can be applied in the current context
is no added benefit over anyone. The rationale for this payment
(i.e., according to current resource availability). More formally, Pi
scheme is that applications are not paying for the resources they
can be defined as follow:
use when applying a policy, but, rather, for the (added) quality-of
service level they get from it. We assume that ties are broken by se-
Pi = F[|serv(sname, peeri)|]Env(peeri)
lecting a policy randomly (i.e., a k-way tie is decided by flipping a
‘k-sided coin’, where each policy is chosen with probability 1/k).
being F the semantic function defined in Figure 2; serv : S ×
PEER → service a function that, given a service name and a
If a service sname is requested that requires the cooperation of a
peer, returns the corresponding service specification, and Env :
PEER → E
set of peer peerList, then the whole conflict resolution mechanism
a function that computes the current execution envi-
can be summarised as follows:
ronment of a peer.
G : command → P
Computation of the Solution Set
G[|sname peerList|] =
Middleware instances then cooperate to compute the solution set
W [| B [| I[|sname|]
P ∗, that is, the set of policies that all peers involved in the execution
{peerList} |]{peerList} |]
of the service have agreed upon:
A service request may then produce one the following two results:
P ∗ = I[|sname|]
• G[|sname peerList|] = pname: service sname is deliv-
{peer1...peern}
ered using policy pname (either because all peers agreed on
being I the semantic function described in Figure 3.
the policy, or because pname was the policy valued most
If the cardinality of P ∗ is zero, that is, the solution set is empty,
during a conflict resolution process);
a conflict exists that cannot be solved, as peers do not agree on
• G[|sname peerList|] = : the service request fails as no
a common policy to be applied; the conflict resolution process is
policy can be found that is both agreed by all peers and valid
terminated with a failure and peers are notified. If the cardinality is
in the current context.
exactly 1, there is an agreement on the policy to apply (i.e., there
is no conflict). Finally, if the cardinality is greater than 1, there is a
The auctioning mechanism has been described in the general
conflict that can be resolved using one of the policies in P∗. In this
situation where there are different applications running on differ-
case, the auctioning process proceeds as below, to decide which of
ent hosts (inter-profile conflict). N -on-1 conflicts are detected and
these policies should be applied.
solved in the same way as inter-profile conflicts. However, as the
application instances involved are running on the same host (i.e.,
Computation of Bets
on the same middleware instance), no communication overhead is
For every peer peeri participating in the communication process,
required, and the solution set P ∗ can be computed locally. Intra-
and for every agreed policy pj ∈ P ∗, j ∈ [1, m], a bet bi,j is com-
profile conflicts can be considered a degeneration of inter-profile
puted, based on the peer’s utility function ui and quota qi. Unlike
conflicts, where the number n of bidders is 1, and the solution set
‘human’ auctions, we make the assumption that all peers partici-
coincides with P1 (i.e., the set of policies that can be applied in the
pating in a bidding process bid a price, that is, they cannot refuse to
current execution context, according to peer1’s application profile).
bid. Middleware instances of bidding peers exchange the bids they
The auction proceeds as described above, selecting the policy that
have received, ending up with a merged set of tuples B∗ specifying
maximises peer1’s utility, without communication costs.
35

---

F
:
service → E → ℘(P)
F[|sname policyList|]e = F[|policyList|]e
F[|policy policyList|]e = F[|policy|]e ∪ F[|policyList|]e
F[|pname contextList|]e = {pname} if valid[|contextList|]e =
∅
if valid[|contextList|]e = ⊥
valid
:
contextList → E → bool
valid[|context contextList|]e
= valid[|context|]e ∨ valid[|contextList|]e
valid[|context|]e
= valid[|resourceList|]e
valid[|resource resourceList|]e
= valid[|resource|]e ∧ valid[|resourceList|]e
valid[|rname oname valueList|]e
= eval((rname, oname, valueList), e)
valid[|ε|]e
=
Figure 2:
Application profile semantics.
E
=
℘(R × V) represents the set of all possible execution con-
texts (e.g,
{(Memory, 8), (Battery, 4)}); eval is a boolean function that returns true if the value of resource
rname in the execution context e is among the values obtained by applying the operator oname to valueList (e.g.,
eval((Memory, inBetween, [2, 7]), {(Memory, 6)}) =
, while eval((M emory, lessT han, [5]), {(M emory, 6)}) = ⊥).
I
:
S → ℘(PEER) → ℘(P)
I[|sname|]{peer peerList} = I[|sname|]{peer} ∩ I[|sname|]{peerList}
I[|sname|]{peer} = F[|serv(sname, peer)|]Env(peer)
Figure 3: Semantics of the computation of the solution set
B
:
℘(P) → ℘(PEER) → ℘(P × PEER × +)
Ê
B[|{p1, . . . , pm}|]{peer peerList} = B[|{p1, . . . , pm}|]{peer} ∪ B[|{p1, . . . , pm}|]{peerList}
m
B[|{p1, . . . , pm}|]{peer} =
{(pj, peer, min{qpeer, upeer,j})}
j=1
B[|{p}|]{peerList} = {(p, , 0)} No conflict
B[|∅|]{peerList} = ∅
No agreement
Figure 4: Semantics of the computation of bets
W
:
℘(P × PEER × +) → P
Ê
W[|{(pj, peeri, bi,j), ∀i ∈ [1, n], j ∈ [1, m]}|] = p˜ |
p˜ ∈ {π1(pj , peeri, bi,j), ∀i ∈ [1, n], j ∈ [1, m]}
n
n
∧
π3(p˜
) = max
, peeri, bi,˜

π3(pj, peeri, bi,j )
j∈[1,m]
i=1
i=1
∧ pay(qmw(i), fi, qi), ∀i ∈ [1, n]
a. 0 if ∀k ∈ [1, n] π3(p˜
) = max
)
, peerk, bk,˜

j∈[1,m] π3(pj , peerk, bk,j
where fi =
b È
b
.
l,˜
−max( {bs,˜
|bs,˜
<bl,˜
, s∈[1,n]}∪{bmin,˜
} )
l∈{s|s∈[1,n] #{b
∧b
s,˜
|bs,˜
≥bl,˜
, s∈[1,n]}∗#{bs,˜
|bs,˜
=bl,˜
, s∈[1,n]} ,
s,˜
≤bi,˜
}
b
= min
min,˜

{bi,˜, i ∈ [1, n]} otherwise
W[|{(p, , 0)}|] = p No conflict
W[|∅|] =
No agreement
Figure 5: Semantics of the election of the winning policy. πi(a1, a2, . . . , an) = ai is a function that projects a tuple onto the ith
value; #{a1, a2, . . . , an} = n is a function that computes the cardinality of a set; qmw(i) is a function that retrieves the quota of the
middleware on top of which peer peeri is executing; finally, pay(q1, x, q2) = (q1 + x, q2 − x) is a function that both increases the
middleware quota q1, and decreases the peer’s quota q2, of the specified amount.
36

---

Once a conflict has been detected and resolved using the auc-
tioning mechanism presented above, no further action is taken. The
uf unction
::= addendList
conflict cannot be removed as it is not usually local to a profile but
addendList
::= addend addendList | addend
distributed among the profiles of different peers. If the peers in-
addend
::= cb name weight
volved change, or if the context changes, there may be no conflict
at all. Also, we assume that each auction is carried on in isola-
Figure 6: Utility function abstract syntax
tion: a peer cannot expect that its behaviour will in any way affect
a future conflict or, similarly, that it will behave in a particular way
based on its interaction history (i.e., we cannot assume that next
each conflicting policy p
time the same conflict arises, the winning policy will be the same
j . The semantics of a utility function is
presented in Figure 7. As shown, each value is normalised to vary
one, as the result depends on current peer quotas, utility functions
in a range [0, 1], so that different bets can be effectively compared,
and application profiles). Each conflict resolution process stands
and money fairly redistributed (see Section 5.3).
therefore alone.
As stated before, while policy specifications are fixed, utility
There are some questions that need to be answered about the
function specifications change over time, as they have to reflect
process described above; in particular, how is an utility function
current user’s needs. This implies that the reflective API of our
defined, and how is the quota managed by middleware? We answer
middleware (see Section 3) has to allow dynamic modification of
these questions in the following sections.
utility function specifications. This allows our conflict resolution
5.2
Utility Function
scheme to achieve also the second requirement we aimed to, that
is, customisation.
Whenever a conflict is detected, either inside a profile (intra-
Note that, to avoid incompatibility among the prices bid during
profile conflict) or among various profiles (inter-profile conflict),
a conflict resolution process, utility functions are locked at the be-
user’s goals, such as maximisation of the quality of the display for
ginning of an auction, and cannot be modified until the auction
an image processing application, or directionality of data synchro-
finishes. Thus, applications cannot ‘cheat’ and associate high bids
nisation for a calendaring application, must be taken into account.
to the policies they value most, while bidding zero for the others,
In other words, users should be allowed to influence the conflict
to increase the chances to have the policy they value most finally
resolution process operated by the middleware as they are the only
applied, as this would require applications to change the weights of
ones who know what their goals are at the moment and how differ-
their utility functions during the auction.
ent outcomes are valued.
Utility functions serve this purpose. A utility function ui trans-
5.3
Quota Allocation
lates user’s goals with respect to peer peeri into a value ui,j that
represents the price the user is currently willing to pay to have pol-
When describing the rules of our mechanism (see Section 5.1),
icy p
we specified that each peer peer
j applied, that is, to have its goals fulfilled. The following
i is allowed to bid a value bi,j for
holds:
policy pj, given that this value is lower than its current quota qi.
We now explain how this quota is managed.
ui,j ≥ 0, ∀i ∈ [1, n], j ∈ [1, m].
Whenever an application instance Ai is started, an initial quota
q
As in ‘human’ auctions, values cannot be negative; a value u
i = qinit is awarded. Each time Ai participates in a bidding pro-
i,j = 0
cess, its current quota is decreased by an amount equal to f
means that policy p
i ∈
j is not relevant to peer peeri, that is, applying
[0, 1], as defined in Figure 5. A
p
i’s underlying middleware instance
j does not give any benefit to peeri (this is a plausible ‘machine’
collects A
representation of a ‘human’ “refuse to bid”).
i’s payments and stores them in a wallet q(i). We assume
that there is no flow of money from one middleware instance to
Utility functions change dynamically to reflect changes in the
another (i.e., each application instance pays its underlying middle-
user’s goals; however, the value they return is computed over static
ware). Moreover, we assume that there is no explicit utility transfer
policy specifications that estimate the consumption of resources
among applications (e.g., no money can be transfered to a peer to
that applying the policy entails, and the benefits it gives in terms of
compensate for a disadvantageous agreement).
quality of service. If R ⊂ Σ∗ defines the set of resource names that
Every t time units, each middleware instance redistributes the
the middleware monitors, and Q ⊂ Σ∗ the set of benefits achieved
money it has collected in its wallets q(i), i ∈ [1, n], to the various
by applying policies in P, then a policy specification can be de-
application instances A
scribed as a domain set:
i, i ∈ [1, n]. The amount of money each
application instance gets back is in direct relation to the number of
PSPEC = ℘({R ∪ Q} × level)
interactions it has been involved during the last t time units, and
in inverse relation to the amount of money it bid. We define an
being level ::=
1 | . . . | LMAX an estimate of resource con-
interaction as a service request which incorporates an inter-profile
sumption/benefit achieved that the policy developers compute be-
conflict (intra-profile conflicts are excluded from the quota recharg-
fore delivering the policy.
ing as no flow of money occurs).
The abstract syntax of a utility function is given in Figure 6,
In particular, if we indicate with Nt(i) the number of interactions
where cb name ∈ (R ∪ Q) is a name that uniquely identifies a
in which application instance Ai was involved during the last t time
resource or benefit inside a policy specification, and weight ::=
units, then the recharging process is carried out as described below:
1 | . . . | WMAX is a factor that represents the importance the
user gives to a particular resource/benefit (the higher the weight,
q
the more important the resource/benefit). In this paper, we do not
i
= qi + q(i) − q(i)
Nt(i)
discuss how weights, that represent user’s needs as faithfully as
possible, can be generated, as we consider this issue a matter of
q(i) =
q(i)
N
future research.
t(i)
Whenever a peer peeri is involved in a bidding process, its utility
function is retrieved and used to find the peer’s evaluation ui,j for
being q(i) the money currently stored by the middleware in the
37

---

U
:
uf unction → PSPEC →
+
Ê
U[|addend addendList|]ps = U[|addend|]ps + U[|addendList|]ps
U[|cb name weight|]ps = intval(S[|cb name|]ps) ∗ intval(weight) ,
LM AX ∗ W M AX ∗ RQM AX
Figure 7: Semantics of an utility function. S : (R ∪ Q) → PSPEC → level is a function that, given a resource/benefit name
cb name, and a policy specification ps, fetches the level associated to cb name in ps (if the utility function tries to retrieve a value for
a resource/benefit that does not appear in the policy specification, we consider a value of 0). intval is a function that given a literal
in { 1 , . . . , MAX }, returns the corresponding integer value in [1, MAX]; LM AX ∗ W M AX ∗ RQM AX is the maximum bid an
application can place, being RQM AX the maximum number of resources/benefits of interest to an application.
wallet associated to Ai, and qi equals to Ai’s current quota.
strate an optimal choice for qinit, qmax, t and α.
This quota redistribution scheme discourages dictatorial interac-
This concludes the discussion about our auctioning approach to
tions: if an application instance bids very high in a few interac-
the conflict resolution problem. In the following section, we il-
tions, ‘imposing’ its preferred policy over the others, then only a
lustrate how this mechanism can be instantiated and used to solve
very low amount of money is returned during a recharging process.
conflicts.
The only way to get money back from the middleware is to par-
ticipate in other interactions in a more cooperative fashion (i.e., by
6.
EXAMPLE
bidding lower and interacting more). For example, let us assume
In this section, we present an example of inter-profile conflict
that at time t0, two applications instances A1 and A2 are started
using an instant messaging application on top of our reflective mid-
and awarded the same quota qi = 3, i ∈ {1, 2}. During the follow-
dleware, and show how our auctioning mechanism can be success-
ing t time units, they are involved in a number of interactions that
fully applied to resolve it.
cost them altogether the same amount of money; however, while
One of the services that our instant messaging application can
A1 bid aggressively, paying a lot of money in few interactions, A2
customise is the way messages are delivered among peers that have
was more cooperative, paying low amounts in many interactions.
started a chat. In particular, our middleware provides four different
As a result, our quota redistribution scheme returns money to A2
policies among which the application can choose: a SendChar
faster than to A1 (see Figure 8).
policy, which is used to deliver to the peers a character at a time;
The approach to quota redistribution that we have described could
a SendLine policy, which is used to deliver to the peers a line
be defined as ‘conservative’: at any time, the money associated
of characters at a time; a SendZippedLine policy, which first
to an application instance Ai are the same, although split differ-
compresses a line of characters and then sends it to the peers, and
ently between its current quota qi and the corresponding middle-
finally a SendEncryptedLine policy which first encrypts and
ware wallet q(i). In other words:
then sends a line of characters to the peers. Each of these policies
q(i) + q
requires a different amount of resources to be used (in particular,
i = qmax
battery and bandwidth), and achieves a different quality of service
being qmax a fixed amount that is the same for any application. At
(in terms of availability and privacy of the message). The corre-
time t0 when an application instance Ai is started, different choices
sponding policy specifications are shown in Figure 9.
of qinit and q(i) are possible. In particular, any assignment that
complies with the following equations is acceptable:
SendChar
{(Battery,4),(Bandwidth,10),(Availability,10)}
SendLine
∀α ∈ [0, 1]
qinit = α · qmax
{(Battery,3),(Bandwidth,6),(Availability,7)}
q(i) = (1 − α) · qmax
SendZippedLine
{(Battery,5),(Bandwidth,4),(Availability,5)}
Setting α = 1 favours newly started application instances, while
SendEncryptedLine
setting α = 0 favours applications that have been executing for
{(Battery,6),(Bandwidth,7),(Availability,4),(Privacy,10)}
a long while. The differences among these possibilities disappear
while time passes. It is beyond the scope of this paper to demon-
Figure 9: Policy specifications
Time / Action
q1
q(1)
q2
q(2)
Let us suppose that three peers peer1, peer2, and peer3 get in
t0 / Start
3
0
3
0
reach of each other and want to start a chat. In order to do so,
t
we assume they have to agree on a common policy to be applied
1 / Bid
2.1
0.9
2.7
0.3
t
to exchange messages. During the lifetime of the chat, the policy
2 / Bid
1.2
1.8
2.4
0.6
t
used may change to adapt to new context configurations where the
3 / Bid
2.1
0.9
t
currently used policy is no longer suitable. However, when this
4 / Bid
1.8
1.2
happens, all the chatting peers must agree on the new policy to use.
t5 / Bid
1.5
1.5
The peers’ application profiles are represented in Figure 10. The
t6 / Bid
1.2
1.8
first peer enables each of the four policies in different contexts; the
t7 / Redistribution
2.1
0.9
2.7
0.3
second peer prevents the use of the two heaviest policies, Send-
Char and SendEncryptedLine; finally the third one prevents
the use of SendChar, while leaving SendLine always enabled
Figure 8: Example of quota redistribution (with t7 − t0 = t)
(there is in fact no context associated to it). Leaving one or more
38

---

% peer 1
% peer 3
SendMessage
SendMessage
Assuming that each peer has a quota qpeeri > 1 (i.e., the bid is not
SendChar
SendLine
constrained by current quota, as each bid bi,j ∈ [0, 1]), we obtain:
Bandwidth > x1
SendLine
SendZippedLine
B[|{SendLine, SendZippedLine}|]{
Bandwidth < x1
Bandwidth < x3
peer1,peer2,peer3} =
{(
SendZippedLine
SendEncryptedLine
SendLine, peer1, 0.275), (SendZippedLine, peer1, 0.22),
Bandwidth < x1/2
Battery > y3
(SendLine, peer2, 0.2125), (SendZippedLine, peer2, 0.2225),
SendEncryptedLine
(SendLine, peer3, 0), (SendZippedLine, peer3, 0) }
Battery > y1
% peer 2
Election of the winner
SendMessage
Bids received for each policy in the solution set are added, and the
SendLine
policy that maximises the sum (i.e., social welfare) is selected:
Battery < x2
SendZippedLine
Bandwidth < y2
peer1
peer2
peer3
SendLine :
0.275 +
0.2125 +
0 =
0.4875
SendZippedLine :
0.22 +
0.2225 +
0 =
0.4425
Figure 10: Application profiles
Therefore:
% peer 1
% peer 2
% peer 3
Battery
4
Battery
7
Privacy
10
W[| B[|{SendLine, SendZippedLine}|]{peer1,peer2,peer3}|]
Bandwidth
3
Bandwidth
9
= SendLine
Availability
10
Finally, each peer’s quota is adjusted in the following way:
Figure 11: Utility function specifications. peer1 aims at max-
q
− 0.2125 − 0 − 0
imising availability without wasting to many resources; peer
1
= q1 − 0.275 − 0.2125
2
1
2
3
aims at minimising resource consumption, and peer3 aims at
− 0
maximising privacy.
q2
= q2 − 0.2125 − 0
2
3
0
q3
= q3 − 3
policies always enabled is a good way to reduce the risk of ending a
conflict resolution process with a failure because no agreed policy
could be found. However, this increases the risk of conflicts and,
therefore, the time used to resolve them (which is anyway rather
7.
IMPLEMENTATION AND EVALUATION
low, as it will be shown in the next section). It is up to the applica-
We have implemented our middleware in Java that supports the
tion to decide which strategy is best.
full reflective model and the conflict resolution mechanism described
Assuming that the utility functions are the ones shown in Fig-
in this paper. We have also developed an instant messaging appli-
ure 11, and that the current execution context enables the following
cation on top of it and ran tests on a Compaq iPAQ PDA running
sets of policies:
Linux. Application profiles and utility functions have been encoded
using the eXtensible Markup Language (XML). We chose to use
P1 = {SendLine, SendZippedLine, SendEncryptedLine}
XML as we believe this language may enhance context-aware and
P2 = {SendLine, SendZippedLine}
user-driven interactions between middleware and applications, sup-
P3 = {SendLine, SendZippedLine, SendEncryptedLine}
porting a representation of information that is both easily manipu-
latable by machines and readily understandable by humans.
for peers peer1, peer2 and peer3 respectively, then the conflict
The middleware platform currently requires less than 250Kb of
resolution process proceeds as described below.
persistent storage, and less than 800Kb of memory (without con-
sidering the memory required by the Java Virtual Machine). We
Computation of the solution set
have measured the average time required to start a service, with and
without conflicts. We have experienced no time increase in the case
I[|SendMessage|]{peer1,peer2,peer3} = P1 ∩ P2 ∩ P3
of intra-profile conflicts, and an increase of around 20% (450ms
= {SendLine, SendZippedLine}
instead of 365ms) in case inter-profile conflicts between two peers
were detected and solved (with only 300 bytes of information sent
around). In both cases, there was no human perception of the delay
Computation of bets
as most of the time is taken by the loading and provisioning of the
High weights associated to resources in utility function specifica-
service.
tions mean that the user aims at sparing resources; however, pol-
In our auctioning scheme, the role of the auctioneer can be played
icy specifications estimate the amount of resources consumed, not
by more than a middleware instance at the same time, as bidders
spared. In order to give higher scores (i.e., higher bid prices) to the
may be distributed across different machines (inter-profile conflicts);
policies that reduce resource consumption, we therefore need to
this requires cooperation among all the middleware instances in-
compute the value: LMAX− expected consumption. For example,
volved, to compute the solution set and to exchange bids. The com-
if we assume LMAX= 10, WMAX= 10, and RQMAX= 4
munication paradigm we are currently using requires that all the
(i.e., battery, bandwidth, availability and privacy), then:
peers remain connected while the conflict resolution mechanisms
is performed, otherwise a failure is reported. We plan to investigate
(10 − 3) ∗ 4 + (10 − 6) ∗ 3 + 7 ∗ 10
and develop different communication paradigms that allow our auc-
upeer (
1 SendLine)
=
10 ∗ 10 ∗ 4
tioning protocol to be resilient even in the presence of individual’s
= 110/400 = 0.275
disconnections.
39

---

8.
CONCLUSION AND FUTURE WORK
2001. The Third International Conference on Metalevel Architectures
In this paper we presented a microeconomic approach to conflict
and Separation of Crosscutting Concerns, volume 2192 of LNCS,
pages 126–133, Kyoto, Japan, Sept. 2001.
resolution in a mobile setting. In particular, we modelled a mo-
[5] D. Chalmers and M. Sloman. A Survey of Quality of Service in
bile distributed system as an economy where applications compete
Mobile Computing Environments. IEEE Communications Surveys,
to have a common service delivered according to their preferred
2(2), 1999.
quality-of-service level; in this economy, middleware plays the role
[6] A. Dardenne, A. van Lamsweerde, and S. Fickas. Goal-Directed
of an auctioneer, collecting bids from applications and selecting the
Requ