THE IEEE (Institute of Electrical and Electronics Engineers) Computer Society has traced its origin to the formation of the AIEE (American Institute of Electrical Engineers) Large-Scale Computing Devices Committee (CDC) during May and June 1946, which was formally approved by the AIEE Board of Directors on January 29, 1948. The IRE (Institute of Radio Engineers) Professional Group on Electronic Computers (PGEC) was formed on September 14, 1951, which was formally approved by the IRE Board of Directors on October 19, 1951. The AIEE CDC and the IRE PGEC were the roots of the IEEE Computer Society. After the merger of the AIEE and the IRE to form the IEEE in 1963, the AIEE CDC and the IRE PGEC were combined to form the IEEE Computer Group on April 22, 1964, which became the IEEE Computer Society in January 1971. Accordingly the IEEE Computer Society is celebrating its 65th Anniversary in 2011. Likewise the IEEE Transactions on Computers (TC) has traced its origin to the inaugural publication of the IRE Transactions on Electronic Computers in December 1952, with Werner Buchholz as Editor and Jean Felker and James Weiner comprising the Editorial Board. The inaugural issue (PGEC-1) contained papers on computers from WESCON (the Western Electronic Show and Convention), held at Long Beach, California, on August 27-29, 1952. The IRE Transactions on Electronic Computers began as a quarterly publication and became a bimonthly publication in January 1962. After the merger of the AIEE and the IRE in 1963, it became the IEEE Transactions on Electronic Computers in August 1963 (Volume EC-12, Number 4). Since January 1968 (Volume C-17, Number 1), it has become the current IEEE Transactions on Computers (TC) and a monthly publication. The inception of the IRE Transactions on Electronic Computers in 1952 had undoubtedly contributed much to the IRE Computer Group’s visibility and stability. The early formative years saw a succession of outstanding editors, beginning with Werner Buchholz in 1952, Ralph Meagher in 1954, John (Jack) Nash in 1957, Howard Tompkins in 1959, and Arnold Cohen in 1961. The position of associate editor was introduced in April 1961, the fi rst one being John (Jack) Sherman who was appointed to cover the area of analog and hybrid computers; also the name of editor was changed to editor-in-chief. The IEEE Transactions on (Electronic) Computers continued to develop under the editorship of Norman Scott (1963) and Harry Huskey (1965). With expanded breadth of technical coverage, the number of annual pages increased from about 800 in 1962 to nearly 1,400 in 1970. A special 25th Anniversary issue of TC was guest edited by Harry Huskey and published in 1976. It contained state-of-the-art surveys and tutorial presentations, and high-quality papers on emerging computing technology were brought together to present a comprehensive view of developments and evolution of concepts, education, languages, and peripherals in the computer fi eld. The special issue published 18 papers authored by 26 leading experts in their areas of interest. A chronological list of editors/editors-in-chief of TC with years of their appointments is listed as follows. 1. Werner Buchholz, 1952 2. Ralph Meagher, 1954 3. John Nash, 1957 4. Howard Tompkins, 1959 5. Arnold Cohen, 1961 6. Norman Scott, 1963 7. Harry Huskey, 1965 8. Robert Short, 1971 9. Richard Merwin, 1975 10. Taylor Booth, 1978 11. Tse-yun Feng, 1982 12. Ming T. Liu, 1986 13. Earl Swartzlander, 1991 14. Jane W.S. Liu, 1995 15. Jean-Luc Gaudiot, 1999 16. Viktor Prasanna, 2003 17. Fabrizio Lambardi, 2007 18. Albert Zomaya, 2011 In 2011 TC is celebrating the 60th year of its publication. Happy Anniversary!

We propose a Web caching scheme, based on the caching neighborhood protocol, featuring dynamic caching hierarchies as its underlying infrastructure. Dynamic Web caching hierarchies consist of proxy servers building hierarchies on a per request basis, in contrast to static Web caching hierarchies that comprise proxy servers preconfigured into hierarchies. Concerns of overheads and efficiency in forwarding requests individually have driven conventional Web caching schemes to use static Web caching hierarchies. Nevertheless, we show that a Web caching scheme featuring dynamic caching hierarchies can be both efficient and effective in request forwarding.

