Providing Flexibility in Distributed Applications Using a Mobile Component Framework

Future distributed applications will need to support computing devices with a wide range of capabilities, varying network connectivity, increasing mobility of users, and a wide variation in load placed by clients on services. This dissertation addresses these challenges through the realization of a component-based framework, named DACIA, for building and executing adaptive distributed applications. Applications are viewed as graphs of connected components that typically implement data streaming, processing, and filtering functions. DACIA provides mechanisms for run-time reconfiguration of applications to allow them to adapt to the changing operating environments. Applications can dynamically load new components, change the way various components interact and exchange data, move components from one host to another, and replicate some components across multiple hosts.

We identify the issues involved in runtime application reconfiguration. We propose an algorithm for performing dynamic reconfiguration while preserving the consistency and correctness of the application and minimizing the application disturbance. This algorithm executes in linear time with respect to the size of the application graph, and graciously handles failures that occur during the reconfiguration.

Component mobility in DACIA provides support for mobile users and mobile applications. Logical connections between moving components are persistent. Messages are reliably and orderly delivered during and after component relocation. The execution of components connected to the moving component is not affected. Users do not see any interruptions in the services accessed, and they do not need to manually re-establish connections with the communication parties.

We give several examples of applications implemented using DACIA, that demonstrate the benefits of using our framework, both from the performance and from the usability standpoint. DACIA is designed so that communication overheads are low, comparable to those of procedure calls when components are co-located and those of raw network communication when they are located on remote hosts. Moreover, the cost of moving components across hosts can be kept low. We show that by using simple adaptive heuristics to reconfigure an application, the performance of the application can be significantly improved compared to the static case in which the application structure is fixed.



Developing Adaptive Groupware Applications Using a Mobile Component Framework

There is a need to develop groupware systems that adapt to available resources and support user mobility. This paper presents DACIA, a system that provides mechanisms for building such groupware applications. Using DACIA, components of a groupware application can be moved to different hosts during execution, while maintaining communication connectivity with groupware services and other users. DACIA provides mechanisms that simplify building groupware for domains where users are mobile. New collaboration features can be also more easily implemented. For example, users may ``park'' their client agents temporarily at a fixed host while they are disconnected; the parked agent can continue to maintain connectivity with other group members on behalf of the user, if desired. DACIA is also applicable to non-mobile environments. We show its applicability to building groupware applications that can be reconfigured at run-time to adapt to changing user demands and resource constraints, for example, by relocating services or introducing new services. This paper describes the architecture of DACIA and its use in building adaptable groupware systems.



DACIA: A Mobile Component Framework for Building Adaptive Distributed Applications

Future distributed applications will need to support computing devices with a wide range of capabilities, varying network connectivity, increasing mobility of users, and a wide variation in load placed by clients on services. This paper presents DACIA (Dynamic Adjustment of Component InterActions), a framework for building adaptive distributed applications. In DACIA, distributed applications are viewed as consisting of connected components that typically implement data streaming, processing, and filtering functions. DACIA provides mechanisms for run-time reconfiguration of applications to allow them to adapt to the changing operating environments. Components can be moved to different hosts during execution, while maintaining communication connectivity with other components. New components can also be introduced along data paths, for example, to provide compression on low-bandwidth connections. Keeping communication overheads low is a significant challenge in designing component-based services. DACIA is designed so that communication costs among co-located components are similar to those of procedure calls. Performance results, as well as examples of adaptive services that can be built using DACIA are presented.



Stateful Group Communication Services

Reliable group multicasts provide a nice abstraction for communicating data reliably among group members and have been used for a variety of applications. In this paper we present Corona, a group communication service for building collaboration tools and reliable data dissemination services in Web-based environments, where clients connect independently of other clients and are not necessarily connected to the group multicast services all the time. The key features of Corona are: (1) the shared state of a group consists of a set of objects shared collectively among group members; (2) Corona supports multiple state transfer policies to accommodate clients with different needs and resources; (3) the communication service provides the current group state or state updates to new clients even when other clients are not available; (4) the service supports persistent groups that tolerate client failures and leaves. We show that the overhead incurred by the multicast service in managing each group's shared state has little impact on the latency seen by the clients or the server throughput. We also show that the multicast service does not have to be aware of the client-specific semantics of the objects in the group's state.



