在一定相容度下不确定性推理的可靠性分析

本文引入推理结论的可靠性度量，分析两种相容性对不确定性推理的影响，给出了推理结论可靠性的判别条件。     

Design and analysis of the Dual-Torus Network

In this paper, we propose a new topology called theDual Torus Network (DTN) which is constructed by adding interleaved edges to a torus. The DTN has many advantages over meshes and tori such as better extendibility, smaller diameter, higher bisection width, and robust link connectivity. The most important property of the DTN is that it can be partitioned into sub-tori of different sizes. This is not possible for mesh and torus-based systems. The DTN is investigated with respect to allocation, embedding, and fault-tolerant embedding. It is shown that the sub-torus allocation problem in the DTN reduces to the sub-mesh allocation problem in the torus. With respect to embedding, it is shown that a topology that can be embedded into a mesh with dilation δ can also be embedded into the DTN with less dilation. In fault-tolerant embedding, a fault-tolerant embedding method based on rotation, column insertion, and column skip is proposed. This method can embed any rectangular grid into its optimal square DTN when the number of faulty nodes is fewer than the number of unused nodes. In conclusion, the DTN is a scalable topology well-suited for massively parallel computation. Sang-Ho Chae, M.S.: He received the B.S. in the Computer Science and Engineering from the Pohang University of Science and Technology (POSTECH) in 1994, and the M.E. in 1996. Since 1996, he works as an Associate Research Engineer in the Central R&D Center of the SK Telecom Co. Ltd. He took part in developing SK Telecom Short Message Server whose subscribers are now over 3.5 million and Advanced Paging System in which he designed and implemented high availability concepts. His research interests are the Fault Tolerance, Parallel Processing, and Parallel Topolgies. Jong Kim, Ph.D.: He received the B.S. degree in Electronic Engineering from Hanyang University, Seoul, Korea, in 1981, the M.S. degree in Computer Science from the Korea Advanced Institute of Science and Technology, Seoul, Korea, in 1983, and the Ph.D. degree in Computer Engineering from Pennsylvania State University, U.S.A., in 1991. He is currently an Associate Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. Prior to this appointment, he was a research fellow in the Real-Time Computing Laboratory of the Department of Electrical Engineering and Computer Science at the University of Michigan from 1991 to 1992. From 1983 to 1986, he was a System Engineer in the Korea Securities Computer Corporation, Seoul, Korea. His major areas of interest are Fault-Tolerant Computing, Performance Evaluation, and Parallel and Distributed Computing. Sung Je Hong, Ph.D.: He received the B.S. degree in Electronics Engineering from Seoul National University, Korea, in 1973, the M.S. degree in Computer Science from Iowa State University, Ames, U.S.A., in 1979, and the Ph.D. degree in Computer Science from the University of Illinois, Urbana, U.S.A., in 1983. He is currently a Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. From 1983 to 1989, he was a staff member of Corporate Research and Development, General Electric Company, Schenectady, NY, U.S.A. From 1975 to 1976, he was with Oriental Computer Engineering, Korea, as a Logic Design Engineer. His current research interest includes VLSI Design, CAD Algorithms, Testing, and Parallel Processing. Sunggu Lee, Ph.D.: He received the B.S.E.E. degree with highest distinction from the University of Kansas, Lawrence, in 1985 and the M.S.E. and Ph.D. degrees from the University of Michigan, Ann Arbor, in 1987 and 1990, respectively. He is currently an Associate Professor in the Department of Electronic and Electrical Engineering at the Pohang University of Science and Technology (POSTECH), Pohang, Korea. Prior to this appointment, he was an Associate Professor in the Department of Electrical Engineering at the University of Delaware in Newark, Delaware, U.S.A. From June 1997 to July 1998, he spent one year as a Visiting Scientist at the IBM T. J. Watson Research Center. His research interests are in Parallel, Distributed, and Fault-Tolerant Computing. Currently, his main research focus is on the high-level and low-level aspects of Inter-Processor Communications for Parallel Computers.     

Common knowledge and consistent simultaneous coordination

Summary There is a very close relationship between common knowledge and simultaneity in synchronous distributed systems. The analysis of several well-known problems in terms of common knowledge has led to round-optimal protocols for these problems, includingReliable Broadcast, Distributed Consensus, and theDistributed Firing Squad problem. These problems require that the correct processors coordinate their actions in some way but place no restrictions on the behaviour of the faulty processors. In systems with benign processor failures, howrver, it is reasonable to require that the actions of a faulty processor be consistent with those of the correct processors, assuming it performs any action at all. We consider problems requiringconsistent, simultaneous coordination. We then analyze these problems in terms of common knowledge in several failure models. The analysis of these stronger problems requires a stronger definition of common knowledge, and we study the relationship between these two definitions. In many cases, the two definitions are actually equivalent, and simple modifications of previous solutions yield roundoptimal solutions to these problems. When the definitions differ, however, we show that such problems cannot be solved, even in failure-free executions. Gil Neiger was born on February 19, 1957 in New York, New York. In June 1979, he received an A.B. in Mathematics and Psycholinguistics from Brown University in Providence, Rhode Island. In February 1985, he spent two weeks picking cotton in Nicaragua in a brigade of international volunteers. In January 1986, he received an M.S. in Computer Science from Cornell University in Ithaca, New York. On August 20, 1988, Gil Neiger married Hilary Lombard in Lansing, New York. IN August 1988, he received a Ph.D. in Computer Science, also from Cornell University. Since August 1988, he has been an Assistant Professor in the College of Computing (formerly School of Information and Computer Science) at the Georgia Institute of Technology in Atlanta, Georgia. Mark Tuttle was born in Lincoln, Nebraska in 1962. He received his B.S. in math and computer science from the University of Nebraska-Lincoln in 1984, and his M.S. and Ph.D. from the Massachusetts Institute of Technology in 1987 and 1989. He is currently a member of the research staff at Digital Equipment Corporation's Cambridge Research Lab in Cambridge, Massachusetts. His research interests include models for distributed computation, knowledge and distributed computation, computer security, and concurrent data structures.An earlier version of this paper appeared in J. van Leeuwen and N. Santoro (eds.) Proceedings of the Fourth International Workshop on Distributed Algorithms, volume 486 of Lecture Notes on Computer Science, pages 334–352. Springer, September 1990This author was supported in part by the National Science Foundation under grants CCR-8909663 and CCR-9106627