This paper outlines a generic approach to modeling Web caching schemes. Four Web caching schemes-SH, ICP, CD, and CNP-were modeled to study their performance in terms of request latencies. There were two important findings. First, conventional Web caching schemes such as SH, ICP, and CD would have shorter request latencies if total numbers of levels in their caching hierarchies were one or two. Second, under some reasonable assumptions, CNP was found to outperform the other schemes in terms of request latencies.

In this paper we propose a Caching Neighborhood Protocol (CNP) that describes an infrastructure upon which proxy servers can build dynamic Web caching hierarchies. Such a scheme decreases the response times for the requests by increasing the availability of documents without compromising the currency of the rendered documents. Some qualitative reasonings and studies on the request accessing traces collected by a proxy server at NLANR are presented to justify CNP. A five-day trace analysis shows that the top 20% Web sites (in terms of frequency of accesses) provide 93% of the most frequently accessed top 20% documents and such top 20% documents account for 94% of the documents that have been accessed more than once. Hence, an important observation is that caching the most popular documents provided by the most popular Web sites would be a very effective approach for Web caching.

Code division multiple access (CDMA) has become an attractive technique for media access control in personal communication networks (PCN). Two MAC protocols, namely preamble signaling access (PSA) and minislot signaling access (MSA) are defined and evaluated for voice/data integration at the base station. It assumes that there are two types of mobile hosts, voice mobiles and data mobiles. The base station integrates the data and voice transmission access so that there are no contentions between voice and data users. An adaptive access control is proposed with parameters which affect the system performance. Markovian chain models have been developed to analyze the performance of PSA and MSA protocols. Performance results based upon simulations are also provided.

In this paper, two MAC schemes are defined and studied for DS-CDMA personal communication networks (PCN), namely preamble signaling access (PSA) and mini-slot signaling access (MSA). PSA uses preamble-packet slot structure while MSA is applying mini-slot techniques to solve the problems of code assignment and MAI control. Markovian chain models have been developed to analyze the performance of these two protocols for voice-only systems as well as data-only systems. The analytical model is shown to be very close to simulation results. Based on the results obtained from the analysis, it is shown that, for many cases, the MSA protocol performs better than the PSA protocol, especially for voice services.

Distributed queue dual bus (DQDB) networks are high speed metropolitan area networks specified by the IEEE 802.6 standard. They may serve as local subnetworks to gather high speed data for transmission over wide area B-ISDN networks or as backbones in mobile networks to connect wireless infrastructures. In these situations, DQDB networks will carry a predominant portion of isochronous traffic. Thus we are motivated to investigate how to efficiently support isochronous traffic via the pre-arbitrated (PA) access method in DQDB networks. We propose a new PA slot reuse scheme which can much improve DQDB networks' utilization via arranging isochronous connections to share octets in the PA slots. It is based on the idea of categorizing octets with octet types. A related problem of octet type selection is formulated and an algorithm is developed to solve the problem. Based on the algorithm's results, the proposed scheme is made efficient as well as traffic-oriented. Simulations are performed to show that the scheme is much better than the previous ones, in terms of utilization, drop rate and overhead. The new scheme is compatible with the current DQDB standard and can be implemented in the bandwidth manager and VCI server of a DQDB network.

In this paper, a new wireless medium access control protocol, called Mini-Packets Reservation Multiple Access (MPRMA), is proposed for the microcellular wireless environments to support voice and data traffic. Instead of using information packets to contend for reservation, the protocol uses smaller reservation packets for contention. Thus, regular slots can be further divided into smaller slots for sending reservation packets. Furthermore, in order to facilitate subsequent packet transmission, a continuation flag is used in each information packet for requesting further reservation. Comparing to the Packet Reservation Multiple Access (PRMA), it is shown by simulation that MPRMA can support more voice and data users, respectively, in a single traffic type environment. And more importantly, MPRMA is also a better alternative to PRMA for supporting voice-data integration. In order to counter adverse channel conditions, a strategy is also proposed. In addition, MPRMA requires no deadline scheduling at the base stations and minimizes overhead bandwidth on the downlink for sending acknowledgment messages.

