Efficient elections in chordal ring networks

We study the message complexity of the problem of distributively electing a leader in chordal rings. Such networks consist of a basic ring with additional links, the extreme cases being the oriented ring and the complete graph with a full sense of direction. We present a general election algorithm for these networks, and prove its optimality. As a corollary, we show thatO(logn) chords at each processor suffice to obtain an algorithm that uses at mostO(n) messages; this improves and extends a previous work, where an algorithm, also usingO(n) messages, was suggested for the case where alln-1 chords exist (the oriented complete network).The work of this author was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant No. A2415.The work of this author was supported in part by Technion Research Grant No. 120-0641.     

Necessary conditions for infinite-dimensional control problems

We consider infinite-dimensional nonlinear programming problems which consist of minimizing a functionf ₀(u) under a target set constraint. We obtain necessary conditions for minima that reduce to the Kuhn-Tucker conditions in the finite-dimensional case. Among other applications of these necessary conditions and related results, we derive Pontryagin’s maximum principle for a class of control systems described by semilinear equations in Hilbert space and study convergence properties of sequences of near-optimal controls for these systems. The work of this author was supported in part by the National Science Foundation under Grant DMS-8701877.     

Purely top-down updating algorithms for stratified search trees

Summary The existence of purely top-down updating algorithms for balanced search trees is of importance when maintaining such trees in a concurrent environment, where purely top-down means a single sweep from the root to frontier along a search path. We present algorithms for internal- and external-search trees in the general framework of stratified trees. This enables us to demonstrate that many classes of balanced search trees have such updating schemes, although, for example, weight-balanced trees do not fit into this framework.Work carried out partially under NATO Grant No. RG 155.81 and the work of the third author was partially supported by Natural Sciences and Engineering Research Council of Canada Grant No. A-5692     

An Access Control Framework for Reflective Middleware

Reflective middleware opens up the implementation details of middleware platform and applications at runtime for improving the adaptability of middleware-based systems. However,such openness brings new challenges to access control of the middleware-based systems. Some users can access the system via reflective entities,which sometimes cannot be protected by access control mechanisms of traditional middleware. To deliver high adaptability securely,reflective middleware should be equipped with proper access control mechanisms for potential access control holes induced by reflection. One reason of integrating these mechanisms in reflective middleware is that one goal of reflective middleware is to equip applications with reflection capabilities as transparent as possible. This paper studies how to design a reflective J2EE middleware - PKUAS with access control in mind. At first,a computation model of reflective system is built to identify all possible access control points induced by reflection. Then a set of access control mechanisms,including the wrapper of MBeans and a hierarchy of Java class loaders,are equipped for controlling the identified access control points. These mechanisms together with J2EE access control mechanism form the access control framework for PKUAS. The paper evaluates the security and the performance overheads of the framework in quality and quantity.     

Optimal Control of Switching Surfaces in Hybrid Dynamical Systems

This paper concerns an optimal control problem defined on a class of switched-mode hybrid dynamical systems. The system's mode is changed (switched) whenever the state variable crosses a certain surface in the state space, henceforth called a switching surface. These switching surfaces are parameterized by finite-dimensional vectors called the switching parameters. The optimal control problem is to minimize a cost functional, defined on the state trajectory, as a function of the switching parameters. The paper derives the gradient of the cost functional in a costate-based formula that reflects the special structure of hybrid systems. It then uses the formula in a gradient-descent algorithm for solving an obstacle-avoidance problem in robotics. The work of Boccadoro has been partially supported by MIUR under Grant PRIN 2003090090. The work of Wardi has been partly supported by a grant from the Georgia Tech Manufacturing Research Center. The work of Egerstedt has been partly supported by the National Science Foundation under Grant \# 0237971 ECS NSF-CAREER, and by a grant from the Georgia Tech Manufacturing Research Center.     

Approximate polynomial preconditionings applied to biharmonic equations

