Search

In a large-scale multimedia storage system (LMSS) where client requests for dFfferent multimedia objects may have different demands, the placement and replication of the objects is an important factor, as it may result in an imbalance in server loading across the system. Since replication management and load balancing are all the more crucial issues in multimedia systems, in the literature, these problems are handled by centralized servers. Each object storage server (OSS) responds to the requests that come from the centralized servers independently and has no communication with other OSSs in the system. In this paper, we design a novel distributed load balancing strategy for LMSS, in which OSSs can cooperate to achieve higher performance. Such OSS modeled as an M/G/m system can replicate the objects to and balance the requests among other servers to achieve a near-optimal average waiting time (AWT) of the requests in the system. We validate the performance of the system via rigorous simulations with respect to several influencing factors and prove that our proposed strategy is scalable, flexible, and efficient for real-life applications. Index Terms--Multimedia storage system, request balancing, distributed system, average waiting time, queuing theory.

Distributed systems generate a large amount of monitoring data such as log files to track their operational status. However, it is hard to correlate such monitoring data effectively across distributed systems and along observation time for system management. In previous work, we proposed a concept named flow intensity to measure the intensity with which internal monitoring data reacts to the volume of user requests. We calculated flow intensity measurements from monitoring data and proposed an algorithm to automatically search constant relationships between flow intensities measured at various points across distributed systems. If such relationships hold all the time, we regard them as invariants of the underlying systems. Invariants can be used to characterize complex systems and support various system management tasks. However, the computational complexity of the previous invariant search algorithm is high so that it may not scale well in large systems with thousands of measurements. In this paper, we propose two efficient but approximate algorithms for inferring invariants in large-scale systems. The computational complexity of new randomized algorithms is significantly reduced, and experimental results from a real system are also included to demonstrate the accuracy and efficiency of our new algorithms. Index Terms--Distributed systems, monitoring data, time series, data management, invariants, randomized algorithms, computational complexity.

Advance reservations are a useful method to allocate resources of various kinds in many different environments. Among others, a major advantage of this kind of reservation is the improved admission probability for requests that are made sufficiently early. In order to implement reliable admission control for these requests, it is important to store information in data structures about future allocations and to provide fast access to the available information. In this paper, two data structures are examined: a tree specially designed to support advance reservations is compared to arrays. Both structures are examined analytically and by measurements in a realistic network management system capable of advance reservations. It turns out that arrays are far better suited to support the required operations, in particular when large time intervals need to be scanned. Index Terms--Performance evaluation, arrays, trees, network management, advance reservations, distributed applications.

In any distributed processing environment, decisions need to be made concerning the assignment of computational task modules to various processors. Many versions of the task allocation problem have appeared in the literature. Intertask communication makes the assignment decision difficult; capacity limitations at the processors increase the difficulty. This problem is naturally formulated as a nonlinear integer program, but can be linearized to take advantage of commercial integer programming solvers. While traditional approaches to linearizing the problem perform well when only a few tasks communicate, they have considerable difficulty solving problems involving a large number of intercommunicating tasks. This paper introduces new mixed integer formulations for three variations of the task allocation problem. Results from extensive computational tests conducted over real and generated data indicate that the reformulations are particularly efficient when a large number of tasks communicate, solving reasonably large problems faster than other exact approaches available. Index Terms--Task allocation, nonlinear optimization, integer programming.

Atomic Broadcast is a fundamental problem of distributed systems: It states that messages must be delivered in the same order to their destination processes. This paper describes a solution to this problem in asynchronous distributed systems in which processes can crash and recover. A Consensus-based solution to Atomic Broadcast problem has been designed by Chandra and Toueg for asynchronous distributed systems where crashed processes do not recover. We extend this approach: It transforms any Consensus protocol suited to the crash-recovery model into an Atomic Broadcast protocol suited to the same model. We show that Atomic Broadcast can be implemented requiring few additional log operations in excess of those required by the Consensus. The paper also discusses how additional log operations can improve the protocol in terms of faster recovery and better throughput. To illustrate the use of the protocol, the paper also describes a solution to the replica management problem in asynchronous distributed systems in which processes can crash and recover. The proposed technique makes a bridge between established results on Weighted Voting and recent results on the Consensus problem. Index Terms--Distributed fault-tolerance, asynchronous systems, atomic broadcast, consensus, crash/recovery, quorum, replica management, weighted voting.