Today's demanding applications, such as multimedia, require higher network transfer rates. Traditional local area networks (LANs) will not be able to provide the throughput required by these applications. The use of switches in LANs is an effective technique to increase the throughput of the network. These switches have finite buffers at their input and output ports. The size of these buffers affect the packet loss rate. It also affect the delay at the switch as packets may have to wait for the output buffer to become available. We study the effect of buffer sizes within these switches. We show how the buffer size is related to the performance of the switch as well as overall performance of the LAN.

Media synchronization and freedom from starvation at destination devices are the two most important problems in a multimedia communication system. In order to solve these problems at the same time, this paper presents a protocol combining the scheduling scheme and the buffering scheme with underflow threshold (SBUF). In this protocol, by controlling the buffer sizes and modifying transmission schedule of the synchronizer synchronization can be achieved without synchronizing clocks during a connection. In this paper the algorithm of the protocol is described. The setting of the system parameters and network QOS to support the proposed protocol are also given in this paper. A simulation is performed for comparison of four synchronization schemes: scheduling schemes (with and without clock synchronization), marker scheme, and the proposed SBUF protocol. The results confirm that the proposed protocol guarantees satisfaction of QOS requirements and also performs better than the other schemes in terms of media synchronization and freedom from starvation at destination devices.

We propose an architecture of FDDI-based mobile networks and address issues that arise in providing real-time communication services on such networks. A wide range of problems concerning synchronous bandwidth management and quality of service guarantee are identified. To solve these problems, we present a dynamic bandwidth management scheme, a source handoff protocol and two approaches to handling destination handoffs. These schemes make handoffs transparent to mobile users; no degradation in quality of service will be observed during handoffs. The proposed solutions are compatible with the FDDI standards.

We study different local area networks (LAN) configurations and their suitability to multimedia traffic. The transfer rates required by multimedia traffic are beyond the typical bandwidth of traditional LANs. The use of switching hubs in LAN configurations overcomes the bandwidth limitation and supports multiple concurrent communications. We present hub-network configurations that provide high performance and reliability in addition to increasing the effective network bandwidth. We study the performance of these configurations using simulation techniques.

The knockout switch is a nonblocking, high-performance switch suitable for broadband packet switching. It allows packet losses, but the probability of a packet loss can be kept extremely small in a cost-effective way. The performance of the knockout switch was analyzed under uniform traffic. In this paper, we present a new, more general analytic model of the knockout switch, which enables us to evaluate the knockout switch under nonuniform traffic. The new model also incorporates the effects of a concentrator and a shared buffer on the packet loss probability. Numerical results for nonuniform traffic patterns of interest are presented.>

The media streams of a multimedia communication application may traverse through different communication channels. Because of the network delay and jitter, data in these streams sent at the same time may not arrive at a destination simultaneously. In this paper a multimedia synchronization protocol that resynchronizes the media streams is proposed. The protocol inserts extra control cells into the media streams, and aligns the cells at the receiver site. Three synchronization policies, namely, the Drop-Old, the Transmit-Old and the Delayed-Transmit, are introduced to align the control cells. To satisfy the Quality of Service (QOS) specified by an application, the protocol must negotiate an appropriate QOS with the underlying ATM network. For each of the three synchronization policies, the relationship between the specified QOS and the negotiated QOS is derived.>

In this paper a method is proposed to produce test paths that check both data flow and control flow for a protocol specified in the extended finite state machine (EFSM) model. The method first identifies a set of paths from a given specification to cover a data flow selection criterion, then it appends state check sequences to some transitions in this set of paths for checking control flow. The criterion that our method employs for selecting these transitions is called effective domain for testing. Effective domain for testing is used to evaluate how effective a transition can be tested in a given path in terms of the range of values that the variables in this transition can have. Since each transition can appear in several paths, our method is to append state check sequences to its occurrences that have distinct effective domains. In addition, our method will compute the path domain for each path and make some inexecutable paths executable.>

