Many applications are being built by integrating multiple distributed components in order to implement a particular business function. The increasing popularity of component programming models, such as JavaBeans**¹ and Web services,² is predicted to further accelerate the adoption of component-based development (CBD).

An impediment to the adoption of CBD, however, is the inability of the “user” of the components to optimize their performance for use in a particular solution. Web services, with its premise of loosely coupled distributed components working together, makes this issue even more acute, as the development, deployment, and maintenance of components making up a single solution may come from different vendors and run in very different system environments.¹

In this paper, we propose a generic framework that addresses this issue. In our formulation, an adaptive component has multiple implementations, each optimized for a particular request workload. A mechanism for switching between implementations is also provided. The underlying system monitors the current request workload for a given component and adaptively switches to the implementation best suited to this workload. By shifting more of the performance optimization burden to the component, performance tuning is simplified and the resulting overall system performance is likely to be improved. Additionally, by having the system monitor the request workload and dynamically switch implementations based upon current usage patterns, the component can better accommodate changing request patterns.

Because switching between implementations can incur a heavy cost, good algorithms are needed for determining, at run time, when to switch between implementations. We call this the adaptive component problem. This paper describes an algorithm, named Delta, for the case when there are exactly two implementations. We show that Delta is (3 + )-competitive. This algorithm is designed for the case when the cost of switching between implementations is very large compared to the cost of processing a single request. In this case, the value of is guaranteed to be very small. Because we also show a 3-competitive lower bound, this algorithm is close to optimal.

We show the applicability of this framework to two problems. The first is an adaptive version of the distributed pub/sub problem, where multiple loosely coupled components are reading and writing from a shared data repository. A component can either read and write to this shared repository or create a local data cache for fast access. The second example is an adaptive version of the data structure selection problem, where an application must choose the appropriate internal data structure to use in order to provide the quickest answer to particular queries. We show that both of these are instances of the adaptive component problem and that Delta can be used to decide when to switch implementations, thus optimizing run-time performance. This illustrates the applicability of our framework to a wide range of problems.

Here is an outline for the rest of this paper. The next section “The adaptive component problem” is followed by “The Delta algorithm.” Then, the section “Examples” contains our two case studies. In the section “Competitiveness” we prove that Delta is (3 + )-competitive, and in the section “Lower bounds,” we establish a 3-competitive lower bound for this problem. The section “Related work” is followed by “Summary and open issues.”

The adaptive component problem

We propose a model where the component developer implements multiple versions of a component, each optimized for a specific request workload. The developer also writes the code that controls the switching between implementations at run time. For each request type that the component can service, and for each implementation of that component, we determine the cost for processing a request of that type. We similarly determine the cost of switching between any two implementations. These costs may be specified by the component developer or may be derived empirically (e.g., by profiling). An on-line algorithm will monitor request workloads at run time and determine when to switch implementations. The rest of this section formalizes these concepts and defines an optimality criterion for determining when to switch implementations.

Let Comp be an adaptive component, and let ReqTypes = {typ_i} be the set of request types that Comp can process. Let Impls = {impl_j} be the set of implementations of Comp, with impl₁ being the default implementation. Let Cost:ReqTypes × Impls → R be the function that gives the cost for Comp to process a request of a given type using a particular implementation (R denotes the set of reals). Let SwitchCost:Impls × Impls → R be the function that determines the cost in Comp of switching from one implementation to another. SwitchCost(impl_i, impl_j) = ∞ iff Comp cannot switch from impl_i to impl_j. The cost functions may reflect internal computation costs, network message costs, or a combination of these and other metrics, depending upon the application environment.

We represent the computation to be performed as a sequence of requests, r₁, …, r_k. The empty sequence is denoted by . To facilitate the modeling of many different sorts of problems, we allow a single request to be processed by either a single component or by multiple components. Given such a sequence of requests, a switch of implementations may occur after processing any request in the sequence. We represent this by the operation switch(impl_i, impl_j), where impl_i is the current implementation of the component, and impl_j is the implementation being switched to. Hence, given a sequence of requests = r₁, …, r_k, we model the adaptive behavior of the component Comp as transforming this sequence to the sequence ' = s₁, …, s_f such that the following comments are true:

• For 1 ≤ i ≤ f, either s_i is a request or s_i is a switch operation.
• Removing the switch operations from ' produces .
• If s_m = switch(impl_j, impl_k) then either s_m is the first switch operation in the sequence and j = 1 or the closest preceding switch operation in the sequence is of the form switch(impl_i, impl_j).

