Transdisciplinary research is a rapidly expanding part of science and engineering, demanding new methods for connecting results across fields. In biomedicine for example, modeling complex biological systems requires linking knowledge across multiple levels of science, from genes to disease. The move to multilevel research requires new strategies; in this paper we present path knowledge discovery, a novel methodology for linking published research findings. Path knowledge discovery consists of two integral tasks: 1) association path mining among concepts in a multipart lexicon that crosses disciplines, and 2) fine-granularity knowledge-based content retrieval along the path(s) to permit deeper analysis. Implementing this methodology has required development of innovative measures of association strength for pairwise associations, as well as the strength for sequences of associations, in addition to powerful lexicon-based association expansion to increase the scope of matching. In our discussions, we describe the validation of the methodology using a published heritability study from cognition research, and we obtain comparable results. We show how path knowledge discovery can greatly reduce a domain expert's time (by several orders of magnitude) when searching and gathering knowledge from the published literature, and can facilitate derivation of interpretable results.

Malicious users can exploit the correlation among data to infer sensitive information from a series of seemingly innocuous data accesses. Thus, we develop an inference violation detection system to protect sensitive data content. Based on data dependency, database schema and semantic knowledge, we constructed a semantic inference model (SIM) that represents the possible inference channels from any attribute to the pre-assigned sensitive attributes. The SIM is then instantiated to a semantic inference graph (SIG) for query-time inference violation detection. For a single user case, when a user poses a query, the detection system will examine his/her past query log and calculate the probability of inferring sensitive information. The query request will be denied if the inference probability exceeds the prespecified threshold. For multi-user cases, the users may share their query answers to increase the inference probability. Therefore, we develop a model to evaluate collaborative inference based on the query sequences of collaborators and their task-sensitive collaboration levels. Experimental studies reveal that information authoritativeness, communication fidelity and honesty in collaboration are three key factors that affect the level of achievable collaboration. An example is given to illustrate the use of the proposed technique to prevent multiple collaborative users from deriving sensitive information via inference.

Indexing XML is crucial for efficient XML query processing. We propose a compact tree (Ctree) for XML indexing, which provides not only concise path summaries at group level but also detailed child-parent relationships at element level. Based on Ctree, we are able to measure how well XML data is structured. We also propose a three-step query processing method. Its efficiency is achieved by: (1) summarizing large XML data structures into a condensed Ctree; (2) pruning irrelevant groups to significantly reduce the search space; (3) eliminating join operations between the matches for value predicates and those for structure constraints and (4) using Ctree properties such as regular groups to reduce query processing time. Our experiments reveal that Ctree is an effective data structure for managing XML data.

An ever-increasing amount of valuable information is stored in Web databases, "hidden" behind search interfaces. To save the user's effort in manually exploring each database, metasearchers automatically select the most relevant databases to a user's query. In this paper, we focus on one of the technical challenges in metasearching, namely database selection. Past research uses a precollected summary of each database to estimate its "relevancy" to the query, and in many cases make incorrect database selection. In this paper, we propose two techniques: probabilistic relevancy modelling and adaptive probing. First, we model the relevancy of each database to a given query as a probabilistic distribution, derived by sampling that database. Using the probabilistic model, the user can explicitly specify a desired level of certainty for database selection. The adaptive probing technique decides which and how many databases to contact in order to satisfy the user's requirement. Our experiments on real hidden-Web databases indicate that our approach significantly improves the accuracy of database selection at the cost of a small number of database probing.

Indexing and ranking are two key factors for efficient and effective XML information retrieval. Inappropriate indexing may result in false negatives and false positives, and improper ranking may lead to low precisions. In this paper, we propose a configurable XML information retrieval system, in which users can configure appropriate index types for XML tags and text contents. Based on users' index configurations, the system transforms XML structures into a compact tree representation, Ctree, and indexes XML text contents. To support XML ranking, we propose the concepts of "weighted term frequency" and "inverted element frequency," where the weight of a term depends on its frequency and location within an XML element as well as its popularity among similar elements in an XML dataset. We evaluate the effectiveness of our system through extensive experiments on the INEX 03 dataset and 30 content and structure (CAS) topics. The experimental results reveal that our system has significantly high precision at low recall regions and achieves the highest average precision (0.3309) as compared with 38 official INEX 03 submissions using the strict evaluation metric.