We address the issues related to the delivery of multimedia streams on local area networks. Multimedia integrates voice and video along with text and images into existing systems. Traditionally, local area networks were designed to handle regular data traffic which are bursty in nature and for which variable delay is acceptable. Multimedia traffic, on the other hand, requires constant delay in addition to fast (or real time) delivery. Multimedia traffic also requires large bandwidth compared to regular traffic. Since local area networks are widely in use, their modification to integrate multimedia streams is very important. We propose priority-based communication schemes for the timely delivery of multimedia traffic on local area networks. We compare the performance of these schemes using simulation techniques.>

A key issue in distributed scheduling is selecting appropriate jobs to transfer. A job selection policy that considers the diversity of job behaviors is proposed. A mechanism used in artificial neural networks, called weight climbing, is employed. Using this mechanism, a distributed scheduler can learn the behavior of a job from its past executions and make a correct prediction about whether transferring the job is worthwhile. A scheduler using the proposed job selection policy has been implemented and experimental results show that it is able to learn job behaviors fast, make decisions accurately and adjust itself promptly when system configuration or program behaviors are changed. In addition, the selection policy introduces only negligible time and space overhead.>

An automatic test case generation method for Estelle is proposed. A formal model is introduced to describe the dynamic properties of Estelle specifications so as to verify the difference between the behavior of the specification and the behavior of its models. Based on the difference, an algorithm is presented to produce test cases that can detect such implementation faults. The algorithm can generate test cases not only for single module specifications but also for systems containing multiple modules that run concurrently. In addition, heuristics are suggested to improve the performance of the test case generation process.>

A test case generation method is proposed for the conformance testing of communication protocols. Given a protocol specification and a fault model, both specified by extended finite state machines (EFSMs), the proposed method generates test cases that detect the given faults. A theoretical model is proposed to describe the dynamic properties of EFSMs. Test cases can be generated by analyzing the differences in the dynamic properties between the specification and the fault models.>

Abstract The star graph has a smaller degree and diameter than the well‐known n‐cube, and can be an alternative to the n‐cube for systems with a large number of nodes [2]. In our previous work [11], three different indirect star‐type networks were obtained from the star graph: the indirect star network I, the indirect star network II, and the star‐delta network. However, the indirect star networks I & II are constructed from large switches, and do not perform as well as the indirect cube‐type networks of comparable switch sizes. Also, they are not modular. The star‐delta network is modular, but it employs varying switch sizes for different switching stages, and has a lower performance than the indirect cube‐type networks based on comparable switch sizes. Moreover, the switch sizes for all three indirect star networks grow with the network size. In this work, a new indirect star network, called the μ‐star network, is proposed. Being modular and constructed from (2 × 2) crossbar switches, the new network is an improvement over previously proposed indirect star‐type networks. The μ‐star network is analyzed for its performance and the analytic results are verified through simulations. © 1993 by John Wiley & Sons, Inc.

A test suite generation method is proposed for conformance testing of communication protocols to solve the problem of generating test sequences for protocol specification models that have memories. A program verification technique called axiomatic semantics, is used to test protocols specified by extended finite state machines (EFSMs). While an EFSM is verified by the technique, observable events are recorded. By carefully manipulating the execution path in EFSM, the observed events can be used to examine the correctness of the protocol implementations.>

A four-step algorithm for constructing a protocol converter using the top-down approach is proposed. The algorithm involves construction of a system graph from the required service specification and the service specifications of the target protocols; construction of a service converter and new protocols services from the constructed system graph modification of the given protocols entities, to support the new service specifications, and derivation of a final converter by integrating the service converter and the constructed protocol entities. The protocol converter is guaranteed not only to satisfy the conformity property, but also to be free from deadlock and livelock.>

