As distributed real-time applications gain in popularity, a key challenge is to allocate resources so that diverse real-time requirements (including non-real-time applications), distributed application components and varying workloads can all be accommodated without violating timeliness constraints. We examine the problem of resource allocation in distributed soft real-time systems, where both network and CPU resources are consumed. The timeliness constraints of applications are expressed through utility functions, which compute "benefit" as a function of end-to-end latency. We present LLA (Lagrangian Latency Assignment), a scalable and efficient distributed algorithm which maximizes aggregate utility by computing an optimal trade-off between end-to-end latency and allocated resources. The algorithm runs continuously and adapts to both workload and resource variations. LLA is guaranteed to converge if the workload and resource requirements stabilize. We evaluate the quality of results and convergence characteristics under various workloads, using both simulation and real-world experimentation.

Event-driven distributed infrastructures are becoming increasingly important for information dissemination and application integration. We examine the problem of optimal resource allocation for such an infrastructure composed of an overlay of nodes. Resources, like CPU and network bandwidth, are consumed by both message flows and message consumers; therefore, we consider both rate control for flows and admission control for consumers. This makes the optimization problem difficult because the objective function is nonconcave and the constraint set is nonconvex. We present LRGP (Lagrangian Rates, Greedy Populations), a scalable and efficient distributed algorithm to maximize the total system utility. The key insight of our solution involves partitioning the optimization problem into two types of subproblems: a greedy allocation for consumer admission control and a Lagrangian allocation to compute the flow rates, and linking the subproblems in a manner that allows tradeoffs between consumer admission and flow rates while satisfying the nonconvex constraints. LRGP allows an autonomic approach to system management where nodes collaboratively optimize aggregate system performance. We evaluate the quality of results and convergence characteristics under various workloads.

Content-based subscription systems are an emerging alternative to traditional publish-subscribe systems, because they permit more flexible subscriptions along multiple dimensions. In these systems, each subscription is a predicate which may test arbitrary attributes within an event. However, the matching problem for content-based systems — determining for each event the subset of all subscriptions whose predicates match the event — is still an open problem. We present an efficient, scalable solution to the matching problem. Our solution has an expected time complexity that is sub-linear in the number of subscriptions, and it has a space complexity that is linear. Specifically, we prove that for predicates reducible to conjunctions of elementary tests, the expected time to match a random event is no greater than O(N 1;) where N is the number of subscriptions, and is a closed-form expression that depends on the number and type of attributes (in some cases, 1=2). We present some optimizations to our algorithms that improve the search time. We also present the results of simulations that validate the theoretical bounds and that show acceptable performance levels for tens of thousands of subscriptions. 1

Current middleware solutions such as CORBA and Java's RMI emphasize compositional design by separating functional aspects of a system (e.g. objects) from the mechanisms used for interaction (e.g. remote procedure call through stubs and skeletons). While this is an effective solution for handling distributed interactions, higher-level requirements such as heterogeneity, availability, and adaptability require policies for resource management as well as interaction. We describe the Distributed Connection Language (dcl): an architecture description language based on the Actor model of distributed objects. System components and the policies which govern an architecture are specified as encapsulated groups of actors. Composition operators are used to build connections between components as well as customize their behavior. This customization is realized using a meta-architecture. We describe the syntax and semantics of dcl, and illustrate the language by way of several examples.