Based on techniques in information retrieval, we discuss the methods for knowledge acquisition from the documents composed of both fixed and free formats. The documents with the fixed format imply items with those selected from the sentences, words, symbols, or numbers, while the documents with free format are with the usual text. In this paper, starting with the item-document matrix and term-document matrix used for the representation of a document set, we propose a new method for knowledge acquisition taking simultaneously into account of both fixed and free formats. A method based on the probabilistic latent semantic indexing (PLSI) model is used for clustering a set of documents. The proposed method is applied to a document set given by the questionnaires of students taken for the purpose of faculty development. We show the effectiveness of the proposed method compared to the conventional method.

Two algorithms, called NeT and CoT, to translate relational schemas to XML schemas using various semantic constraints are presented. The XML schema representation we use is a language-independent formalism named XSchema, that is both precise and concise. A given XSchema can be mapped to a schema in any of the existing XML schema language proposals. Our proposed algorithms have the following characteristics: (1) NeT derives a nested structure from a flat relational model by repeatedly applying the nest operator on each table so that the resulting XML schema becomes hierarchical, and (2) CoT considers not only the structure of relational schemas, but also semantic constraints such as inclusion dependencies during the translation. It takes as input a relational schema where multiple tables are interconnected through inclusion dependencies and converts it into a good XSchema. To validate our proposals, we present experimental results using both real schemas from the UCI repository and synthetic schemas from TPC-H.

Two conversion algorithms, called NeT and COT, to translate relational schemas to XML schemas using various semantic constraints are presented. We first present a language-independent formalism named XSchema so that our algorithms are able to generate output schema in various XML schema language proposals. The benefits of such a formalism are that it is both precise and concise. Based on the XSchema formalism, our proposed algorithms have the following characteristics: (1) NeT derives a nested structure from a flat relational model by repeatedly applying the nest operator so that the resulting XML schema becomes hierarchical, and (2) COT considers not only the structure of relational schemas, but also inclusion dependencies during the translation so that relational schemas where multiple tables are interconnected through inclusion dependencies can also be handled.

Maximal frequent itemsets (MR) are crucial to many tasks in data mining. Since the MaxMiner algorithm first introduced enumeration trees for mining MR in 1998, several methods have been proposed to use depth first search to improve performance. To further improve the performance of mining MR, we proposed a technique that takes advantage of the information gathered from previous steps to discover new MR. More specifically, our algorithm called SmartMiner gathers and passes tail information and uses a heuristic select function which uses the tail information to select the next node to explore. Compared with Mafia and GenMax, SmartMiner generates a smaller search tree, requires a smaller number of support counting, and does not require superset checking. Using the datasets Mushroom and Connect, our experimental study reveals that SmartMiner generates the same MFI as Mafia and GenMax, but yields an order of magnitude improvement in speed.

This paper proposes a new novel method for similarity search that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. Previous methods for processing similarity search that supports time warping fail to employ multi-dimensional indexes without false dismissal since the time warping distance does not satisfy the triangular inequality. Our primary goal is to innovate on search performance without permitting any false dismissal. To attain this goal, we devise a new distance function D/sub tw-lb/ that consistently underestimates the time warping distance and also satisfies the triangular inequality D/sub tw-lb/ uses a 4-tuple feature vector that is extracted from each sequence and is invariant to time warping. For efficient processing of similarity search, we employ a multi-dimensional index that uses the 4-tuple feature vector as indexing attributes and D/sub tw-lb/ as a distance function. The extensive experimental results reveal that our method achieves significant speedup up to 43 times with real-world S&P 500 stock data and up to 720 times with very large synthetic data.

Efficient algorithms to mine frequent patterns are crucial to many tasks in data mining. Since the Apriori algorithm was proposed (R. Agrawal and R. Srikant, 1994), there have been several methods proposed to improve its performance. However, most still adopt its candidate set generation-and-test approach. We propose a pattern decomposition (PD) algorithm that can significantly reduce the size of the dataset on each pass, making it more efficient to mine frequent patterns in a large dataset. The proposed algorithm avoids the costly process of candidate set generation and saves time by reducing dataset. Our empirical evaluation shows that the algorithm outperforms Apriori by one order of magnitude and is faster than FP-tree. Further, PD is more scalable than both Apriori and FP-tree.