Processing rules in a distributed active database involves three design issues: how to decompose rules, how to distribute rules to sites, and how to evaluate distributed rules correctly. The authors study these three issues for complicated rules, which are complex and time-consuming to evaluate. They propose a relational operator, AND, and the associated algebraic manipulations of this operator to find independent parts of a rule query, which can be distributed among sites. Due to geographical dispersion in a distributed system, correct evaluation of distributed rules is not trivial. A distributed evaluation algorithm is preferred, which guarantees the correctness of the evaluation result of the distributed rule by collecting consistent local results from sites to form a global view.>

The authors propose a novel method for test sequence generation based on UIOS which only needs a minimal verification part. They also prove that the UIOv method (or revised unique input/output method) has the same applicability as the characteristic set method. The UIOv method can find a test sequence for any minimal finite-state machine. The proposed method has the same applicability as the UIOv method. In addition, the method uses a simple test on a given protocol specification to decide whether a verification part is needed for detecting transfer faults, the method can generate a minimal number of input/output sequences for a verification part. A more efficient algorithm for generating UIOSs and signature sets is presented. It is proven that the upper bound on the length of a UIOS is (n-1)*n rather than n/sup n/, where n is the number of states in a finite-state machine.>

Existing packet combining schemes, implemented either by hardware or software, developed for hot-spot congestion-control in multiprocessors are not applicable for use in telecommunication systems. The authors propose a hot-spot prevention scheme which exploits the structural characteristics of buffered delta networks to regulate the traffic. This scheme prevents the tree saturation by controlling the flow of the packets into the network and ensures that the hot-spot traffic can be supported with little degradation to the throughput of the uniform traffic, even when more than one hot-spot exists. The scheme retains all the desirable properties, including packet order preserving, of buffered delta networks, and is shown by simulations to be highly effective under either light or heavy hot-spot traffic. Since no a priori knowledge of the traffic patterns is required, the proposed scheme can be applied equally well to buffered delta networks in multiprocessors and telecommunication systems.>

The authors consider the conformity property, i.e. that the protocol converters providing communication between different networks meets the service specified by the designer, in constructing protocol converters. Using the top-down approach, an algorithm consisting of the following five steps is proposed to construct a protocol converter: (1) construction of a system graph from the given input; (2) removal of states and transitions that violate the synchronization requirements from the system graph constructed previously; (3) enforcement of liveness requirement on the system graph; (4) verification of the system graph against the service specification; and (5) derivation of a protocol converter from the system graph. The protocol converter so constructed is guaranteed not only to satisfy the conformity property, but also to be free from both deadlock and livelock.>

A hybrid approach to mutual exclusion is proposed to minimize both message traffic and time delay at the same time. A hybrid mutual exclusion algorithm using the release local sites first mode, the requesting group semantics, and the requesting sequence 1324 (i.e., local competition followed by global competition) is found to be an efficient way to control the interaction. This hybrid algorithm uses M. Singhal's (1989) algorithm as the local algorithm and M. Maekawa's (1985) algorithm as the global algorithm. Compared to Maekawa's algorithm, which needs 3 square root N. . .5 square root N messages but two time units delay between successive executions of the critical section (where N is the number of sites in the system), the proposed hybrid algorithm can reduce message traffic by 55% and time delay by 32% at the same time. Furthermore, when a distributed system exhibits locality of requests, the proposed hybrid algorithm can achieve even better performance.>

A modular approach is proposed for constructing a converter for two protocols that go through different phases, performing separate functions in each phase. The construction of such a converter consists of three steps: (1) the decomposition of protocols into distinct functions; (2) the construction of functional converters for each pair of functions selected by the converter designer; and (3) the merging of local functions with functional converters to construct the final converter. The final converter not only contains a common subset of functions of the two protocols, but also includes functionalities specified to each protocol.>

A fault-tolerant mutual exclusion algorithm for distributed systems is presented. The algorithm uses a distributed queue strategy and maintains alternative paths at each site to provide a high degree of fault tolerance. However, owing to these alternative paths, the algorithm must use reverse messages to avoid the occurrence of directed cycles, which may form when the direction of edges is reversed after the token passes through. If there is no alternative path, the total number of the messages exchanged is O (2*log N) in light traffic and two messages in heavy traffic; however, in this case the system cannot tolerate even a single communication link or site failure. If there are alternative paths between sites, the system can achieve a higher degree of fault tolerance at the expense of increased message traffic (owing to reverse messages). Thus, there is a tradeoff between efficiency and reliability, and a system can be designed to balance these two criteria properly. A recovery procedure for restoring a recovering site consistently into the system is also presented.>

