/ V. B. Marakhovsky / Professor
/ Zi Xue Cheng / Assistant Professor
/ Kshirasagar Naik / Assistant Professor
The Computer Networks Laboratory is working in four directions within Research Projects and Top-Down Education Course-ware Development Projects:
1. Self-timing and Event-driven Systems
1.1 Structural methods of self-timed device synthesis: A procedure of designing a self-timed device defined by the model of finite automaton is suggested.
1.2 Global Synchronization in massively parallel computing systems: The problem of global synchronization is solved for asynchronous processor arrays with an arbitrary interconnection graph. The solution is based on decomposing the system to the processor stratum and synchro-stratum. For the case of a synchronous system with two-phase master-slave synchronization, several simple implementations of the synchro-stratum for the corresponding asynchronous system are proposed.
1.3 Self-timed interfaces: The transition from synchronized working of the system to its globally asynchronous behavior requires that all local processes in the system should interact between each other on the base of asynchronous interfaces. The possibility of organizing single-wire bit handshake is demonstrated and self-timed circuits of transmission/reception are developed with throughput not worse than of double-wire circuits. Using single-wire bit handshake allows one to transmit n-bit binary code by n+2 communication lines.
1.4 Self-timing with current sensors: The idea of applying current indication of transient process completion to construct asynchronous blocks of CMOS VLSI systems is considered. We analyzed design principles and characteristics of the known current sensors, formulated stubborn problems of their using, suggested improved circuits and two ways of the interaction between blocks with current sensors.
2. Multi-media Communication and Synchronization
Fault-tolerance in Multi-media Synchronization: We proposed a presentation architecture suitable for network-based multi-media applications. The main idea in the architecture is to reduce and tolerate presentation faults. We showed how detailed design of such an architecture can be obtained from its requirement specification.
3. Protocol Engineering and Conformance Testing
3.1 Protocol Synthesis: To automate the development of protocols, we investigated a methodology to synthesize a protocol without logic errors such as deadlock based on formal description technique LOTOS.
3.2 Protocol implementation: Multi-Rendezvous is powerful concept in the abstract specification of communication protocols. However, implementing Multi-Rendezvous is a difficult task. We developed three distributed algorithms for implementing Multi-Rendezvous, which can be used as foundation of protocol implementations.
3.3 Distributed Group Resource Allocation Method: Recent new applications, such as supporting collaborative group work, distributed cooperative development of software, causes a new resource allocation problem that some resources are competed for by several groups of processes. We present a model to describe the new problem and a distributed algorithm as a solution to the problem.
3.4 Fault-tolerant State Verification Sequence: The idea of Unique Input/Output (UIO) sequences in a finite-state machine is an attractive way to verify a state of a machine. However, faults in an implementation make such verification a difficult task. We developed the idea of fault-tolerant UIO sequences that enables us to verify states in spite of some faults in an implementation.
4. Modeling of Autonomous Decentralized Cooperative Systems
Modelling for Autonomous Decentralized Systems: A model for negotiation among the various types of agents in autonomous decentralized systems was proposed based on the Transaction Analysis Theory. The model deals with the effect of attitude of agents in negotiation.
Refereed Journal Papers
This paper contributes toward
exception handling and fault-tolerance in multi-media presentation. Our study
is based on the well-known four phases in fault-tolerant computing: fault
detection, damage assessment, error recovery, and continued service. We
define a {\it fault} in multi-media synchronization and a simple fault
detection mechanism. Using the concept of a
A procedure of designing a self-timed device defined by the model of finite automaton is suggested. In accordance with the chosen automaton standard implementation structure from the automaton transition/output graph one derives the Signal Graph Specification that then is processed by the formal synthesis procedure for self-timed implementation. The design procedure is illustrated by two examples: Stack Memory and Counter with Constant Acknowledge Delay.
Local processes in MPCS can be coordinated by asynchronous system of global synchronization via handshake using current sensors for detection of the transient processes completion. The known current sensors are considered, the best one is analyzed and its shortcomings are revealed. Current sensor with wide range of the measured current is suggested. The principles of control in circuits with current sensors are developed. Self-timed data exchange between local processes of the system is discussed. Transmission/reception circuits with single-wire bit handshake are demonstrated. Their transmission rate is no worse than that of double-wire circuits. They allow one to transmit combinations of $n$-bit code by $n+2$ communication lines.
This paper presents a new automatic synthesis algorithm to construct two communicating protocol entities. The specifications of entities are in LOTOS. We also give definitions of logic errors which are different from the logic errors in the protocol synthesis based on FSMs. The synthesized protocol is proved to be logic error free. The protocol synthesis algorithm is applicable to every structure of protocol layer which provides services to its upper layer. To show the effectiveness of the proposed synthesis algorithm, we have applied it to a simplified version of the protocol handler of the Transport Layer.
The objective of this paper is to obtain a gate-level description of a multimedia synchronizer specified in a time interval notation. A synchronization requirement specification (SRS) is modeled as a Timed Petri Net from which a Timed Signal Transition Graph (TSTG) is obtained. An asynchronous circuit, who output satisfies the synchronization requirement, is derived from the TSTG.
We argue that the programming simplicity and message passing complexity of implementing LOTOS multi-rendezvous largely depends on the underlying communication structure. The programming simplicity and low complexity of our algorithm are due to our viewing the multi-rendezvous problem as a distributed mutual exclusion problem. Using the parallel programming environment of Linda, we present an efficient algorithm to easily implement multi-rendezvous in LOTOS. The orthogonal communication structure in Linda allows us to separate synchronization concerns in multi-rendezvous from concerns in interprocess communication in an implementation. The concept of Tuple Space in Linda and the associated $in$, $out$, and $rd$ primitives for managing the tuple space lead to an elegant programming style for distributed implementation of multi-rendezvous.
The central idea in the paper is to
define the concept of
The problems of designing self-timed circuitry based fault-tolerant ring communication channel for multi-computer control systems are discussed. The technical solutions suggested are the basis of the logic project of a communication channel adapter designed for a fault-tolerant airborne multi-computer system with the local area network architecture. The basic element of such an adapter is a mono-channel controller consisting of the protocol automaton and the automaton of control and recovery. The approaches to self-timed realization of these automata and the principles of mono-channel self-recovery organization are stated.
The problem of global synchronization is solved for asynchronous processor arrays and multiprocessor systems with an arbitrary interconnection graph. Global synchronization of asynchronous systems is treated as a homomorphic mapping of an asynchronous system behavior in logical time onto the behavior of the corresponding synchronous system with a common clock functioning in physical time. The solution is based on decomposing the system to the processor stratum and synchro-stratum; the latter plays the role of a global asynchronous clock. For the case of a synchronous system with two-phase master-slave synchronization, a simple implementation of the synchro-stratum for the corresponding asynchronous system is proposed. It is shown that, depending on the local behavior of the processors, the synchro-stratum is able to perform two types of global synchronization: parallel synchronization and synchronization that uses a system of synchro-waves.
The problems are discussed that arise when designing massively parallel computer systems. The transition from globally synchronized working of such systems to globally asynchronous behavior resolves most of them. The problems of asynchronous interaction of local processes with the system of their global coordination on the base of handshake are considered as well as the problems of self-timed data transmission between processes. If the system modules that realize local processes are not asynchronous and implemented in CMOS-technology, then, to detect the moments of the transient processes completion in them, the idea of current indication is used. A circuit of a current sensor is suggested with wide range of permissible changes of the measured current and with admissible characteristics. Two ways of organizing the interaction between circuits with current sensors are developed. The principles of self-timed data exchange between local processes of the system and data transmission by means of a dual-rail code and binary code with handshake for every bit are considered. The possibility of organizing single-wire bit handshake is demonstrated and its self-timed implementation is developed with the transmission rate no worse than that of double-wire bit handshake.
We describe the design of a speed-independent communication channel based on a pipeline token-ring architecture. We believe that this approach can help reduce some negative "analogue" effects inherent in asynchronous buses (including on-chip ones) by means of using only "point-to-point" interconnections. We briefly outline the major ideas of the channal's organization, protocol and our syntax-driven implementation of the channel protocol controller. The protocol has been recently verified for deadlock-freedom and fairness.
To solve the problem of global synchronization in massively parallel VLSI systems, it is necessary to organize asynchronous interaction between system blocks. The possibility of applying current sensors for detection of the end of signal transitions to construct asynchronous blocks in CMOS-technology is discussed. For known current sensors, their design principles and characteristics are analyzed. Two ways of organizing the interaction between circuits with current sensors are suggested. Stubborn problems of using the known current sensors that appear due to the imperfection of their characteristics are formulated. A current sensor is suggested that removes the major of these problems but is capable of working only with a particular circuit class. However, simulation results indicated that using even such sensors is not efficient enough.
LOTOS is a high level specification language which incorporates the Multi-Rendezvous. Multi-Rendezvous is a powerful communication mechanism that allows a set of processes to execute an event in synchronous way. Besides the multi-synchronous property, Multi-Rendezvous has nondeterministic and exclusion properties. It is not a trivial problem to implement Multi-Rendezvous in a network system. The implementation has to maintain the properties mentioned above, be fair and make progress. In this paper, we propose a new efficient distributed algorithm, based on the concept of coterie, for implementing Multi-Rendezvous with $O(N\sqrt{N})$ message passes. Our algorithm is fully distributed and does not use manager processes and auxiliary resources.
Protocol entities,in communication protocols, behave under sets of communication rules (protocols). Thus it is desirable to concentrate on the design of one protocol entity and generate the corresponding protocol entity automatically by exploiting the communication rules. A protocol is desired to be formal, precise and unambiguous, in other words, it is described using FDTs (Formal Description Techniques). In this paper, we propose a protocol synthesis algorithm in which a peer protocol entity is generated from a single given entity. Unlike previous works, where FSMs (Finite State Machines) were used to synthesize partial protocols, we use LOTOS, which is one of FDTs developed by ISO, in our proposed synthesis algorithm. We prove that the resultant protocol consisting of the given entity and the generated peer entity is logical errors free, collectively represented as deadlock free, if the given entity is in certain forms which are natural in the context of communication protocols. We also present that the protocol is bisimulated by both the given entity and the peer entity to show that the protocol maintains the behaviors of the entities.
Distributed resource allocation is an important problem in developing distributed systems. Many works have been done on the problem. However recent new applications, such as supporting collaborative group work, distributed cooperative development of software, cause some new problems. One of them is that some resources are competed for by several groups of processes. There may exist deadlock or starvation among groups. We call them " group deadlock'' and " group starvation''. In this paper, we first define the new resource allocation problem: Distributed Resources Allocation among Process Groups. This problem is an extension of the Distributed Resource Allocation problem. Then we present a new distributed algorithm as a solution to the problem. Our algorithm can allocate resources to groups of processes without group deadlock and group starvation.
Abstract Data Type (ADT) is a powerful method which can be used to specify data part of protocol in a implementation independent way. It also allows to conduct verification and validation. However, practically ADT is rarely used because it is difficult for a non ADT expert to specify. Due to this reason, in order to promote the spread use of ADT, support method for ADT specification is necessary, Unfortunately, there are almost no such a support method so far. We propose an ADT specification support method based on Case Base Reasoning. The support system can prevent user from spending too much time and effort in specifying the whole ADT from the beginning.
In this paper, we propose a new efficient distributed algorithm for implementing Multi-Rendezvous with $2Nm$ message passes for a Multi-Rendezvous, without using auxiliary resources. Here, $N$ is the number of processes which participate in a Multi-Rendezvous, $m$ is the number of possible Multi-Rendezvous within a system. A formal specification of the algorithm in LOTOS is included in the paper.
In this research work, interactions among the various types of agents in autonomous decentralized systems are based on the theory of Transaction Analysis (TA) of psychology. Human beings are considered one particular type of autonomous agents. Hence, the agent's structure as well as interactions among them are defined and performed much the same as human behavior and attitudes. Cooperation among agents is negotiated by exchanging {\it strokes}. After the cooperation among agents is established, each of them has a specific role to perform in order to reach a particular goal. This paper presents the definition of the inner structure of an agent along with the negotiation process occurred among them until the cooperation is established.
In this paper, we consider an extended committee coordination problem in an autonomous decentralized social environment. The basic committee coordination problem and a distributed algorithm, as a solution to this problem in distributed environment, are presented by K.M.Chandy and J.Misra in. The algorithm guarantees the synchronous and exclusion properties of the problem and is fair (i.e. starvation-free) and makes progress (i.e. deadlock-free). In an autonomous decentralized social environment, besides the above mentioned properties, some social properties, such as individual preference, privacy protection, and stable assignment are required to be considered and guaranteed. In this paper, we extend the committee coordination problem by introducing some social properties, such as individual preference and stable assignment and give a decentralized social algorithm as a solution to this extended problem. The algorithm guarantees not only the synchronous and exclusion properties but also individual preference and stable assignment properties.