We propose an indexing technique for fast retrieval of similar subsequences using time warping distances. A time warping distance is a more suitable similarity measure than the Euclidean distance in many applications, where sequences may be of different lengths or different sampling rates. Our indexing technique uses a disk-based suffix tree as an index structure and employs lower-bound distance functions to filter out dissimilar subsequences without false dismissals. To make the index structure compact and thus accelerate the query processing, we convert sequences of continuous values to sequences of discrete values via a categorization method and store only a subset of suffixes whose first values are different from their preceding values. The experimental results reveal that our proposed technique can be a few orders of magnitude faster than sequential scanning.

Current large-scale information sources are designed to support general queries and lack the ability to support scenario-specific information navigation, gathering, and presentation. As a result, users are often unable to obtain desired specific information within a well-defined subject area. Today's information systems do not provide efficient content navigation, incremental appropriate matching, or content correlation. We are developing the following innovative technologies to remedy these problems: 1) scenario-based proxies, enabling the gathering and filtering of information customized for users within a pre-defined domain; 2) context-sensitive navigation and matching, providing approximate matching and similarity links when an exact match to a user's request is unavailable; 3) content correlation of documents, creating semantic links between documents and information sources; and 4) user models for customizing retrieved information and result presentation. A digital medical library is currently being constructed using these technologies to provide customized information for the user. The technologies are general in nature and can provide custom and scenario-specific information in many other domains (e.g., crisis management).

A semantic caching scheme suitable for wrappers wrapping web sources is presented. Since the web sources have typically weaker querying capabilities than conventional databases, existing semantic caching schemes cannot be applied directly. A seamlessly integrated query translation and capability mapping between the wrappers and web sources in semantic caching is described. In addition, an analysis on the match types between the user's input query and cached queries is presented. Semantic knowledge acquired from the data can be used to avoid unnecessary access to the web sources by transforming the cache miss to the cache hit. A polynomial time algorithm based on the proposed query matching technique is presented to find the best matched query in the cache. Experimental results reveal the effectiveness of the proposed semantic caching scheme.

Machine learning induction algorithms are difficult to scale to very large databases because of their memory-bound nature. Using virtual memory results in a significant performance degradation. To overcome such shortcomings, we developed a classification rule induction algorithm for relational databases. Our algorithm uses a bottom-up rule generation strategy that is more effective for mining databases having large cardinality of nominal variables. We have successfully used our algorithm to mine a retail grocery database containing more than 1.6 million records in about 5 hours on a dual Pentium processor PC.

A knowledge-based approach to retrieve medical images by feature and content with spatial and temporal constructs is developed. Selected objects of interest in an image are segmented and contours are generated. Features and content are extracted and stored in a database. Knowledge about image features can be expressed as a type abstraction hierarchy (TAH), the high-level nodes of which represent the most general concepts. Traversing TAH nodes allows approximate matching by feature and content if an exact match is not available. TAHs can be generated automatically by clustering algorithms based on feature values in the databases and hence are scalable to large collections of image features. Since TAHs are generated based on user classes and applications, they are context- and user-sensitive. A knowledge-based semantic image model is proposed to represent the various aspects of an image object's characteristics. The model provides a mechanism for accessing and processing spatial, evolutionary and temporal queries. A knowledge-based spatial temporal query language (KSTL) has been developed that extends ODMG's OQL and supports approximate matching of features and content, conceptual terms and temporal logic predicates. Further, a visual query language has been developed that accepts point-click-and-drag visual iconic input on the screen that is then translated into KSTL. User models are introduced to provide default parameter values for specifying query conditions. We have implemented the KMeD (Knowledge-based Medical Database) system using these concepts.

The authors take a real world application from a text database and present a case history. The techniques ultimately led to a discovery contradicting an accepted paradigm in seismology. Using simple, tailored, keyword extraction, they examined a text collection of earthquake data. A discovery was made when an unusual pattern emerged from the text. They then tested a more comprehensive numerical database, treating the the text discovery as a hypothesis. It was verified using a standard /spl chi//sup 2/ statistic. The hypothesis was significant earthquakes in the longitude regions that include California, occur more often in the morning hours than any other time of day.

A knowledge based approach is introduced for retrieving images by content. It supports the answering of conceptual image queries involving similar-to predicates, spatial semantic operators, and references to conceptual terms. Interested objects in the images are represented by contours segmented from images. Image content such as shapes and spatial relationships are derived from object contours according to domain specific image knowledge. A three layered model is proposed for integrating image representations, extracted image features, and image semantics. With such a model, images can be retrieved based on the features and content specified in the queries. The knowledge based query processing is based on a query relaxation technique. The image features are classified by an automatic clustering algorithm and represented by Type Abstraction Hierarchies (TAHs) for knowledge based query processing. Since the features selected for TAH generation are based on context and user profile, and the TAHs can be generated automatically by a clustering algorithm from the feature database, our proposed image retrieval approach is scalable and context sensitive. The performance of the proposed knowledge based query processing is also discussed.