Distributed locking is commonly adopted for performing concurrency control in distributed systems. It incorporates additional steps for handling deadlocks. This activity is carried out by methods based on wait-for-graphs or probes. The present study examines detection of conflicts based on enhanced local processing for distributed concurrency control. In the proposed 'edge detection' approach, a graph-based resolution of access conflicts has been adopted. The technique generates a uniform wait-for precedence order at distributed sites for transactions to execute. The earlier methods based on serialization graph testing are difficult to implement in a distributed environment. The edge detection approach is a fully distributed approach. It presents a unified technique for locking and deadlock detection exercises. The technique eliminates many deadlocks without incurring message overheads. Index Terms--Concurrency control, deadlock avoidance, distributed algorithms, distributed databases, nonblocking protocols, serializability.

When a group {I, ..., [I.sub.n]} of individuals wishes to collaboratively construct a complex multimedia document, the first requirement is that they be able to manipulate media-objects created by one another. For instance, if individual [I.sub.j] wishes to access some media objects present at participant [I.sub.k]'s site, he must be able to: 1) retrieve this object from across the network, 2) ensure that the object is in a form that is compatible with the viewing/editing resources he has available at his node, and 3) ensure that the object has the desired quality (such as image size and resolution). Furthermore, he must be able to achieve these goals at the lowest possible cost. In this paper, we develop a theory of media objects, and present optimal algorithms for collaborative object sharing/synthesis of the sort envisaged above. We then extend the algorithms to incorporate quality constraints (such as image size) as well as distribution across multiple nodes. The theoretical model is validated by an experimental implementation that supports the theoretical results. Index Terms - Multimedia networks, active networks, multimedia object delivery, quality of service guarantees, multimedia collaboration, multimedia authoring, distributed systems.

In this paper, we describe a high assurance discretionary access control model for object-oriented systems. The model not only ensures protection against Trojan horses leaking information, but provides the flexibility of discretionary access control at the same time. The basic idea of our approach is to check all information flows among objects in the system in order to block possible illegal flows. An illegal flow arises when information is transmitted from one object to another object in violation of the security policy. The interaction modes among objects are taken into account in determining illegal flows. We consider three different interaction modes that are standard interaction modes found in the open distributed processing models. The paper presents formal definitions and proof of correctness of our flow control algorithm. Index Terms - Object-oriented databases and systems, security, discretionary access control, mandatory access control, Trojan horse, distributed processing.

In some environments, it is more difficult for distributed systems to cooperate. In fact, some distributed systems are highly heterogeneous and might not readily cooperate. In order to alleviate these problems, we have developed an environment that preserves the autonomy of the local systems, while enabling distributed processing. This is achieved by 1) modeling the different application systems into a central knowledge base (called a Metadatabase), 2) providing each application system with a local knowledge processor, and 3) distributing the knowledge within these local shells. This paper is concerned with describing the knowledge decomposition process used for its distribution. The decomposition process is used to minimize the needed cooperation among the local knowledge processors, and is accomplished by 'serializing' the rule execution process. A rule is decomposed into a ordered set of subrules, each of which is executed in sequence and located in a specific local knowledge processor. The goals of the decomposition algorithm are to minimize the number of subrules produced, hence reducing the time spent in communication, and to assure that the sequential execution of the subrules is 'equivalent' to the execution of the original rule. Index Terms - Heterogeneous distributed database management systems, production systems, autonomous systems, distributed knowledge processing, knowledge distribution, Metadatabase.