A computer-aided protocol design system based on the OPS5 production system approach is proposed. Communication rules (state transitions) are specified as triples of object-attribute-value and the modeling of state transitions is specified by production rules. An incremental validation algorithm to facilitate protocol design is also presented. Based on a globally shared dataspace (working memory) in which different types and levels of information are all represented in a uniform structure, the OPS5 production system integrates both rule-based and procedure-based computations. Using this characteristic, the machine-dependent part can be abstractly specified through external procedure calls, the details of which can be coded in a procedure language until the implementation phase. Since computations in OPS5 are based on pattern matching, all of the attributes of elements that are in production rules or in external procedure calls can act as data templates for generic data types. This capability enhances the generic specification that allows different realizations for various implementation environments.>

An analytic model and analytic results for the performance of multibuffered packet-switching interconnection networks in multiprocessor systems are presented. The performance of single-buffered delta networks is first modeled using the state transition diagram of a buffer. The model is then extended to account for multiple buffers. The analytic results for multibuffered delta networks are compared to simulation results. The performance of multibuffered data manipulator networks is analyzed to demonstrate the generality of the model.>

A deductive approach which incorporates first-order logic into a relational database is proposed to remedy the problems incurred in the relational algebraic approach. The method not only allows recursive definitions for more complex logical reasoning but also provides a uniform query interface to the users for verifying functional properties of a protocol. Most important, with the deductibility of the deductive database it becomes possible to define algorithms for the incremental verification method, which speeds up the verification process by reverifying protocols without generating the global states from scratch.>

A formal model is presented to analyze two aspects of conversion problems: translation and synchronization. The purpose of the translation is to map messages in one protocol to those in another protocol, whereas the synchronization is to hold matched messages for carrying out the translation. An algorithm is given to construct a valid converter. The algorithm is low in space complexity, and yields a converter with several merits: concurrent processing, easy debugging, minimum work on development, and easy implementation for half-gateways.>

The authors propose a protocol synthesis method in which both service and protocol specifications are based on a state-transition model. In particular, they present an algorithm for deriving the protocol specification from a given service specification which is described by a set of directly coupled finite state machines (FSMs). These FSMs together regulate the execution sequence of service primitives intended by the service specification. To complement the protocol derivation algorithm for dealing with error-prone communication medium, the authors also devise a transformation procedure to construct an error-recoverable protocol from its error-free version derived from the proposed algorithm.>

The key idea of the algorithm is to let one transaction controller be in charge of all transactions in a set of interacting transactions. Two transactions are interacting if they are both interested in (accessing) the same resource. In addition, the controller is in charge of all the resources allocated to any of the transactions in the set. Having one controller in charge of all the transactions in a set of interacting transactions and all the resources allocated to them makes it easier to detect deadlocks and avoid them. The main problem dealt with is how a controller takes charge of another transaction when the transaction tries to access one of the resources currently in the control of the controller and how a controller releases a transaction back to its original controller when the transaction is no longer interested in any of the resources in which one or more of the other transactions are also interested. Communicating sequential processes (CSP) is used to code the algorithm. The correctness of the algorithm is proved in a semiformal manner.>

Optimistic concurrency control mechanisms have the tendency of freezing the system in order to validate a transaction at the end of the transaction's execution phase. This paper presents an optimistic concurrency control that does not freeze the database system. According to the property of conflicting transactions, concurrency control is divided into two counterparts. While one part is exercised at the data object, which responds instantly to consistency violation, the other part is exercised by messages flowing between transactions as background tasks. The whole system need not stop during the time concurrency control is exercising, nor during the time the system is restoring its state when consistency is violated. This makes the mechanism more attractive, since a higher degree of parallelism is provided between consistency control and transaction execution. An object-based model is used to present the mechanism in a distributed database system, in which communication relies heavily on message passing.