Adaptive Group Communication Services for Groupware Systems

Collaborative, multi-user applications require group multicast services that provide ordering guarantees for maintaining consistency of replicated shared context as well as provide a high degree of interactivity, even under varying load on the communication servers. While the most common view of the quality of service (QoS) in a distributed system is in terms of the guarantee of the network connection parameters (bandwidth, end-to-end delay) for audio and video, in this paper we investigate the various requirements placed on group communication servers for reliable data communication among diverse groups of collaborative users. We show that in the absence of such considerations in the design of a group communication service, some groups or individual users can be severely affected by bursty traffic or increase in the size of other groups. We present the design of a best-effort adaptive group communication service for supporting reliable data communication in CSCW systems, which addresses both group's requirements and individual user's requirements, balancing the needs of multiple groups of users by taking into account their priorities and needs when resources are constrained at the communication server.



Visibility Line in a Direction for a Set of Parallel Line Segments

In this paper we present a sequential algorithm that computes the part of a set of parallel line segments visible in a direction. The algorithm performs in O(n log n) time and O(n) time with preprocessing-sorting, where n is the number of line segments. The worst possible configuration of the line segments is determined to be a staircase arrangement with a garbage collection segment.



Individual and Group QoS Issues in Communication Services for Groupware Systems

The proliferation of computer networks in the last decade and the ubiquity of the World Wide Web have led to increased interest in the development of computer-supported cooperative work (CSCW) systems. Collaborative, multi-user applications require group multicast services that provide ordering guarantees for maintaining consistency of replicated shared context as well as provide a high degree of interactivity, even under varying load on the multicast servers. While the most common view of the quality of service (QoS) in a distributed system is in terms of the guarantee of the network connection parameters (bandwidth, end-to-end delay), in this paper we investigate QoS from the perspective of the various requirements placed on group communication servers with limited resources by multiple and diverse groups of collaborative users. We show that in the absence of QoS considerations in the design of a group communication service, some groups or individual users can be severely affected by bursty traffic or increase in the size of other groups. We present the design of a best-effort QoS-based adaptive group communication service for supporting reliable data communication in CSCW systems. Our QoS considerations address both group's requirements and individual user's requirements. We present performance results showing the effectiveness of the approach and discuss some of the open issues for future work.



Stateful Multicast Services for Supporting Collaborative Applications

Collaborative, multi-user applications require group multicast services with ordering guarantees for maintaining consistency of replicated shared state among collaborating processes. In traditional group multicast services (such as Isis), the group's shared state is maintained only by the clients and the multicast service facilitates atomic state transfer from existing clients to new members. In this paper, we argue that, in order to support collaborative applications in Internet-type environments, a copy of the group's state should also be maintained by the multicast service. We show that by maintaining a copy of group's state, the multicast service can provide consistently fast group-join and state transfer times when both slow and fast clients are present or when clients are unreliable --- a crucial requirement in collaborative, multi-user applications where users may dynamically join and leave a collaborative session and expect predictable join times and interactive response time even in the presence of slow or unreliable clients. We show that the overheads incurred by a multicast service in managing each group's shared state can be made minimal and that the multicast service does not have to be aware of the semantics of the group's state. We present the design of such a multicast service, present performance results, and discuss how it meets the various needs of collaborative applications.



Closest Pair for Two Separated Sets of Points

Let P and Q two distinct sets of points separated by a straight line on the 2D space or by a plane on the 3D space. A closest pair of points according to their rectilinear distance, one from P and the other from Q, is computed with time complexity O(n log^d-1 n), where d is the dimension of the space. The worst and best case distributions of the points in P and Q are determined and a generalization to higher than three dimensions is suggested.






last updated 09/01/98, .