This paper proposes the use of a type abstraction hierarchy as a framework for deriving cooperative query answers. The type abstraction hierarchy integrates the abstraction view with the subsumption (is-a) and composition (part-of) views of a type hierarchy. Such a framework provides multilevel object representation, which is an important aspect of cooperative query answering. The concept of pattern that specifies one or more conditions on an object is also proposed. Patterns have smaller granularity than types, and thus provide more specific semantic information. Cooperative query answering consists of query relaxation, generalization, specialization, and association on patterns. Query relaxation can be explicitly specified by the user or implicitly performed by the system. The implicit and explicit relaxations can also be combined and performed interactively by both the system and the user. CSQL, an extension of SQL for cooperative query answering, is also proposed. Preliminary experimental results reveal that the proposed type abstraction hierarchy provides an organized structure representing concepts at different knowledge levels in various domains, and provides a systematic and efficient method for cooperative query answering.>

CoBase, a cooperative database, is a new type of distributed database that integrates knowledge base technology with database systems to provide cooperative (approximate and conceptual) query answering. Based on the database schema and application characteristics, data are organized into conceptual (type abstraction) hierarchies. The higher levels of the hierarchy provide a more abstract data representation than the lower levels. Generalization (moving up in the hierarchy), specialization (moving down in the hierarchy) and association (moving between hierarchies) are the three key operations in deriving cooperative query answers.

An approach to vertical partitioning in relational databases in which the attributes of a relation are partitioned according to a set of transactions is proposed. The objective of vertical partitioning is to minimize the number of disk accesses in the system. Since transactions have more semantic meanings than attributes, this approach allows the optimization of the partitioning based on a selected set of important transactions. An optimal binary partitioning (OBP) algorithm based on the branch and bound method is presented, with the worst case complexity of O(2/sup n/), where n is the number of transactions. To handle systems with a large number of transactions, an algorithm BPi with complexity varying from O(n) to O(2/sup n/) is also developed. The experimental results reveal that the performance of vertical partitioning is sensitive to the skewness of transaction accesses. Further, BPi converges rather rapidly to OBP. Both OBP and BPi yield results comparable with that of global optimum obtained from an exhaustive search.>

The authors present a temporal evolutionary object-oriented data model (TEDM) for modeling medical images. The intelligent medical image management system (IMIS) lies on top of a picture archive and communication system (PACS) infrastructure. The IMIS can retrieve medical images (e.g. X-rays, computed tomography scans, magnetic resonance scans, etc.) by image features and contents rather than by traditional artificial keys such as a patient hospital identification number. As a result, solutions to queries which associate the radiographic findings of an image, the disease pathology and the categorical patient subpopulation can be obtained. The proposed model and language constructs can also be applied to other domains that exemplify the evolutionary transformations of objects, such as modeling the growth of brain tumors.>

The authors investigate the problem of object allocation in a distributed environment with virtually replicated data. The traditional approach to improving data availability in a distributed system is to replicate data. A high degree of replication, however, imposes a serious burden to the system when updates are performed. Data inference can be used to reduce the degree of replication in the system while still providing high data availability. A model to allocate objects under such an environment is proposed. Rules based on application semantics are developed to reduce the search space for optimal allocation. Heuristic algorithms are proposed for allocation when the reduced search space is still prohibitively large. Examples are given to illustrate the effectiveness of the proposed algorithms.>

A new approach is presented that uses knowledge induction and type inference to provide intensional answers. Machine learning techniques are used to analyze database contents and to induce a set of if-then rules. Type inference which is based on forward inference and backward inference is developed that uses database type hierarchies to derive the intensional answers for a query. It is shown that more precise intensional answers can be derived by properly merging the type inference results from multiple type hierarchies. A prototype intensional query-processing system which uses the proposed approach has been implemented. Using a ship database as a testbed, the effectiveness of the use of type interference and induced rules to derive specific intensional answers is demonstrated.>