Replicated data management systems adopt the 1-copy serializability criteria for processing transactions. In order to achieve this goal, many approaches rely on obtaining votes from other sites for processing update requests. In the proposed approach, a technique for generation of precedence graphs for each transaction execution is analyzed. The transaction data flow graph approach is a fully distributed approach. The proposed technique, is free from deadlocks, and avoids resubmission of transactions. Index Terms - Availability, distributed algorithms, fault tolerance, nonblocking protocols, reliability, replicated databases, time-critical transactions, serializability.

A systematic approach has been developed to construct neural networks for qualitative analysis and reasoning. These neural networks are used as specialized parallel distributed processors for solving constraint satisfaction problems. A typical application of such a neural network is to determine a reasonable change of a system after one or more of its variables are changed. A six-node neural network is developed to represent fundamental qualitative relations. A larger neural network can be constructed hierarchically for a system to be modeled by using six-node neural networks as building blocks. The complexity of the neural network building process is thus kept manageable. An example of developing a neural network reasoning model for a transistor equivalent circuit is demonstrated. The use of this neural network model in the equivalent circuit parameter extraction process is also described. Index Terms - Knowledge representation, qualitative reasoning, constraint satisfaction, parallel distributed processing, neural networks, expert systems.

The allocation of data and operations to nodes in a computer communications network is a critical issue in distributed database design. An efficient distributed database design must trade off performance and cost among retrieval and update activities at the various nodes. It must consider the concurrency control mechanism used as well as capacity constraints at nodes and on links in the network. It must determine where data will be allocated, the degree of data replication, which copy of the data will be used for each retrieval activity, and where operations such as select, project, join, and union will be performed. We develop a comprehensive mathematical modeling approach for this problem. The approach first generates units of data (file fragments) to be allocated from a logical data model representation and a characterization of retrieval and update activities. Retrieval and update activities are then decomposed into relational operations on these fragments. Both fragments and operations on them are then allocated to nodes using a mathematical modeling approach. The mathematical model considers network communication, local processing, and data storage costs. A genetic algorithm is developed to solve this mathematical formulation. Index Terms - Distributed database design, data partitioning and replication, data allocation, operation allocation, performance modeling and analysis, genetic algorithm.

We consider a distributed database with partial replication of data objects located on a ring network. Certain placements of replicated objects are shown to optimize the probability of read-only success and the probability of write-only success. We also obtain optimal placements for k-terminal reliability and expected minimal path length for read-only and write-only operations. Index Terms - Optimality, distributed databases, partitions, replication, ring topology

Data availability and security are two important issues in a distributed database system. Existing schemes achieve high availability at the expense of higher storage cost and data security at the expense of higher processing cost. In this concise paper, we develop an integrated methodologv that combines the features of some existing schemes dealing with data fragmentation, data encoding, partial replication, and quorum consensus concepts to achieve storage efficient, highly available, and secure distributed database systems.

This paper deals with I/O throughput maximization in a single processor/multidisk database system, by means of optimal allocation of entire relations (or other nonfragmented data objects) to disks. We examine the cases in which such allocation is beneficial, and present a mathematical formulation of the problem. This formulation is shown to be flexible enough to accommodate various objectives and constraints of a typical system design.

This paper explores the specification and semantics of multiagent problem-solving systems, focusing on the representations that agents have of each other. It provides a declarative representation for such systems. Several procedural solutions to a well-known test-bed problem are considered, and the requirements they impose on different agents are identified. A study of these requirements yields a representational scheme based on temporal logic for specifying the acting, perceiving, communicating, and reasoning abilities of computational agents. A formal semantics is provided for this scheme. The resulting representation is highly declarative, and useful for describing systems of agents solving problems reactively.

In this paper, we explore the approach to applying a combination of join and semi-join operations to minimize the amount of data transmission required for distributed query processing. Specifically, we identify and exploit two important concepts which occur with the use of join operations as reducers in query processing, namely, gainful semi-joins and pure join attributes. Some semi-joins, though not profitable themselves, may benefit the execution of subsequent join operations, and become profitable owing to the use of join operations as reducers. Such a semi-join is termed a gainful semi-join. In addition, join attributes which are not part of the output attributes are referred to as pure join attributes. We shall not only exploit the usefulness of gainful semi-joins, but also utilize the removability of pure join attributes to reduce the amount of data transmission required for query processing. Moreover, in light of the two concepts, heuristic searches are developed to determine a sequence of join and semi-join reducers for query processing. Our results show the importance of the approach to combining joins and semi-joins for distributed query processing.