An on-line algorithm is one that transforms the sequence by deciding whether or not to insert a switch operation after request r_i based only upon the sequence seen so far, r₁,  …,  r_i. We  write →_A ' to indicate that on-line algorithm A (used by Comp) maps into ' when processing it. For any request s_i in the transformed sequence ', we say that the implementation impl_k is active at s_i if the closest switch operation preceding s_i in the sequence is of the form switch(impl_j, impl_k), or k = 1 and there is no switch operation preceding s_i. When algorithm A and sequence are understood from the context, we simply denote this by ImplIs(s_i, impl_k).

Cost^A is the cost of Comp to process request sequence using algorithm A.
Cost^A = Cost(') =∑ⁿ_i=1 C(s_i) where →_A ' = s₁, …, s_n and where

C(si) =		Cost(si, implk)	if si is a request, and implIs(si, implk);
		SwitchCost(implj, implk)	if si is the operation switch(implj, implk).

Let O be an optimal algorithm; that is, for any sequence and any on-line algorithm A, Cost^O ≤ Cost^A. An on-line algorithm A is c-competitive^3,4 iff, for any sequence , there exist constants c and d such that Cost^A ≤ c*Cost^O + d. Given Comp, RegTypes, Impls, Cost, and SwitchCost, the adaptive component problem is to find an on-line competitive algorithm for this problem instance, that is, to find a c-competitive algorithm for some constant c.

Now consider a special case of the adaptive component problem where Impls = {impl₁, impl₂}, which we call the adaptive two-implementation-component problem (the adjective “adaptive” is sometimes omitted, for conciseness). We assume that there is at least one request r such that Cost(r, impl₁) < Cost(r, impl₂), and at least one request r' such that Cost(r', impl₁) > Cost(r', impl₂). Also, we assume that there are no constraints on the order in which requests must be composed in a sequence (i.e., any interleaving of requests is a legitimate request sequence).

Let SC₁ = SwitchCost(impl₁, impl₂), SC₂ = SwitchCost(impl₂, impl₁), and SC = SC₁ + SC₂. We call SC the round trip switching cost. The Delta algorithm described in the next section will perform close to optimal when, for any request r, |Cost(r, impl₁) – Cost(r, impl₂)| SC. That is, the difference in processing cost for a single request when one implementation is active as opposed to the other implementation, is significantly less than the switching cost.

The Delta algorithm

Consider any two-implementation-component problem, where SC is the previously defined round trip switching cost. Let = r₁, …, r_k be a sequence of requests. Then Cost(, impl_j) = ∑^k_i=1 Cost(r_i, impl_j), j = 1, 2. Algorithm Delta is extremely simple and works as follows. Say that implementation impl_i of component Comp is active, i ∈{1, 2}, and the processing of request r_k in the sequence r₁, r₂, … has just ended. Given impl_i, denote the other implementation by . If there exists j ≤ k such that Cost((r_j, …, r_k), ) ≤ Cost((r_j, …, r_k), impl_i) – SC, then Delta instructs Comp to switch implementations.

Delta also has a simple implementation using just three counters: Impl1Cost, Impl2Cost, and MinDelta. The algorithm, when impl₁ is assumed active, is given in Figure 1. The algorithm works analogously when impl₂ is active.

Figure 1

To see why this implementation is correct, note that by definition Cost(r₀) = 0 and if Delta switches to impl₂ after r_k, then j, 1 ≤ j ≤ k, such that

(Cost((r1, …, rk), impl1) – Cost((r0, …, rj-1), impl1) – (Cost((r1, …, rk), impl2) – Cost((r0, …, rj-1), impl2) ≥ SC

(Cost((r1, …, rk), impl1) – Cost((r1, …, rk), impl2) – (Cost((r0, …, rj-1), impl1) – Cost((r0, …, rj-1), impl2) ≥ SC

After processing request k in the sequence, the value of MinDelta in the implementation of Figure 1 equals the minimum of 0 and min_0≤j≤k {Cost((r₀, …, r_j), impl₁) – Cost((r₀, …, r_j), impl₂)}.

At this same point Impl1Cost equals Cost((r₁, …, r_k), impl₁), and Impl2Cost equals Cost((r₁, …, r_k), impl₂). Hence the equation above is true iff:

(Impl1Cost – Impl2Cost) – MinDelta ≥ SC

This is exactly the computation that the algorithm of Figure 1 performs in order to determine when to switch implementations.

The section “Competitiveness,” later, contains a formal proof that Delta is competitive and close to optimal. We now provide some intuition as to why this is the case. Let A be any algorithm and consider B, the “adversary” of A, an algorithm that observes A and tries to devise a sequence on which A performs worse than B. If A keeps impl₁ active too long, the adversary will devise the sequence to be costly when impl₁ is active and cheap when impl₂ is active. Hence, any competitive algorithm must keep switching between implementations when it determines that the cost of keeping the other implementation active is lower. But if A switches implementations too often, the switching costs will dominate and the adversary can choose to keep the same implementation active, thus avoiding all switching costs. The key insight of Delta is to switch exactly when it accumulates SC more in cost than the other implementation would, if it were active. Choosing any value other than SC results in worse performance.

To see why this is the case, say that A makes impl₁ active and switches to impl₂ after accumulating additional cost k, k < SC (more than it would have accumulated if impl₂ were active). As soon as A makes impl₂ active, the adversary would design the sequence so that A accumulates additional cost k when impl₂ is active. At that point A will switch back to impl₁. The adversary would keep impl₁ active throughout this sequence. Hence, the cost to the adversary would be just k, while A's cost would be k + SC + k > 3k. A would thus be worse than 3-competitive (how much worse would depend upon the choice of k).

On the other hand, say that A makes impl₁ active and A switches to impl₂ after accumulating additional cost k, k > SC. The adversary would make impl₂ active at the start of the sequence. As soon as A accumulates k in cost and switches to impl₂, the adversary would switch to impl₁ and would design the sequence so that A accumulates additional cost k when impl₂ is active. At that point A will switch back to impl₁. Hence, the cost to the adversary would be just SC, while A's cost would be k + SC + k > 3*SC. Hence, A would be worse than 3-competitive.

The reason Delta is (3 + )-competitive and not just 3-competitive is due to boundary conditions; Delta does not always have the opportunity to switch when it accumulates exactly SC more in cost. For instance, in may be that impl₁ is active and Delta has accumulated SC - 1 more in cost than it would have if impl₂ had been active. The next request r may cost it rCost = max_rCost(r, impl₁) – Cost(r, impl₂) more to process in impl₁ than in impl₂. Therefore Delta will not actually switch until it accumulates SC + rCost – 1 more cost in impl₁ than it would have in impl₂. The term bounds the cost of these boundary conditions.

Examples

In this section we apply the Delta algorithm to two problems: the distributed pub/sub problem and the data structure selection problem.

The distributed pub/sub problem. Consider a data server that serves records from a database to many clients. The server and each client reside on separate nodes of the network. Each client can perform a read or a write on the data. We assume that the clients are independent, that is, a client reads and writes data independent of any other client. There is no synchronization between clients. More formally, for any given “run,” there is a linear order in which each client reads and writes records, but the interleaving at the server of reads and writes from different clients is subject to various factors, and cannot be predicted.

Each client can exist in one of two modes: either in subscription (Sub) mode or in nonsubscription (NonSub) mode. In the latter case, for each read that the client wants to perform, it must send a message to the server and receive a reply back. In Sub mode, a client caches a local copy of the database. All reads of the database go against this local copy. In either case, writes must still go to the server. Upon receiving a write update from any client, the server must inform all subscribers (even the writer of the data if he or she is in Sub mode) of the change to the data. This mechanism is known as “pub/sub” (publication/subscription).

Because it is often impossible to statically predict the read/write behavior of clients, and because their behavior changes over time, we consider an adaptive pub/sub strategy that does not require a client to permanently use either Sub or NonSub mode, but that can flexibly switch between these implementations depending upon current workloads. The goal is to find an optimal strategy for switching implementations that minimizes network traffic.

An instance of the pub/sub problem consists of a server and m clients denoted by client_j (1 ≤ j ≤ m). Let r₁, …, r_k be a sequence of requests where request r_j is either read_j or write_j, 1 ≤ j ≤ m, indicating that client_j is either reading or writing a data record to the database. We assume that the database contains p – 1 records (by database we simply mean some collection of data items, where each item can be read and written individually). We now focus on how the requests related to client_i, 1 ≤ i ≤ m, when in NonSub mode, are carried out.

• read_i(r): This request generates a message from client_i to the server asking for record r, and a message back from the server delivering record r.
• read_j(r), j ≠ i: This request does not concern client_i (it is only relevant to client_j).
• write_i(r): This request generates a message from client_i to the server asking for record r to be written.
• write_j(r), j ≠ i: This request does not concern client_i.

The requests related to client_i, 1 ≤ i ≤ m, when in Sub mode are carried out as follows.

• read_i(r): Record r is read from the cached data at client_i, thereby avoiding the need for messages to the server.
• read_j(r), j ≠ i: This request does not concern client_i.
• write_i(r): This request generates a message from client_i to the server asking for record r to be written, and an update(r) message from the server to client_i.
• write_j(r), j ≠ i: This request generates an update(r) message from the server to client_i informing it that record r has been updated.

Switching implementations is carried out through subscribe and unsubscribe messages.

• subscribe( ): This is shorthand for switch(NonSub, Sub). It generates a message from client_i to the server, subscribing client_i to the database, and a message from the server delivering a local copy of the database to client_i. It puts client_i into Sub mode.
• unsubscribe( ): This is shorthand for switch(Sub, NonSub). It generates a message from client_i to the server unsubscribing client_i. It puts client_i into NonSub mode, and discards its local copy of the database.

The cost of a request is proportional to the number of messages it generates and their size, such that sending a single message containing a single record has unit cost. Figure 2 gives the costs to client_i for each of these requests.

Figure 2

Algorithm Delta can be applied to the pub/sub problem by monitoring each read and write request at client_i, switching from NonSub to Sub mode when it detects that Sub mode would have processed a previous subsequence of the requests for p + 1 less in network messaging costs than it was processed in NonSub mode. The number p + 1 is the switch cost of the Delta algorithm; SwitchCost(NonSub, Sub) + SwitchCost(Sub, NonSub) = p + 1. It monitors the requests being processed when in Sub mode and decides when to switch to NonSub mode based upon a similar calculation.

Figure 3 gives a sequence involving two clients and a server. For client₁, Cost(, NonSub) = 22 and Cost(, Sub) = 7. If p + 1 ≤ 15, then Delta would dictate that client₁ should subscribe in the course of this sequence. ' is the transformed sequence, if client₁ were to subscribe at the beginning of this sequence. In this example, op_i indicates that client_i is performing operation op, where op ∈{read, localRead, write, subscribe, unsubscribe}, i ∈{1, 2}, and update_i indicates that the server is sending an update message to client_i. localRead indicates a read operation from the local cache.

Figure 3

There is one subtlety, however, in using Delta for the pub/sub problem. Looking at Figure 2, we see that Delta needs to know not only the reads and writes done by client_i, but also the writes done by any client_j, j ≠ i. If Delta is running at client_i, how does it get this information? One possibility is to have Delta run at the server, where all client reads and writes are known, and have the server tell client_i when to switch implementations. However, it may be advantageous to have the control for switching implementations located at the client, thereby providing a more distributed architecture.

In Reference 5 we address the question “How can Delta, running at client_i, know about the write operations performed by other clients without increasing the number of messages that must be exchanged between the client and the server?” In Sub mode the issue does not exist, as the client can infer this from the number of updates messages it receives. In NonSub mode, it is required that the server piggyback a count of the total number of write operations it has received on the reply to each read request by client_i.

Figure 4 illustrates the processing by Delta of sequence involving client₁, client₂, and a server. The value of the counters as well as the intermediate computations at client₁ (in NonSub mode) are shown, as calculated by Delta (cf. Figure 1). In Figure 4, impl₁ is in NonSub mode while impl₂ is in Sub mode.

Figure 4

The adaptive data structure selection problem. Often an application chooses a data structure that is optimized for particular requests. When different types of requests require different data structures, either duplicate data structures are maintained, or a single data structure is used, chosen presumably for the most frequent type of requests. Consider, for example, a set of records S that has two possible keys, i₁ and i₂. (My bank allows me to identify myself either by my social security number or by my account number.) Let Comp be the component that encapsulates all operations on S. Comp may support many types of requests that operate on this set, but all of these requests can be categorized as either of type r₁, for requests using key i₁, or of type r₂, for requests using key i₂.

One strategy is for Comp two create two index tables for S, one using key i₁ and one using key i₂. Each index table is implemented as a dictionary,⁶ allowing one to perform the usual operations of finding, inserting, and deleting elements. But this strategy may not always be feasible, because there may not be sufficient capacity for storing both indices (e.g., a pervasive device), or the overhead in maintaining these two separate indices may be too high. In such cases, we can support two implementations, one that uses key i₁, and one that uses key i₂. Algorithm Delta is used to dynamically decide when to switch between these implementations. In Reference 5 we present a more complete discussion on the use of Delta in this context.

Competitiveness

For any two-implementation-component problem, let SC₁ = SwitchCost(impl₁, impl₂), SC₂ = SwitchCost(impl₂, impl₁), and let SC be the round trip switching cost SC = SC₁ + SC₂. Given request r let

reqCost = max_r|Cost(r, impl₁) – Cost(r, impl₂)|.

Let = 2*reqCost/SC. In this section we prove the following theorem:

Theorem 1: Algorithm Delta is (3 + )-competitive for any two-implementation-component problem.

Note that when the cost of processing a single request is significantly less than the cost of switching implementations, then 1 and Delta is close to optimal.

Proof: Consider any sequence processed by Delta. can always be viewed as consisting of recurring segments of the form = β, switch(impl₁, impl₂), , switch(impl₂, impl₁), where β and are sequences of requests, during processing of βimpl₁ is  active, and  during processing  of impl₂ is active. Note that β and contain no switch statements. Without loss of generality, we can assume that β, ≠ ( is the empty sequence). We will maintain the following invariant:

Invariant: At the start of processing of an segment, for any algorithm processing this sequence, either impl₁ is active or impl₂ is active and there is a debt of SC₁. By “debt” we mean that if, at the start of processing of a segment impl₂ is active, then a cost SC₁ has accrued in a preceding segment that has not yet been charged to the algorithm. Initially we know this is true because we assume that all algorithms start in impl₁ mode.

Let r be the last request in β. Note that Cost(r, impl₁) ≤ Cost(r, impl₂) + reqCost. There are two properties of note regarding the cost to any algorithm of processing the β portion of segment .

Property 1: Let be any algorithm that processes β with impl₁ active at both the start and the end of the sequence, and switching between implementations any number of times in between. Then Cost_β > Cost(β, impl₁) – reqCost; that is, at most reqCost is gained by switching back and forth during the processing of β. To see why this is true, consider the case when switches only once; say, makes impl₁ active during β₁, impl₂ active during β₂, and impl₁ active during β₃, where β = β₁, β₂, β₃. Assume that β₂ ≠ , otherwise this is trivially true. If β₃ ≠ then Cost(β₂, impl₂) + SC > Cost(β₂, impl₁), otherwise Delta would have switched to impl₂ before or at the end of processing β₂. If β₃ = then let β^'₂ be the prefix of β₂ with one operation (r) removed from the end of β₂. Then Cost(β^'₂, impl₂) + SC > Cost(β^'₂, impl₁) since Delta did not switch implementations before completing the processing of β. Since Cost(r, impl₂) ≥ Cost(r, impl₁) – reqCost, we have

Cost(β₂, impl₂) + SC
  = Cost(β'₂, impl₂) + Cost(r, impl₂) + SC
  > Cost(β'₂, impl₁) + Cost(r, impl₁) – reqCost
  = Cost(β₂, impl₁) – reqCost

Hence,

Costβ	= Cost(β1, impl1) + Cost(β2, impl2) + Cost(β3, impl1) + SC
	> Cost(β, impl1) – reqCost

A similar argument applies to any algorithm that switches multiple times back and forth between implementations during β. This completes the proof of Property 1.

Property 2: For any β₁, β₂ such that β = β₁β₂,

Cost(β, impl₁) < Cost(β₁, impl₁) + Cost(β₂, impl₂) + SC + reqCost

That is, it costs at most SC + reqCost more to process β when impl₁ is active than processing part of it when impl₁ is active and the rest when impl₂ is active. If β₂ = , this is trivially true. So assume that β₂ ≠ and let β^'₂ be the prefix of β₂ with one operation (r) removed from the end of β₂. Then

Cost(β₁β'₂, impl₁) < Cost(β₁, impl₁) + Cost(β'₂, impl₂) + SC

since Delta did not switch implementations before completing the processing of β. Since

Cost(r, impl₁) ≤ Cost(r, impl₂) + reqCost

we have

This completes the proof of Property 2.

Let l₁ = Cost(β, impl₁) – SC – reqCost. Now we determine the cost to any adversary algorithm Adv of processing β by examining the four cases A through D.

1. Adv starts with impl₁ active and ends with impl₁ active. If it never switches implementations, its cost is l₁ + SC + reqCost. Otherwise, say that it switches from impl₁ to impl₂ and back to impl₁ during β. By Property 1, this can only decrease its cost by reqCost, so its cost is at least l₁ + SC. Switching multiple times will not further decrease its cost.
   
   
2. Adv starts with impl₁ active and ends with impl₂ active. By Property 2, if it switches only once then it may save at most SC + reqCost over the cost of processing β entirely in impl₁ but incurs a cost of SC₁ in switching implementations. Hence, its cost is at least l₁ + SC₁. Switching multiple times in processing β will not decrease its cost any further.
   
   
3. Adv starts with impl₂ active and ends with impl₂ active. If Adv does not change modes at all during this phase, then by Property 2 the cost to Adv is at least l₁ to process β. However, according to the Invariant, there is a debt of SC₁ to Adv, since it starts β with impl₂ active. We remove that debt and charge it to this phase of the algorithm. Hence, Adv will have at least the cost of l₁ + SC₁. By an argument similar to Property 1, by changing its mode during the processing of this sequence, Adv will not decrease its cost any further.
   
   
4. Adv starts with impl₂ active and ends with impl₁ active. This is similar to the preceding case, except that it has an additional cost of SC₂ for switching to impl₁. Hence, its cost is at least l₁ + SC₁ + SC₂ = l₁ + SC.

Now consider . Let r' be the last request in . Note that

Cost(r', impl₂) ≤ Cost(r', impl₁) + reqCost

The two properties stated above for β have analogs in processing (we omit the proofs as they are similar to those given above).

Property 3: Let be any algorithm that processes by initially starting with impl₂ active, ending with impl₂ active, but switching between implementations any number of times in between. Then Cost > Cost(, impl₂) – reqCost.

Property 4: For any ₁, ₂ such that = ₁₂,

Cost(, impl₂) < Cost(₁, impl₂) + Cost(₂, impl₁) + SC + reqCost

Let l₂ = Cost(, impl₂) – SC – reqCost. Now we use Properties 1 through 4 above and determine the cost to any adversary Adv of processing by examining the four cases E through H.

5. Adv starts with impl₂ active and ends with impl₂ active. If it never switches implementations, its cost is l₂ + SC + reqCost. Otherwise, say, it switches from impl₂ to impl₁ and back to impl₂ during processing of . By Property 3, this can decrease its cost by at most reqCost. However, since Adv ends the processing of segment with impl₂ active (and will start the next segment with impl₂ active), we remove SC₁ in cost from this phase of the algorithm and pay the debt, thereby maintaining the Invariant. Its costs are therefore l₂ + SC – SC₁ = l₂ + SC₂.
   
   
6. Adv starts with impl₂ active and ends with impl₁ active. By Property 4, if it only switches once, then it may save at most SC + reqCost over processing entirely with impl₂ active but incurs a cost of SC₂ to switch modes. Hence, its cost is at least l₂ + SC₂. Switching multiple times in processing will not decrease its cost any further.
   
   
7. Adv starts in impl₁ mode and ends in impl₁ mode. If Adv does not change modes at all during this phase, then by Property 4 the cost to Adv is at least l₂ to process . By an argument similar to Property 3, by changing its mode during the processing of this sequence, Adv will not decrease its cost any further.
   
   
8. Adv starts in impl₁ mode and ends in impl₂ mode. This is similar to the preceding case, except that it has an additional cost of SC₁ for switching to impl₂. However, since Adv ends the iteration of the segment in impl₂, we need to remove SC₁ in cost from this phase of the algorithm and assign it to the debt in order to maintain the Invariant. Hence, its cost is at least l₂.

To analyze the overall complexity of Adv, we consider the cost of executing one complete segment of . Adv must follow one of the following eight “paths”: A → G, A → H, B → E, B → F, C → E, C → F, D → G, D → H. For instance, the first path says that Adv first implements case A for β and then implements case G for . Note that these eight paths are the only ones possible, as A cannot be combined with E, for example, since case A states that impl₁ is active at the end of β, and case E states that impl₂ is active at the start of (= end of β). By summing the costs of each of these paths, one sees that Cost_β^Adv ≥ l₁ + l₂ + SC. The cost to Delta is at most l₁ + SC + reqCost to process β, SC₁ to switch to impl₂ at the end of β, l₂ + SC + reqCost to process , and SC₂ to switch to impl₁ at the end of . Hence,

Hence, Delta is (3 + )-competitive on any segment.

To complete the proof of this theorem, we need to show that for any arbitrary long sequence that is a strict subsequence of an segment, Delta is also (3 + )-competitive. We leave this as a straightforward exercise, based on the discussion above.

End of proof

Lower bounds

In this section we show that there are instances of the two-implementation-component problem such that no algorithm is better than 3-competitive. The proof involves the dynamic pub/sub problem, given in the section “Examples.”

In analyzing adaptive on-line algorithms, it is useful to differentiate between different types of adversaries.^4,7 An oblivious adversary is one that constructs the sequence of requests without regard to the actions taken by the algorithm. An adaptive adversary determines the action corresponding to each element of a sequence on line by taking into account the previous choices made by algorithm. If, additionally, the adversary processes the sequence only after the entire sequence has been generated, it is then said to be an adaptive off-line adversary. This is the most powerful sort of adversary, and we follow the terminology of Reference 8 and call it a strong adversary.

The result of this section shows that no deterministic or randomized algorithm can do better than Delta against a strong adversary for all two-implementation-component problems. Also, since the distinction between strong and oblivious adversaries is irrelevant for deterministic algorithms,⁷ it also shows that no deterministic algorithm is better than 3-competitive against any type of adversary for all two-implementation-component problems.

Lemma 1: Let Alg be any adaptive pub/sub algorithm controlling an individual client. There exists an arbitrarily long sequence constructed by a strong adversary such that, as the length of tends to infinity, Alg is at best 3-competitive on .

Proof: Consider just two clients, client₁ and client₂, and let client₁ be running algorithm Alg. For any integer l, we can construct a sequence of the form = read₁^m₁ write₂^n₁ read₁^m₂ write₂^n₂ … read₁^m_k write₂^n_k with the following characteristics (r₁^m indicates m consecutive client₁ requests of type r):

• The length of the sequence (number of operations) is larger or equal to l
• For all t, 1 ≤ t ≤ k, client₁ subscribes after the read₁^m_t operations and unsubscribes after the write₂^n_t operations.

To find this sequence, we begin by “serving” read requests to the client₁ until it subscribes and then “serving” write requests to client₂, causing update messages to propagate to client₁ until client₁ unsubscribes. We continue this process until we reach the desired sequence length. Since we are dealing with a strong adversary, it knows exactly when to serve read (write) requests, as it just waits until it sees client₁ subscribe (unsubscribe). We assume that client₁ forever alternates between Sub and NonSub modes if served enough write and read requests, respectively. Otherwise, this client would trivially not be competitive. Indeed, if it stayed in Sub mode, the adversary could forever feed it update messages whereas the adversary would incur no cost by staying in NonSub mode. Similarly, if it stayed in NonSub mode the adversary could forever feed it read messages and the adversary would incur no cost by staying in Sub mode.

Let R be the total number of read operations and W be the total number of write operations in . The cost to client₁ incurred by Alg, which we denote by Cost^Alg(1), equals 2R + W + (pk + k), as it costs 2R for client₁ read messages, W for client₁ update messages (= client₂ write operations), pk for the k client₁ subscribe messages, and k for the k client₁ unsubscribe messages. Let M = min{2R, W, (pk + k)}. Now devise the strong adversary as follows:

• Case 1: M = 2R. Let stay in NonSub mode throughout the sequence. Then
  Cost(1) = 2R. Cost^Alg(1) = 2R + W + (pk + k) ≥ 3(2R) = 3*Cost(1). Hence, Alg is at best 3-competitive.
• Case 2: M = pk + k. Let subscribe directly before each set of read operations and unsubscribe directly before each set of write operations. Then Cost(1) = pk + k. Cost^Alg(1) = 2R + W + (pK + k) ≥ 3(pk + k) = 3*Cost(1). Hence, Alg is at best 3-competitive.
• Case 3: M = W. Let initially subscribe and then stay in Sub mode throughout the sequence. Then Cost(1) = W + p. Recall that as l → ∞, we can assume W → ∞, otherwise the client is trivially not competitive. Hence, as l → ∞, Cost(1) → W. Therefore Cost^Alg(1) = 2R + W + (pK + k) ≥ 3W = 3*Cost(1), and Alg is at best 3-competitive.

End of proof

Related work

The ideas in this paper are related to prior work in program optimization, competitive algorithms, and data replication policies.

Some of the work in program optimization discusses optimizing programs by choosing among a set of alternate implementations. For the most part, this work focuses on low-level static optimizations. For example, the early work on SETL examined how to choose the best set representation based upon program analysis.⁹ Similarly the work on SQL (Structured Query Language) optimization can be viewed as statically choosing the best implementation for retrieving information from a database given a particular query.¹⁰

Closer to our strategy is the recent work described in Reference 11, in which the authors propose that the component writer provide multiple implementations of a component, assign costs to the different operations on each component, profile a program made up of multiple components running in a particular context, and construct an object affinity graph for this program. They then use a graph partitioning algorithm to find an optimal partitioning of the graph, thereby finding the optimal implementation for each component. Central to their scheme is the observation that the implementations at different components affect each other. Unlike algorithm Delta, their strategy optimizes a program globally, not just at the level of an individual component. On the other hand, their technique requires a more complicated methodology (profiling and the creation of an object affinity graph) and cannot adjust to dynamically changing contexts as Delta does.

Recent work on dynamic architecture description languages (see Reference 12 for a summary) aims at building software architectures that can respond adaptively to changes. Algorithms like Delta will be important in helping realize the goals of these architectures.

Our adaptive pub/sub application contrasts with previous work on data replication.^13,14 An extended version of Reference 15 gives a good overview of the literature on file allocation, file migration, and file replication problems. Although similar in some ways, our adaptive pub/sub application is closer to the work in References 16 and 17, which we discuss later in this section.

Our work draws inspiration from many competitive algorithms.^4,8,15,18,19 Although it may seem that this work could be used to solve our problem, a closer examination shows that this is not the case. For instance, one immediate idea for a competitive adaptive pub/sub algorithm, modeled after the snoopy caching algorithm,^8,18 is for a client to subscribe after performing (½)p consecutive read operations, and to unsubscribe after receiving p consecutive update operations. The asymmetry between reads and updates is due to the fact that in our model a read is twice as expensive as an update operation. Consider the sequence (read₁^(½)p-1, write₂)ⁿ; that is, client₁ issues (½)p – 1 reads followed by a write by client₂. This is repeated n times. The cost to the snoopy caching algorithm for this sequence with regard to client₁ would be n*(p – 2). One can devise an adversary that would process this sequence at cost p + n (the adversary would initially subscribe and then stay in Sub mode). There do not exist constants c and d independent of p such that n(p – 2) ≤ c(n + p) + d for all n. Hence, the snoopy caching algorithm is not a good competitive algorithm for the pub/sub problem.

As mentioned, our work on the adaptive pub/sub problem is most closely related to the work in References 16 and 17. Reference 16 seems to exactly address our problem and to derive a better lower bound than ours (2k-competitive, for any integer k). In their model, however, the data being replicated are always of unit size, that is, variable p – 1 (the size of the data being replicated) always takes value 1. Hence, our work generalizes that result in an important way, by allowing arbitrary size data.

Let us see how the algorithm in Reference 16 would work for our problem. This algorithm re-evaluates the mode a client is in after every k operations (alternatively, the algorithm in Reference 20 re-evaluates after a fixed time period t). If read operations are the majority, the client switches to (stays in) Sub mode; otherwise it switches to (stays in) NonSub mode. Consider the sequence (read₁^k, write₂^k)ⁿ; that is, k reads by client₁ are followed by k writes by some other client. This is repeated n times. Dynamically switching betweenimplementations of a component should become a useful tool in autonomic computing. The cost with respect to client₁ would be (p + 1)n + 3kn. One can devise an adversary whose cost would be W = min{nk, (p + 1)n}. There do not exist constants c and d independent of p such that (p + 1)n + 3kn ≤ cW + d for all n. Because p may be arbitrarily large, this may result in a large competitive factor. Hence, the algorithm would not perform well in the worst case when one generalizes to larger data structures. The algorithm does model other aspects that we have not considered. Most importantly, whereas we assume a fixed data “server,” Reference 16 uses the notion of a primary site that can dynamically change in the course of execution.

Very recently, as this paper was going into production, I became aware of the very relevant work on metrical task systems.²¹ Metrical task systems are very similar to the adaptive component problem described in this paper, and the results there are consistent with the results of this paper. However, there are two important differences between the two. First, in metrical task systems, it is assumed that SwitchCost(i, j) = SwitchCost(j, i) (symmetry). We make no such assumption. As a matter of fact, for the distributed pub/sub problem described in the section “Examples,” this is not the case. Second, in our model we assume that once a request is received, the processing of the request must be completed before switching to another implementation. We took this approach to better model scenarios where rapid response time is critical (i.e., the response must be made before embarking on the relatively lengthy process of switching implementations). In metrical task systems, however, switching implementations (states) can be done after a request is received but before it is processed. For both of these reasons, our work generalizes metrical task systems in the case of two implementations (or, in the terminology of Reference 21, in the case of two states), and it is not clear that the algorithms and proofs given in metrical task systems apply directly to the adaptive component problem.

Summary and open issues

This paper provides a framework for analyzing the effectiveness of components that switch implementations dynamically at run time based upon run-time workload characteristics. We believe that dynamic selection of component implementations will become an effective tool in optimizing component performance, and therefore the framework given in this paper should become increasingly important.

An important contribution of this paper is the near optimal (3 + )-competitive algorithm Delta, for the two-implementation-component problem, in which there are only two implementations to choose from. An obvious question is whether there exist competitive algorithms for components with an arbitrary number of implementations. In Reference 5 we show there does not exist an algorithm that is better than k-competitive when the number of implementations is k. Another limitation of Delta is that it requires a switch from one implementation to another in “one shot,” and this can often be expensive. In Reference 5 we show how Delta can switch implementations in an incremental fashion for the two example problems of section “Examples,” thereby amortizing the cost of the switch operation. Still, a more general method of incremental switching between component implementations is needed.

Competitiveness is only one criterion by which to judge an algorithm for switching among implementations. In Reference 5 we mention one other criterion: convergence. Other metrics can be used as well. For instance, it may be that some domains exhibit great periodicity of patterns in event sequences. The ability to learn these patterns and then optimize to them is an important strategy in these domains.

Most importantly, we need experience to see how well Delta works in practice. This will shed light on how to best evolve this algorithm. For instance, it may be that domain knowledge needs to be taken into account in order to obtain better results.

**Trademark or registered trademark of Sun Microsystems, Inc.

Cited references