An analytic model is proposed for estimating task response times in distributed systems with resource contentions. The model consists of two submodels. The first submodel is an extended queuing network model used for approximating module response times. This submodel is solved by a decomposition technique which reduces the computational complexity by two to three orders of magnitude when compared with a direct approach. The second submodel is a weighted control-flow graph model from which task response time can be obtained by aggregating module response time in accordance with the precedence relationships. Task response times estimated by the analytic model compare closely with simulation results. It is shown that resource contention delays depend on the availability of resources as well as on the invocation rates and response times of the modules that use the resources. The model can be used to study the tradeoffs among module assignments, scheduling policies, interprocessor communications, and resource contentions in distributed processing systems.>

A knowledge-gased approach for query processing during network partitioning is proposed. The approach uses available domain and summary knowledge to infer inaccessible data to answer a given query. A rule induction technique is used to extract correlated knowledge between attributes from the database contents. This knowledge is represented as rules for data inference. On the basis of a set of queries, simulation is used to evaluate the effectiveness of the proposed data inference technique for improving data availability under network partitioning. Object allocation has a significant impact on data availability. Allocating objects that increase remote redundancy and reduce local redundancy increases data Availability during network partitioning. A prototype distributed database system that uses the proposed inference technique with correlated knowledge from a ship database has been implemented. Experience indicates that the proposed inference technique can significantly improve the availability of a distributed database during network partitioning.>

Response time is affected by interprocessor communications, precedence relationships among the modules, module assignments, and processor scheduling policies. Furthermore, due to sharing of resources and data among the processors, contention delays are incurred. A task response time model that considers all these factors is proposed. A Petri net is used to represent resource contention, and the task control flow graph represents module precedence and logical relationships. A queuing network with resource contention is used to estimate the response time of each module. Module response time consists of delays at the processors and resource queues and is estimated by approximating the extended queuing network as independent finite capacity queuing systems. The module response time is mapped onto a control flow graph, and task response time is obtained by aggregating the module response times in accordance with their precedence relationship in the control flow graph. The task response time derived from the analytical model compares well with that from the simulation.>

Provides an overview of the technical articles and features presented in this issue.

Two tightly coupled multi-computer testbeds, one providing efficient inter-node communications tailored to the application, and the other providing more flexible full connectivity among processors and memories are used to support validation of the design techniques for distributed real-time systems. The testbeds are valuable tools for evaluating, analyzing, and studying the behavior of many algorithms for distributed systems. We have used the testbeds in studying distributed recovery block scheme for handling hardware and software faults. A testbed has also been used to analyze database locking techniques and a fault-tolerant locking protocol for recovery from faults that occur during updating of replicated copies of files in tightly coupled distributed systems. Testbeds can be configured to represent the operating environments and input scenarios more accurately than software simulation. Therefore, testbed-based evaluation provides more accurate results than simulation and yields greater insight into the characteristics and limitations of proposed concepts. This is an important advantage in the complex field of distributed real-time system design evaluation and validation. Therefore, testbed-based experimentation is an effective approach to validate system concepts and design techniques for distributed systems for real-time applications.

Response time is an important design criterion for real-time systems. A new analytic model is developed to estimate task response time. It considers such factors as interprocessor communication, module precedence relationship, module scheduling, interconnection network delay, and assignment of modules and files to computers. Since module assignment as well as its replication have great impact on task response time, a new algorithm is developed to iteratively search for module assignments and replications that reduce task response time. An objective function is introduced that is based on the sum of task response time and delay penalty for the violations of thread response time requirements. With this objective function, good module allocations and replications, which minimize task response time and yet satisfy the thread response time requirements, can be determined by the proposed algorithm. To validate the algorithm, we compare the assignments generated by the algorithm for some sample distributed systems to the optimal module assignments obtained from exhaustive search. It shows that with a very small number of initial module assignments, our algorithm is able to generate the optimal or close-to-optimal assignments. The algorithm is also applied to a real-time distributed system for space defense applications where exhaustive search for the optimal assignment is not feasible. The generated module assignments (with replications) satisfy the specified thread response times, and compare closely with the simulation results. A series of experiments is also performed to characterize the behavior of the algorithm. In conclusion, the algorithm can serve as a valuable tool for assigning modules with replications for distributed systems.

In a distributed processing system with the application software partitioned into a set of program modules, allocation of those modules to the processors is an important problem. This paper presents a method for optimal module allocation that satisfies certain performance constraints. An objective function that includes the intermodule communication (IMC) and accumulative execution time (AET) of each module is proposed. It minimizes the bottleneck-processor utilization—a good principle for task allocation. Next, the effects of precedence relationship (PR) among program modules on response time are studied. Both simulation and analytical results reveal that the program-size ratio between two consecutive modules plays an important role in task response time. Finally, an algorithm based on PR, AET, and IMC and on the proposed objective function is presented. This algorithm generates better module assignments than those that do not consider the PR effects.

