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.
.