The paper is concerned with the parallel evaluation of datalog rule programs, mainly by processors that are interconnected by a communication network. A paradigm, called data-reduction, for the parallel evaluation of a datalog program, is introduced. Parallelization is by partitioning the rule-instantiations among the processors. After presenting the paradigm, its implementation with seminaive evaluation, its communication overhead, and its application to stratified-negation datalog programs are discussed. It is proven that decomposability, a related concept introduced in previous works, is undecidable.

An algorithm is described in this paper for garbage collection in distributed systems with object sharing across processor boundaries. The algorithm allows local garbage collection at each node in the system to proceed independently of local collection at the other nodes. It requires no global synchronization or knowledge of the global state of the system and exhibits the capability of graceful degradation. The concept of a specialized dump node is proposed to facilitate the collection of inaccessible circular structures. An experimental evaluation of the algorithm is also described. The algorithm is compared with a corresponding scheme that requires global synchronization. The results show that the algorithm works well in distributed processing environments even when the locality of object references is low.

Traditionally, the problems of Byzantine agreement, concensus, and interactive consistency are studied in a fully connected network with processors in malicious failure only. Such problems are re-examined with the assumption of malicious faults on both processors and links. The proposed protocols use the minimum number of message exchanges and can tolerate the maximum number of allowable faulty components to make each fault-free processor reach a common agreement for the cases of processor failure, link failure, or processor and link failure. Index Terms--Byzantine agreement, consensus, interactive consistency, fault tolerance, distributed processing, synchronization.

In this work, the Parallel Fast Condensed Nearest Neighbor (PFCNN) rule, a distributed method for computing a consistent subset of a very large data set for the nearest neighbor classification rule is presented. In order to cope with the communication overhead typical of distributed environments and to reduce memory requirements, different variants of the basic PFCNN method are introduced. An analysis of spatial cost, CPU cost, and communication overhead is accomplished for all the algorithms. Experimental results, performed on both synthetic and real very large data sets, revealed that these methods can be profitably applied to enormous collections of data. Indeed, they scale up well and are efficient in memory consumption, confirming the theoretical analysis, and achieve noticeable data reduction and good classification accuracy. To the best of our knowledge, this is the first distributed algorithm for computing a training set consistent subset for the nearest neighbor rule. Index Terms--Classification, parallel and distributed algorithms, nearest neighbor rule, data condensation.

Distributed information processing, in many world wide web applications, requires access, transfer, and synchronization of large multimedia data objects (MDOs) (such as, audio, video, and images) across the communication network. Moreover, the end users have started expecting very fast response times and high quality of service. Since the transfer of large MDOs across the communication network contributes to the response time observed by the end users, the problem of allocating these MDOs so as to minimize the response time becomes very challenging. This problem becomes more complex in the context of hypermedia documents (web pages), wherein the MDOs need to be synchronized during presentation to the end users. Note that the basic problem of data allocation in distributed database environments is NP-complete. Therefore, there is a need to pursue and evaluate solutions based on heuristics which generate near-optimal MDO allocation. In this paper, we address this problem by: 1) conceptualizing this problem by using a navigational model to represent hypermedia documents and their access behavior from end users, and by capturing the synchronization requirements on MDOs, 2) formulating the problem by developing a base case cost model for response time, and generalizing it to incorporate user interaction and buffer memory constraints, 3) designing two algorithms to find near-optimal solutions for allocating MDOs of the hypermedia documents while adhering to the synchronization requirements, and 4) evaluating the trade-off between the time complexity to get the solution and the quality of solution by comparing the solutions generated by the algorithms with the optimal solutions generated through an exhaustive search. Index Terms - Data allocation, response time, multimedia data objects, hypermedia documents, distributed hypermedia document systems, navigational model.