Consistency control protocols can be classified as either pessimistic or optimistic. Pessimistic protocols check for conflicting file accesses before a transaction references shared files; this prevents transaction restarts but adds intercomputer synchronization delays to execution response times TE. Optimistic protocols avoid intercomputer synchronization delays for TE, but existing optimistic protocols repeatedly restart a transaction until it executes without conflict. Repeated restarts lengthen the time to finalize an update TU, and can saturate the computing and communication resources. We present two new optimistic protocols that avoid repeated restarts: the exclusive-writer protocol (EWP) and the exclusive-writer protocol with locking option (EWL). EWP has no transaction restarts, database rollbacks, or deadlocks due to shared data access. But EWP ensures only a limited form of serializability. EWL is an extension of EWP that ensures full serializability. EWL has no database rollbacks. Also, EWL can guarantee that a transaction will be restarted at most once. To further reduce restarts, each site can independently and dynamically switch between primary site locking (PSL), which has no restarts, and EWL. Such switching requires no additional messages or delays to synchronize protocol selection. Analytic models are developed to study the response times (i.e., TEand TU) of EWP, EWL, PSL, and basic timestamps (BTS). Our study reveals that EWP and EWL have the smallest TF since neither requires update-log maintenance (unlike BTS) nor intercomputer synchronization delays for TE(unlike PSL). EWP has the smallest TUunless the cost of communicating and processing updates is high.

Communication among program modules plays an important role in the performance of distributed processing systems. In this paper, a model for estimating intermodule communication (IMC) is developed. The model derives communication volume based on module invocation rates and file access probabilities via the control-and-data-flow graph. The IMC model is validated by simulation experiments. Interprocessor communication (IPC) and system resources utilization can be estimated from the IMC. We show that IMC and IPC are useful in finding good module assignments in distributed processing systems.

The performance (throughput and delay) of the multihop broadcast communication networks is studied via a simulation model that includes channel access, transmission scheduling, buffer, management, and hop-by-hop acknowledgment protocols. The parameters considered are the data and acknowledgment packets transmission probabilities, timeout periods, and buffer sizes. The performance of echo acknowledgment, all-active acknowledgment, and a mixed acknowledgment scheme based on nodes connectivities are also studied.

In a wideband communication channel (> 100 MHz) local network, the propagation delay becomes comparable to the packet transmission time. As a result, CSMA-type protocols may not provide efficient channel utilization. A new channel access protocol, contention based channel reservation (CBCR) that is based on channel reservation is proposed in this paper. Our investigation reveals that the new channel access protocol yields better performance than that of CSMA-type protocols for operating in these high data rate environments. Thus, channel reservation allocation is a good alternative to the contention strategy for high speed local networks.

We analyze the performance of a window multiaccess protocol with collision size feedback. We obtain bounds on the throughput and the expected packet delay, and assess the sensitivity of the performance to collision recognition time and packet transmission time. An approximate optimal window reduction factor to minimize packet isolation time is {equation}, where n is the collision size and R the collision recognition time (in units of packet propagation delay). The WCSF protocol, which requires more information than CSMA-CD, is shown to have at least 30% more capacity than CSMA-CD for high bandwidth channels; that is, when packet transmission time is comparable to propagation delay. The capacity gain of the WCSF protocol decreases as the propagation delay decreases and the collision recognition time increases. Our study also reveals the inherent stability of WCSF. When the input load increases beyond saturation. The throughput remains at its maximum value.

A model is developed for determining the optimal policy for processing a given relational model query. The model is based on operating cost (processing cost and communication cost), which is a function of selection of sites for processing query operations, sequence of operations, file size, and data reduction functions. The optimal policy specifies the site selection and sequence of operations that yield minimum operating cost.

In distributed random access communication, collision occurs when two or more transmissions overlap in time. After a transmission a user should know whether his attempt was successful so that he can decide his next action. Acknowledgments are commonly used to indicate whether a transmission is successful. We study the effect of acknowledgments on the performance of a star broadcast network. We evaluate the network performance for the following four cases: free and instantaneous acknowledgment, common channel for data and acknowledgments, split channel for data and acknowledgments, and a common channel with high-power acknowledgments. Our study reveals that the split channel has the highest capacity, and that the high-power scheme provides an attractive economical alternative when data packets are short.

