Computer Science Department

Computer Science Colloquium

An optimal competitive algorithm for the dynamic selection of component implementations

Daniel M. Yellin
IBM Distinguished Engineer, IBM T.J. Watson Research Center (Affiliated)

Friday October 4, 2002
11:30 a.m.
Room 1302 WWH
251 Mercer Street
New York, NY 10012-1185

Host: Davi Geiger,, 212-998-3253
Colloquium Information:


In component-based development, an application is composed of multiple distributed components. Because components may be used in many different contexts, and because they must process changing request patterns, component performance is an important issue for component-based architectures. In this paper we propose a mechanism whereby components offer multiple implementations, each optimized for a particular request workload. The component must also provide the mechanism for switching between implementations. The underlying system will then monitor, at run-time, the sorts of requests a particular component is currently receiving and adaptively switch to an optimized implementation for that workload.

The performance of the resulting system is dependent upon making good choices as to when to switch between implementations, which we call the adaptive component problem. This paper formalizes the generic problem, and describes the Delta algorithm, a 3-competitive algorithm for the 2 implementation problem (when there are only two implementations to choose from). We prove that no algorithm can do better against an adaptive off-line adversary, and give a lower bound on the generic k-implementation problem. We show the applicability of this framework to two example problems: the distributed pub/sub problem, and the data structure selection problem.