In this paper we introduce the concept of continual queries, describe the design of a distributed event-driven continual query system - OpenCQ, and outline the initial implementation of OpenCQ on top of the distributed interoperable information mediation system DIOM [22], [20]. Continual queries are standing queries that monitor update of interest and return results whenever the update reaches specified thresholds. In OpenCQ, users may specify to the system the information they would like to monitor (such as the events or the update thresholds they are interested in). Whenever the information of interest becomes available, the system immediately delivers it to the relevant users; otherwise, the system continually monitors the arrival of the desired information and pushes it to the relevant users as it meets the specified update thresholds. In contrast to conventional pull-based data management systems such as DBMSs and Web search engines, OpenCQ exhibits two important features: 1. it provides push-enabled, event-driven, content-sensitive information delivery capabilities, and 2. it combines pull and push services in a unified framework. By event-driven we mean that the update events of interest to be monitored are specified by users or applications. By content-sensitive, we mean the evaluation of the trigger condition happens only when a potentially interesting change occurs. And, by push-enabled, we mean the active delivery of query results or triggering of actions without user intervention. Index terms - Distributed information systems, Internet scale information delivery, World Wide Web technology, distributed triggers, event monitoring.

Concurrency control is one of the key problems in design and implementation of collaborative systems such as hypertext/hypermedia systems, CAD/CAM systems, and software development environments. Most existing systems store data in specialized databases with built-in concurrency control policies, usually implemented via locking. It is desirable to construct such collaborative systems on top of the World Wide Web, but most Web servers do not support even conventional transactions, let alone distributed (multi-Website) transactions or flexible concurrency control mechanisms oriented toward teamwork - such as event notification, shared locks, and fine granularity locks. We present a transaction server that operates independently of Web servers or the collaborative systems, to fill the concurrency control gap. By default, the transaction server enforces the conventional atomic transaction model, where sets of operations are performed in an all-or-nothing fashion and isolated from concurrent users. The server can be tailored dynamically to apply more sophisticated concurrency control policies appropriate for collaboration. The transaction server also supports applications employing information resources other than Web servers, such as legacy databases, CORBA objects, and other hypermedia systems. Our implementation permits a wide range of system architecture styles. Index Terms - Distributed transactions, extended transaction models, WWW, computer-supported collaborative work, middleware.

High-bandwidth and real-time constraints for supporting concurrent video accesses make generic software architecture design for high-performance on-demand video servers challenging. This challenging task can be even more complicated when we consider that a generic software architecture should be applied to different hardware platforms. In this paper, we introduce the design, implementation, and evaluation of a generic software architecture for on-demand video servers. We describe different key components on controlling the storage and network devices within the server. The interactive collaborations between these software components are also illustrated. The experimental results indicate a very promising direction on exploring the right combinations of these software components. The server is, thus, able to increase the number of concurrent video accesses with the same hardware configuration. For instance, with the right combinations, the system achieved about 80 percent of the storage system bandwidth of four disks, about 70 percent of the storage system bandwidth of six disks, and generally reached the maximal achieved SCSI bandwidth when eight disks are used over two SCSI buses (i.e., four disks on each SCSI bus). Our research and experimental results are based on video servers currently under construction across a variety of hardware platforms, including SMP, DMP, and clusters of PC or workstations. The most-advanced prototype server is based on an SGI shared-memory multiprocessor with a mass storage system consisting of RAID-3 disk arrays. With all the enabling/management schemes, we were able to further investigate interesting research issues by considering the user's access profiles for taking advantage of popular video titles. The results were significant, with a range of 60 percent improvement given a 512 Kbyte block size. In addition to the experimental results, theoretical performance models were also developed that closely match to our collected experimental results. Index Terms - Experimental systems, system integration and management, distributed multimedia systems.

A study was conducted to analyze applications for cooperative multiagent systems and principles underlying their design. Problems associated with the development of cooperative multiagent systems were examined. In addition, issues and challenges related to the semantic interoperability of agents and the development of a novel protocol for specific interactions were discussed. Results indicated the significant potential of using multiagent systems technology in computer science.