A tandem queueing system with constant slotted service times and threshold control is modeled and analyzed in this paper. The input to the first queue is controlled by the buffer occupancy of the second queue. When the second queue has more than No customers, the input to the first queue will be rejected. The input to the second queue consists of the output from the first queue and an external input which is assumed to be Poisson distributed. The behavior of such a queueing system is analyzed and portrayed in graphs. The threshold control rejects input traffic to the first queue and avoids congestion at the second queue. As a result, the delay for an arrival to be serviced by both of the queues is much lower than the case without threshold control. As No increases, the system behavior approaches the case of the system without threshold control. Such a queueing model is motivated by congestion control in a computer network. An example is given to illustrate the applications of gateway flow control in internet- working.

A new policy that can effectively handle message routing and flow control simultaneously in a packet switched computer network is presented. In such a policy, a traffic threshold level is assigned for each channel in the network. If all the channels along the preassigned primary route from current node to its destination do not exceed the predetermined traffic threshold, then the primary route is used. Otherwise, alternative route(s) are used to share the traffic load. When all the alternative routes from a source to a destination become unavailable, then the input traffic from that source to that destination is temporarily rejected. Simulation results of the behavior and performance of such a routing and flow control policy are presented. The implementation of the policy is also discussed. Simulation results reveal that this new policy is simpler to implement and yields better performance than that of distributed routing algorithm and buffer allocation flow control policy, which are currently being used in many packet switched networks.

This paper presents a deadlock-free and distributed control algorithm for robustly and consistently updating replicated databases. This algorithm is based on local locking and time stamps on lock tables which permit detection of conflicts among transactions executed at different sites. Messages are exchanged in the network whenever a transaction commitment occurs, that is, at the end of every consistent step of local processing. Conflicts among remote transactions are resolved by a roll back procedure. Local restart is based on a journal of locks which provides backup facilities. Performance in terms of the number of messages and volume of control messages of the proposed algorithm is compared with that of the voting and centralized locking algorithms. These results reveal that the proposed distributed control algorithm performs, in most cases, comparably to the centralized locking algorithm and better than the voting algorithm.

This paper presents a robust, deadlock-free and distributed control algorithm for consistently updating replicated databases. This algorithm is based on local locking and time stamps on lock tables which permit detection of conflicts among transactions executed at replicated databases. Messages are exchanged in the network whenever a transaction commitment occurs, that is, at the end of every consistent step of local processing. Conflicts among remote transactions are resolved by a roll back procedure. Local restart is based on a journal of locks which provides backup facilities. Performance in terms of the number of messages and volume of control messages of the proposed algorithm is compared with that of the voting and centralized locking algorithms. The results reveal that the proposed distributed control algorithm performs, in most cases, comparably to the centralized locking algorithm and better than the voting algorithm.

A file directory is a listing of information of the files available to the users of the distributed data base in a computer network. Such a directory will enable a user at any node to determine where in a network a specific sharable file exists. One can consider such a directory to be similar to a card catalogue in a public library. Users at each node may offer to list their files in this directory of public files for sharing purposes. A user may interrogate this list to determine its contents or obtain information on where a specific sharable file exists. The nonshared files is assumed to be stored at the computer that is known to the user and therefore is not considered here. We assume each computer has its own local directory which consists of all the sharable files stored in that computer. To search for a file that is not stored in a local computer, the user must consult the file directory.

A model for program behavior, the renewal model, is introduced; its properties are discussed, and its ability to model the behavior of real programs is investigated. Using this renewal model, several theorems are derived which describe the performance of the working set replacement algorithm. Then the renewal model is used to evaluate the performance of a replacement algorithm for two-level directly addressable memory hierarchies.

Error detection and retransmission are used as error control in many computer communication systems. In these systems, random length messages are partitioned into fixed size blocks for ease in data handling and memory management. A mathematical model is developed in this paper to determine the optimal message block size that minimizes the expected waiting time in retransmission and acknowledgment delay and thus maximizes channel efficiency. The model considers two classes of error detection and retransmission strategies: 1) stop-and-wait and 2) continuous transmissions. Using the relationships among acknowledgment time, channel transmission rate, channel error characteristics (random error or burst error), average message length, optimal block size are computed from the model and presented in graphs. The model and the graphs should be useful as a guide in the selection of the optimal fixed message block size for computer communication systems.

