Computer Networks Laboratory

/ V. B. Marakhovsky / Professor
/ Zi Xue Cheng / Assistant Professor
/ Kshirasagar Naik / Assistant Professor

Computer Networks Laboratory is working in four directions within Research Projects and Top-Down Education Course-ware Development Projects:

• Logical-timing and Decentralized Control in Computing Systems;
• Network-based Computing and Distributed Computing;
• Protocol Engineering and Conformance Testing;
• Groupware

• 1.1 Global Synchronization of Asynchronous Arrays in Logical Time: Our approach is decomposing the asynchronous array to synchro-stratum which acts as a distributed asynchronous clock and automata stratum whose automata have a construction similar to that of the synchronous prototype array. For various disciplines of prototype synchronization, the corresponding variants of synchro-stratum implementation are developed.
• 1.2 Data-Controlled Delays in the Asynchronous Design: Asynchronous design technique has an approach of using padding delays to produce signals of transient process completion. To increase the efficiency of this approach, we suggested to use data-controlled incorporated delays. The approach is illustrated by an example of asynchronous adder design.
• 1.3 Asynchronous Control Device Design by Net Model Behavior Simulation: The problem of designing asynchronous control devices for discrete event coordination specified by a Petri nets have been considered. The design is based on the compilation of standard circuit modules corresponding to PN fragments into a net modeling PN behavior. Modifications of the known modules, a number of new module types, and the procedures of minimization are developed that considerably improve the quality of the solutions.
• 1.4 Self-checking and Self-recovery in Self-timed Embedded Systems: Selftimed designs offer inherent self-checking properties due to their ability to acknowledge the completion of transient processes in subcomponents. A number of techniques for self-checking and self-recovery in self-timed systems is suggested.

• 2.1 Design of a Multicast Protocol for Mobile Computing Prof. K. Naik: We study the problems in designing multicast protocol in a mobile environment. Considering both the problems in mobile computing and efficiency, we design a multicast protocol for single-source ordering.
• 2.1 Design of a distributed algorithm for solving competition among process groups Prof. Z. X. Cheng: Resource allocation is a fundamental problem in distributed systems. Many deadlock-free and starvation-free distributed algorithms have been developed for the resource allocation. However, with the progress of computer networks, a various of group activities over computer network by using groupware become possible and required. When many groups are using the same network resources, competition for resources may happen among group. Even though the deadlock and starvation never happen, the GROUP DEADLOCK and GROUP STARVATION may happen. The new type of problems are very difficult solved by existing algorithms. In this paper, we propose a new algorithm for resolving the competition among groups.

• 3.1 Protocol Specification Support: In order to automate the development of protocols, we investigated methods to support the development of protocol specification based on formal description technique LOTOS.
• 3.2 Protocol implementation: First Order Multiparty Interactions is powerful concept in the abstract specification of communication protocols. However, implementing First Order Multiparty Interactions is a difficult task. We developed a distributed algorithm for implementing First Order Multiparty Interactions, which can be used as foundation of protocol implementations.
• 3.3 Protocols for distributed problems: We have developed some protocols for distributed ranking, sorting, and consensus problems in distributed systems.
• 3.4 Efficient and Reliable Testing of Communication Protocols: Prof.K. Naik: We have developed methodologies to efficiently generate test sequences, and proposed new features of test architectures to incorporate the idea of reliability into a test method.

• 4.1 Groupware for assigning problem.
• 4.2 Groupware for scheduling meetings.

Refereed Journal Papers

1. Wei, D. and Muga, F. and Naik, K., Isomorphism of Constant Degree Four Cayley Graphs and Wrapped Butterfly Networks and Their Optimal Routing Algorithm. IEEE Trans. on Parallel and Distributed Systems , (to appear).

2. Naik, K. and Cheng, Z. and Wei, D., Distributed Implementation of the Disabling Operator in LOTOS. Information and Software Technology (to appear).

1. Varshavsky, V.; Marakhovsky, V., Digital First-Order Filter for Pulse-Duration Modulated Signal. Proceedings of the 7th International Symposium on IC Technology, Systems & Applications (ISIC-97),, Lucent Techologies, p.76--78, Nanyang Technological University School of Electrical and Electronic Engineering, Singapore, Sept. 1997.

   A novel circuit for a first order filter of signals that use pulse-duration modulation is suggested. The filter contains one counter of the reference frequency with a variable count modulus and a control circuit instead of usually used structure of two reference frequency counters and a microprocessor.