Applying a finite difference approximation to a biharmonic equation results in a very ill conditioned system of equations. This paper examines the conjugate gradient method used with polynomial preconditioning techniques for solving such linear systems. A new approach using an approximate polynomial preconditioner is described. The preconditioner is constructed from a series approximation based on the Laplacian finite difference matrix. A particularly attractive feature of this approach is that the Laplacian matrix consists of far fewer non-zero entries than the biharmonic finite difference matrix. Moreover, analytical estimates and computational results show that this preconditioner is more effective (in terms of the rate of convergence and the computational work required per iteration) than the polynomial preconditioner based on the original biharmonic matrix operator. The conjugate gradient algorithm and the preconditioning step can be efficiently implemented on a vector super-computer such as the CDC CYBER 205.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada Grant U0375; and in part by NASA (funded under the Space Act Agreement C99066G) while the author was visiting ICOMP, NASA Lewis Research Center.The work of this author was supported by an Izaak Walton Killam Memorial Scholarship.     

Adaptive exponential stabilization for a class of nonlinear retarded processes

This paper considers the problem of adaptive exponential stabilization for a class of single-input single-output nonlinear retarded processes. The class includes certain linear retarded systems which are subject to sector-bounded actuator and sensor nonlinearities. It is shown that there is a wide range of high-gain adaptive compensators which achieve exponential stability for the class of processes under consideration. This work was supported by SERC under Grant No. GR/D/45710.     

An adaptive multipath routing scheme for connectionless traffic in an ATM network

This paper addresses the problem of routing connectionless traffic through an ATM network. A solution is proposed based on a per-packet adaptive multipath routing scheme which is added to the routing algorithm implemented at the Inter-Working Units. A scheme is presented that distributes packets among multiple Virtual Paths (VPs) according to the utilization of the links on these VPs. The utilization of the VPs is determined by a periodic feedback mechanism. Simulation studies show the effectiveness of the proposed adaptive multipath routing scheme.The work by J. Sole-Pareta was supported in part by a CIRIT (Generalitat de Catalunya) grant (expedient number EE92/2-338), and in part by the National Science Foundation under Grant No. INT-94033646. The work by I. Akyildiz was supported in part by the National Science Foundation under Grant No. INT-94033646.     

Integrating Scene Parallelism in Camera Auto-Calibration

This paper presents an approach for camera auto-calibration from uncalibrated video sequences taken by a hand-held camera.The novelty of this approach lies in that the line parallelism is transformed to the constraints on the absolute quadric during camera autocalibration.This makes some critical cases solvable and the reconstruction more Euclidean.The approach is implemented and validated using simulated data and real image data.The experimental results show the effectiveness of the approach.     

Adaptive decentralized control under non-uniqueness of the optimal control

We study the problem of decentralization of flow control in packet-switching networks under the isarithmic scheme. An incoming packet enters the network only if there are permits available at the entry port when it arrives. The actions of the controllers refer to the routing of permits in the network and the control variables are the corresponding probabilities. We study the behavior of adaptive algorithms implemented at the controllers to update these probabilities and seek optimal performance. This problem can be stated as a routing problem in a closed queueing network. The centralized version of a learning automation is a general framework presented along with the proof of asymptotic optimality. Decentralization of the controller gives rise to non-uniqueness of the optimal control parameters. Non-uniqueness can be exploited to construct asymptotically optimal learning algorithms that exhibit different behavior. We implement two different algorithms for the parallel operation and discuss their differences. Convergence is established using the weak convergence methodology. In addition to our theoretical results, we illustrate the main results using the flow control problem as a model example and verify the predicted behavior of the two proposed algorithms through computer simulations, including an example of tracking.The work of this author was partially supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Government of Canada, and partially supported by NSERC grant WFA 0139015 and FCAR-Québec grant 95-NC-1375.The work of this author was supported by a grant from the CITR under the NCE program of the Government of Canada.