Demultiplexing serves as an important function for statistical multiplexors. Its purpose is to reassemble the received message and distribute it to the appropriate destination. An important cost consideration for this function is the size of the buffer necessary to meet a specified overflow service requirement. The demultiplexing buffer can be modeled as a finite waiting room queueing model with batch Poisson arrivals and multiple distinct constant servers. Stimulation is used to study buffer behavior for traffic arriving at the buffer according to the uniform, linear, step, and geometric destination functions. The relationships among buffer overflow probability, buffer size, traffic intensity, average message length, and message destination are presented in graphs to provide a guide in the design of demultiplexing buffers. Simulation results reveal that buffer input messages that have short average message lengths and uniform traffic destinations yield the best buffer behavior. Thus, in planning the CPU scheduling algorithm and in selecting the demultiplexing output rates, the designing of a computer communications system that uses the statistical multiplexing technique should also consider the output statistics needed to achieve optimal demultiplexing performance.

Recent advances in computer communications are discussed including computer-traffic and channel error characteristics, optimal fixed message block size, statistical multiplexing, and loop systems. A unified model is developed and then used to analyze the queueing behavior of the star and loop systems. Numerical results for selected traffic intensities and message lengths, given in graphical form, provide insight into the performance of these systems.

A queueing model with limited waiting room (buffer), mixed input traffic (Poisson and compound Poisson arrivals), and constant service rate is studied. Using average burst length, traffic intensity, and input-traffic mixture rate as parameters, we obtain relationships among buffer size, overflow probabilities, and expected message-queueing delay due to buffering. These relationships are portrayed on graphs that can be used as a guide in buffer design. Although this study arose in the design of statistical multiplexors, the queueing model developed is quite general and may be useful for other industrial applications.

A queuing model with a limited waiting room (buffer), Poisson arrivals, multiple synchronous servers (synchronous transmission channels), and constant services is studied. Using traffic intensity and number of transmission lines as parameters, the relationships among overflow probabilities, buffer size, and expected queuing delay due to buffering are obtained. These relationships are represented in graphs which are provided as a guide to the design of buffer systems. An example is given to illustrate the use of these results in buffer design problems. In addition, the procedure to design an optimal buffer system in the sense of minimal cost (tradeoff between buffer cost and transmission cost) is discussed.

A model is developed for allocating information files required in common by several computers. The model considers storage cost, transmission cost, file lengths, and request rates, as well as updating rates of files, the maximum allowable expected access times to files at each computer, and the storage capacity of each computer. The criterion of optimality is minimal overall operating costs (storage and transmission). The model is formulated into a nonlinear integer zero-one programming problem, which may be reduced to a linear zero-one programming problem. A simple example is given to illustrate the model.

A mathematical model is developed for diagnosing system failures when symptoms are observable. Optimal policies for searching malfunctions yielding minimum expected diagnostic cost are developed, based on the probabilities of various malfunctions conditioned on the set of observable symptoms, the detection probability of each malfunction, and its associated testing cost. The necessary and sufficient conditions satisfied by such policies are derived. The model can be implemented easily on a computer, reducing costs of diagnosis and training diagnosticians.

A model is presented for evaluating the electrical loss (assuming the head medium is not infinitely permeable) and loading effect of the readback process in magnetic recording. The technique is based on the fact that the readback process can be approximated as linear and that the read head is a linear frequency-variant device. After approximating the open-circuit readback signal by a Fourier series, the readback signal with loading and electrical loss is the summation of the responses produced by the harmonic components. Examples are given to evaluate the electrical loss and loading effect on the readback signal. Simulation results agree well with experimental results.

The author of the paper, "On the Realizability of Special Classes of Autonomous Sequential Networks," which appeared on pp. 791-797 of the December, 1965, issue of these Transactions, has called to the attention of the Editor corrections on pages 792 (including relation (2), and 796 (including Figure 5).

When frequency or phase modulation is applied to digital magnetic recording, both peak shift and amplitude variation occur in the readback signals. These distortions are due specifically to pulse crowding, noise, and variation of separation between read head and recording medium. When such waveform distortions are simulated on the digital computer, the results agree well with those obtained from a time-consuming experimental method, and are more accurate than an approximate analytical solution. Simulation results are also produced in graphical form, and thus provide an additional guide for designing and evaluating the performance of optimal recording systems.