2. Tongjun Huang and Zixue Cheng, A Distributed Algorithm for Optimal Allocation of Resources. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'97), H.R.Arabnia. p.880--884, CSREA, July, 1997.

   In this paper, we present a new distributed algorithm for solving the resource allocation problem with multi-types of resources, by employing a technique called multiple matching. A merit of the algorithm is that it allocates the resources to as many processes as possible concurrently, so that only minimum processes need to wait.

3. Zixue Cheng and Qian-Ping GU, A Distributed Algorithm for Leader Election from a Partially Ordered Set on a Coterie. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'97), 1997. H.R.Arabnia, p.825 -- 828, CSREA, July 1997.

   One of the well studied distributed problems is leader election, which finds the process with the greatest key (identifier) from a set of processes in a network environment, assuming that each process has a unique key and a total order is defined on the set of keys. In this paper, we generalize the leader election problem by replacing the total order on the set of keys with a partially ordered on the set. We proposed a distributed algorithm which solves the generalized problem on a coterie, with the message complexity being $O(min\{K_{l}n\sqrt{n},n^2\})$.

4. Yutaka Wada, Zixue Cheng, and Tongjun Huang, A Distributed Algorithm for Allocation of Resources to Process Groups with Acyclic Graphs. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'97), H.R.Arabnia, p.801 - 805, CSREA, July, 1997.

   With the progress of computer networks, developments of applications for distributed cooperative group works in a network environment are regarded as important. Since there may be more than one group working in a network environment, these groups may compete for resources. The importance of the distributed resource allocation problem is already known well. In the paper, we propose a new distributed problem as an extension of the resource allocation problem, i.e. ``Allocation of Resources to Process Group'', and its solution. In this problem, there may exist deadlocks or starvation among groups. We call them ``group deadlocks'' and ``group starvation''. Our algorithm is based on an acyclic graph approach to the Dining Philosopher problem, and can allocate resources to groups of processes without group deadlock and group starvation. Also, our algorithm can be applied to a dynamic case, where processes of a group may join/leave in/off form the network environment.

5. Qian-Ping GU and Zixue Cheng, Efficient Estimation of Diameter for Distributed Networks. Proceedings of the 11th Annual International Symposium on High Performance Computing Systems (HPCS'97), July, 1997.

6. Zixue Cheng and Qian-Ping GU, A Distributed Algorithm for Leader Election from a Partially Ordered Set. Proceedings of the 11th Annual International Symposium on High Performance Computing Systems (HPCS'97), July, 1997.

7. Zixue Cheng, Naka Tajima, and Shoichi Noguchi, l-coterie: A New Generalization Coterie for Decentralized Consensus. Proceedings of the 12th International Conference on Information Networking (ICOIN--12), Jan. 1998.

8. Naik, K. and Tahara, Y. and Cheng, Z, Experimenting Distributed Algorithms on a Network of Workstations. 7th IEEE International Conference on High-Performance Distributed Computing, editor, S. Hariri, IEEE Press,

9. Kataoka, T. and Naik, K. and Wei, D., Crafting a Mobile Network Simulation Environment with Java. Proc. of the 9th International Conference on Computing and Communication, 1998, editor J. Barker.

10. Matsumaru, N. and Naik, K. and Wei, D., Comparing Three Location Management Strategies for Tracking Mobile Systems. Proc. of the PDPTA 98, 1998. Hamid Arabnia, editor.

1. Wei, D. and Naik, K., Advances in Randomized Parallel Computing Chapter: Efficient Randomized Algorithms for Parallel and Distributed Machines. editors: Pardalos, P. M. and Rajasekaran, S., Kluwer Academic Publishers, to appear.

1. Vyacheslav B. Marakhovsky, Member of ACM.

2. Vyacheslav B. Marakhovsky, Member of IEEE.

1. Noyama, K., A Support Method for Group Marriage Meeting Based on Subjective Expected Theory. The Univ. of Aizu, 1997. Thesis Advisor: Z. Cheng.

2. Yoshiki Hibino, A Negotiation Method among Multi-Agent for Grouping. The Univ. of Aizu, 1997. Thesis Advisor: Z. Cheng.

3. Yukiko Inoue, Distributed Allocation of Resources to Process Groups. The Univ. of Aizu", 1997. Thesis Advisor: Z. Cheng.

4. Haruka Kunii, A Distributed Method for Scheduling Meetings with Participant's Preference being considered. The Univ. of Aizu, 1997. Thesis Advisor: Z. Cheng.

5. Kenji Nogami, A Meeting Scheduling Method in a Mobile Environment. The Univ. of Aizu, 1997. Thesis Advisor: Z. Cheng.