Degradation in system performance due to component failures is an important factor that prevents a distributed database management system (DDBMS) from achieving its full potential of better availability, response time, and system throughput. Resiliency mechanisms that help to continue system operation in spite of failures introduce overhead due to the need to maintain redundant information. Earlier performance studies of DDBMS have either altogether ignored failure or studied only limited aspects of the effect of failures and performance of resiliency mechanisms. In this paper an analytical model is used to comprehensively characterize the effect of failures and resiliency mechanisms on the performance of DDBMS. Two new performance measures are introduced. The methodology is illustrated by comparatively evaluating the performance of three algorithms.

In this paper, a centralized deadlock detection algorithm with multiple outstanding requests (CDDMOR) is proposed for use in distributed database systems and transaction-processing systems. This algorithm allows a process to request many resources simultaneously. While a centralized scheme is superior to a completely distributed scheme in terms of performance, a major problem of such a scheme is congestion. Therefore, an important extension to the basic CDDMOR, a partially distributed scheme, is proposed to alleviate the problem of congestion, as well as to take advantage of the result presented by several researchers that global (multisite) deadlocks are infrequent. It takes care of the local (single site) deadlocks without involving other sites and uses centralized deadlock detection only when there is a possibility of global deadlock.

Performance analysis studies of distributed database systems in the past have assumed that the message transmission time between any two nodes of a network is constant. They disregard the effect of communication network parameters such as network traffic, network topology, and capacity of transmission channels. In this paper, an analytical model is used to estimate the delays in transmission channels of the long haul network supporting the distributed database system. The analysis shows that the constant transmission time assumption cannot be justified in many cases, and that the response time is sensitive to the parameters mentioned above. Extensions and performance analysis in the context of interconnection networks are also discussed.

Performance of a Concurrency Control Algorithm (CCA) managing a distributed database system will deteriorate considerably when the configuration of the network supporting it will change due to either communication link failures or the communication delays introduced by varying load patterns. To get a good performance in spite of the changing configurations, we propose a scheme that involves breaking down the network into ‘weakly connected’ clusters. The problem to identify the clusters of a network is NP-hard. However, we present a heuristic strategy to identify the clusters of a network that works in polynomial time. Any of the present CCAs can be modified to work on a network that is partitioned into clusters by our scheme that uses (what we term as) multiple controllers. As an example, we present a Centralized Locking Algorithm with Acknowledgment using Multiple Controllers (CLAA/MC). Performance gain achieved using multiple controllers is also discussed.

In this paper we present a new methodology for designing reliable communication protocols. This methodology enhances communicating processes with a synchronization mechanism so that they can detect and resolve the errors caused by collisions automatically. The major advantages of this new methodology include: (1) the “state explosion” problem involved in protocol validation is alleviated; and (2) the burden of handling errors due to collisions is removed from the protocol designer. There is a need to verify that this methodology is applicable to arbitrary protocols. In this paper we also discuss the application of a program verification technique to this methodology.

This paper presents the framework and model of a network operating system (NOS) called MIKE for use in distributed systems in general and for use in the Distributed Double-Loop Computer Network (DDLCN) in particular. MIKE, which stands for Multicomputer Integrator KErnel, provides system-transparent operation for users and maintains cooperative autonomy among local hosts.

This paper presents a cluster structure, characterized by a set of structure parameters and a set of interconnection functions, as a conceptual interconnection scheme for large multimicrocomputer systems. It is shown that three popular interconnection structures (hypercube, hierarchy, and tree structures) are examples of the cluster structure. Two communication problems (traffic congestion and message delay), which may result in interconnection limitation to a particular structure, are analyzed. The analysis provides a way to understand structural properties such as complexity, capacity, and limitation. Through the use of the cluster structure and the analytical model, topological optimization is presented to show how interconnection limitation can be minimized.

