Distributed match-making is a paradigm that deals with the match-making property of distributed issues such as name service, mutual exclusion, and replicated data management. In order to realize distributed match-making, two kinds of subsets with certain properties must be constructed for each process. We call a set of the subsets defined for all processes an arrangement." In this paper, we discuss arrangements for symmetric and fault-tolerant distributed match-making. First, it is shown that a combinatorial design called a symmetric balanced incomplete block design (SBIBD) can be applied to fault-tolerant distributed match-making. However, an SBIBD does not realize symmetry. We therefore focus on ways of achieving this. A completely symmetric arrangement for fault-tolerant distributed match-making does not always exist. We show that a completely symmetric arrangement called a symmetric resilient arrangement (SRA) exists when n/m is an integer, where n is the number of processes and m-1 is the resiliency of an algorithm. We present a method of constructing an SRA and generalize the method to allow construction of a generalized SRA (GSRA), which is almost symmetric and can be constructed with any combination of n and m. The communication complexity of fault-tolerant distributed match-making is also discussed. We show that the communication complexity of our SRA is 2mn and that the communication complexity of our GSRA is equal to or less than 2 min (mn/m, n). We also show that a lower bound of the communication complexity of an SBIBD is 2mn.

Distributed algorithms that entail successive rounds of message exchange are called decentralized consensus protocols. Several consensus protocols use a finite projective plane as a communication structure and require 4nn messages in two rounds, where n is the number of nodes. This paper presents an efficient communication structure that uses a finite projective plane with a duality of indices. The communication structure requires 2nn messages in two rounds, and can therefore halve the number of messages. It is shown that a finite projective plane with a duality can be constructed from a difference set, and that the presented communication structure has two kinds of symmetry.

Voting is a general way of achieving mutual exclusion and synchronization in distributed systems with replicated data. In centralized voting protocols, a requesting node, which works as a central controller, exchanges messages in order to collect votes from other nodes. This paper proposes decentralized voting protocols, in which all nodes execute the same protocol and reach the same result in a decentralized and autonomous way. When a decentalized voting protocol is implemented by using one-round message exchange, it requires n(n1) messages, where n is the number of nodes. The number of messages can be reduced by using multiple-round message exchange. The paper describes the computation in each node in the form of the finite state automaton, and gives communication structures for it. It is shown that kn(n1/k1) messages are enough when messages are exchanged in k rounds.

In current teleteaching systems, video conferencing systems have been used to transmit a motion video from a teacher's site. A video that captures a teacher or his or her chalkboard is transmitted to a remote site through a communication channel. Since the resolution of the video is not very high, a camera captures either a teacher or a chalkboard, but not both at the same time. Thus, remote students have difficulty in obtaining realistic sensation. Another approach to realizing teleteaching is to use a computer-based desktop conferencing system that supports a motion video and a computer-based shared chalkboard. In this approach, a teacher has to use a mouse or a handwriting tablet for input, and therefore cannot use a real chalkboard. Moreover, the teacher cannot use gestures to remote students. This paper presents a multimedia teleteaching system that integrates an electronic whiteboard with a multimedia desktop conferencing system for providing realistic sensation to remote students. The system provides two-way communication of a video and a computerized chalkboard. A teacher uses an electronic whiteboard as a real whiteboard using direct manipulation, and transmits his or her gestures to remote students by using video communication. The system provides dual views; one view is for teacher's gestures and the other is for chalkboard contents. By providing the dual views, the system can transmit teacher's gestures all the time. Since chalkboard contents are processed and displayed as computer data, students can see them clearly. With the computerized chalkboard, a teacher or a student can zoom contents, input data written on a paper using a scanner, or add annotation.