This paper presents a formal model using the context-free grammar (CFG) for the design and implementation of communication protocols. It is similar to the Backus-Naur Form that has been used to define the syntax of programming languages. The transmission grammar (TG) is used to define the protocol for the communication entities of a computer network. For the hierarchical protocol design, the communication entity of each level is decomposed into more detailed inner-layered components and/or logically independent parts. The local approach is first used to define the TG for each of the decomposed components and logical parts. The shuffle and substitution operations are then applied to integrate the TGs of the logical parts and the TGs of the components, respectively. Examples are given to illustrate the grammatical properties of protocols and the design methodologies of TGs.

The Distributed Loop Computer Network (DLCN) is envisioned as a powerful, unified distributed computing system which interconnects midi/mini/micro-computers, terminals and other peripherals through careful integration of hardware, software and a loop communication network. Research concerning DLCN has concentrated on the loop communication network, message protocol and distributed network operating system. For the loop communication network, previous papers [2,3] reported a novel message transmission mechanism, its hardware implementation, and its superior performance verified by GPSS simulation. This paper presents an overview of the design requirements and implementation techniques for DLCN's message protocol and network operating system. Firstly, a bit-oriented distributed message communication protocol (DLMCP) which handles four message types under one common format is proposed. Besides user information transfer, this protocol supports automatic hardware-generated message acknowledgment, error detection and recovery, and network control and distributed operating system functions, Secondly, the network operating system (DLOS) is described which provides facilities for interprocess communication by process name, global process control and calling of remote programs, generalized data transfer, alterable multi-linked process control structures, distributed resource management, and logical I/O transmission in a distributed file system.

An architectural concept called Grammar-Programming is introduced which allows computers to be constructed that can directly execute a variety of high-level languages. Representing an intermediate level between the basic hardware/firmware functions of ordinary computers and the software operations of language translators, it is shown how grammar-programs can be constructed which specify the syntax and semantics of various programming languages. The Grammar-Programmable Machine (GPM) then uses these specifications to process directly the users' high-level language programs. In the Ph.D. dissertation* upon which this abstract is based, a model is first developed for representing the syntactic and semantic characteristics of context-free language generators, and an automaton called a Syntax Network (SN) is constructed. Next a simple, statement-directed language is introduced to express the states of the syntax network and to define the actual grammar-programming language. A simulator is then implemented which is used to test the grammar-programs written for ALGOL and SNOBOL. Finally, the architectural organization for the Grammar-Programmable Machine is described at the register-transfer level. By taking advantage of its intermediate position between software compilation and hardware interpretation of high-level languages, the Grammar-Programmable Machine is able to emphasize the best features of both techniques and to achieve a potential that neither can reach individually.

The primary goals of this paper are two-fold: 1) to present the design and hardware implementation of the interface transmitter for the Distributed Loop Computer Network (DLCN), using a novel shift-register insertion message transmission mechanism, and 2) to discuss simulation results comparing DLCN with Pierce and Newhall loops, which verify earlier claims as to DLCN's superior performance.

A loop (ring) system is proposed for distributed computer networks which: i) allows simultaneous transmission of variable-length message frames, 2) minimizes loop access and transmission times, and 3) provides a form of automatic traffic regulation. The ring interface transmitter which performs these three functions is described, and a conceptual model of its operation is developed. The model illustrates a technique by which the ring interface transmitter can delay incoming messages by hardware buffering just long enough for a variable-length output message to be placed on the loop. It is shown how advantage can be taken of gaps between incoming messages to clear out the delay buffer and to make room for future outgoing messages. It is further demonstrated that an interesting form of automatic message traffic regulation results from use of the proposed technique. Possible hardware implementations of the model are also considered, using a variable-length shift register for the incoming message delay buffer. The probable effects of the proposed technique on message transmission are discussed, and ongoing analytic and simulation studies are described.

A necessary condition for a threshold function in terms of comparability was first reported by Paull and McCluskey [4] who have established a chain of conditions later called 1-monotonicity, 2-monotonicity, and k-monotonicity, in general. Each of these conditions entails its predecessors, and is stricter than them; the union of this denumerable set of conditions is called complete monotonicity by Winder. Winder [5] has given an extensive treatment of these ideas and has offered an efficient procedure for the design of threshold devices.