Asymptotically optimal algorithms for approximate agreement

This paper introduces some algorithms to solve crash-failure, failure-by-omission and Byzantine failure versions of the Byzantine Generals or consensus problem, where non-faulty processors need only arrive at values that are close together rather than identical. For each failure model and each value ofS, we give at-resilient algorithm usingS rounds of communication. IfS=t+1, exact agreement is obtained. In the algorithms for the failure-by-omission and Byzantine failure models, each processor attempts to identify the faulty processors and corrects values transmited by them to reduce the amount of disagreement. We also prove lower bounds for each model, to show that each of our algorithms has a convergence rate that is asymptotic to the best possible in that model as the number of processors increases. Alan Fekete was born in Sydney Australia in 1959. He studied Pure Mathematics and Computer Science at the University of Sydney, obtaining a B.Sc.(Hons) in 1982. He then moved to Cambridge, Massachusetts, where he obtained a distributed Ph.D. degree, awarded by Harvard University's Mathematics department for work supervised by Nancy Lynch in M.I.T.'s Laboratory for Computer Science. He spend the year 1987–1988 at M.I.T. as a postdoctoral Research Associate, and is now Lecturer in Computer Science at the University of Sydney. His research concentrates on understanding the modularity in distributed algorithms, especially those used for concurrency control in distributed databases.A preliminary version of this paper has appeared in the Proceedings of the 5th ACM Symposium on Principles of Distributed Computing (August 1986). This work was begun in the Department of Mathematics, Harvard University, and completed at the Laboratory for Computer Science at Massachusetts Institute of Technology. The work was supported in part (through Professor N. Lynch) by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under contract DAAG29-84-K-0058, by the National Science Foundation under Grants MCS-8306854, DCR-83-02391, and CCR-8611442, and by the Defense Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125     

Connectivity requirements for Byzantine agreement under restricted types of failures

We investigate the problem of reaching Byzantine Agreement in arbitrary networks where both processors and communication links are subject to omission or stopping faults. For the case of deterministic, synchronous algorithms we give a necessary and sufficient condition relating the solvability of the problem to the connectivity of the network. In particular, we show that an algorithm resilient to at mostt faulty processors andk faulty links subject to omission or stopping faults exist, if and only if the network has a connectivity pair (t, k)>(t, k).Vassos Hadzilacos received his BSE from Princeton in 1980 and his PhD from Harvard in 1984, both in Computer Science. He is presently an Assistant Professor at University of Toronto. His research interests are synchronisation and reliability in distributed computing. He is a co-author of a book on Concurrency Control and Reliability in Database Systems.     

S-Club: an overlay-based efficient service discovery mechanism in CROWN Grid

Information service plays a key role in grid system, handles resource discovery and management process. Employing existing information service architectures suffers from poor scalability, long search response time, and large traffic overhead. In this paper, we propose a service club mechanism, called S-Club, for efficient service discovery. In S-Club, an overlay based on existing Grid Information Service (GIS) mesh network of CROWN is built, so that GISs are organized as service clubs. Each club serves for a certain type of service while each GIS may join one or more clubs. S-Club is adopted in our CROWN Grid and the performance of S-Club is evaluated by comprehensive simulations. The results show that S-Club scheme significantly improves search performance and outperforms existing approaches. Chunming Hu is a research staff in the Institute of Advanced Computing Technology at the School of Computer Science and Engineering, Beihang University, Beijing, China. He received his B.E. and M.E. in Department of Computer Science and Engineering in Beihang University. He received the Ph.D. degree in School of Computer Science and Engineering of Beihang University, Beijing, China, 2005. His research interests include peer-to-peer and grid computing; distributed systems and software architectures. Yanmin Zhu is a Ph.D. candidate in the Department of Computer Science, Hong Kong University of Science and Technology. He received his B.S. degree in computer science from Xi’an Jiaotong University, Xi’an, China, in 2002. His research interests include grid computing, peer-to-peer networking, pervasive computing and sensor networks. He is a member of the IEEE and the IEEE Computer Society. Jinpeng Huai is a Professor and Vice President of Beihang University. He serves on the Steering Committee for Advanced Computing Technology Subject, the National High-Tech Program (863) as Chief Scientist. He is a member of the Consulting Committee of the Central Government’s Information Office, and Chairman of the Expert Committee in both the National e-Government Engineering Taskforce and the National e-Government Standard office. Dr. Huai and his colleagues are leading the key projects in e-Science of the National Science Foundation of China (NSFC) and Sino-UK. He has authored over 100 papers. His research interests include middleware, peer-to-peer (P2P), grid computing, trustworthiness and security. Yunhao Liu received his B.S. degree in Automation Department from Tsinghua University, China, in 1995, and an M.A. degree in Beijing Foreign Studies University, China, in 1997, and an M.S. and a Ph.D. degree in computer science and engineering at Michigan State University in 2003 and 2004, respectively. He is now an assistant professor in the Department of Computer Science and Engineering at Hong Kong University of Science and Technology. His research interests include peer-to-peer computing, pervasive computing, distributed systems, network security, grid computing, and high-speed networking. He is a senior member of the IEEE Computer Society. Lionel M. Ni is chair professor and head of the Computer Science and Engineering Department at Hong Kong University of Science and Technology. Lionel M. Ni received the Ph.D. degree in electrical and computer engineering from Purdue University, West Lafayette, Indiana, in 1980. He was a professor of computer science and engineering at Michigan State University from 1981 to 2003, where he received the Distinguished Faculty Award in 1994. His research interests include parallel architectures, distributed systems, high-speed networks, and pervasive computing. A fellow of the IEEE and the IEEE Computer Society, he has chaired many professional conferences and has received a number of awards for authoring outstanding papers.     

On the message complexity of binary byzantine agreement under crash failures

Summary The binary Byzantine Agreement problem requiresn–1 receivers to agree on the binary value broadcast by a sender even when some of thesen processes may be faulty. We investigate the message complexity of protocols that solve this problem in the case of crash failures. In particular, we derive matching upper and lower bounds on the total, worst and average case number of meassages needed in the failure-free executions of such protocols.More specifically, we prove that any protocol that tolerates up tot faulty processes requires a total of at leastn+t–1 messages in its failure-free executions —and, therefore, at least [(n+t–1)/2] messages in the worst case and min (P ₀,P ₁)·(n+t–1) meassages in the average case, whereP _v is the probability that the value of the bit that the sender wants to broadcast isv. We also give protocols that solve the problem using only the minimum number of meassages for these three complexity measures. These protocols can be implemented by using 1-bit messages. Since a lower bound on the number of messages is also a lower bound on the number of meassage bits, this means that the above tight bounds on the number of messages are also tight bounds on the number of meassage bits. Vassos Hadzilacos received a BSE from Princeton University in 1980 and a PhD from Harvard University in 1984, both in Computer Science. In 1984 he joined the Department of Computer Science at the University of Toronto where he is currently an Associate Professor. In 1990–1991 he was visiting Associate Professor in the Department of Computer Science at Cornell University. His research interests are in the theory of distributed systems. Eugene Amdur obtained a B. Math from the University of Waterloo in 1986 and a M.Sc. from the University of Toronto in 1988. He is currently employed by the Vision and Robotics group at the University of Toronto in both technical and research capacities. His current areas of interest are vision, robotics, and networking. Samuel Weber received his B.Sc. in Mathematics and Computer Science and his M.Sc. in Computer Science from the University of Toronto. Currently, he is at Cornell University as a Ph.D. student in Computer Science with a minor in Psychology. His research interests include distributed systems, and the semantics of programming languages.     

Efficient agreement using fault diagnosis

Summary We give an extremely simple Byzantine agreement protocol that usesO(t ²) processors, min(f+2,t+1) rounds of communication,O(n·t·f·log|V|) total message bits, andO(log|V|) maximum message size, wheren is the total number of processors that actually participate in the protocol,t is an upper bound on the number of faulty processors,f is the number of processors that actually fail in a given execution, andV is the set of possible inputs. This protocol uses roughly the same resources as a more complex protocol due to Dolev, Reischuk, and Strong. By adding explicit fault diagnosis to our first protocol, we produce a some-what more complicated protocol that usesO(t ^1.5) processors, min(f+2,t+1) rounds,O(n·t ² ·f·log|V|) total message bits, andO(t·log|V|) maximum message size. Brian A. Coan received the B.S.E. degree in electrical engineering and computer science from Princeton University in 1977, the M.S. degree in computer engineering from Stanford University in 1979, and the Ph.D. degree in computer science from the Massachusetts Institute of Technology in 1987. He has worked for Amdahl Corporation and AT&T Bell Laboratories. Since 1987 he has been a member of the technical staff in the Network Systems Research Department at Bellcore. His main research interests are in distributed systems, fault tolerance, and platforms to support distributed multimedia systems.A preliminary version of this paper appeared in the Proceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing, pp 663–672, 1988     

Preference update for e-commerce applications: Model,language, and processing

It is likely that customers issue requests based on out-of-date information in e-commerce application systems. Hence, the transaction failure rates would increase greatly. In this paper, we present a preference update model to address this problem. A preference update is an extended SQL update statement where a user can request the desired number of target data items by specifying multiple preferences. Moreover, the preference update allows easy extraction of criteria from a set of concurrent requests and, hence, optimal decisions for the data assignments can be made. We propose a group evaluation strategy for preference update processing in a multidatabase environment. The experimental results show that the group evaluation can effectively increase the customer satisfaction level with acceptable cost. Peng Li is the Chief Software Architect of didiom LLC. Before that, he was a visiting assistant professor of computer science department in Western Kentucky University. He received his Ph.D. degree of computer science from the University of Texas at Dallas. He also holds a B.Sc. and M.S. in Computer Science from the Renmin University of China. His research interests include database systems, database security, transaction processing, distributed and Internet computer and E-commerce. Manghui Tu received a Bachelor degree of Science from Wuhan University, P.R. China in 1996, and a Master Degree in Computer Science from the University of Texas at Dallas 2001. He is currently working toward the PhD degree in the Department of Computer Science at the University of Texas at Dallas. Mr. Tu’s research interests include distributed systems, grid computing, information security, mobile computing, and scientific computing. His PhD research work focus on the data management in secure and high performance data grid. He is a student member of the IEEE. I-Ling Yen received her BS degree from Tsing-Hua University, Taiwan, and her MS and PhD degrees in Computer Science from the University of Houston. She is currently an Associate Professor of Computer Science at the University of Texas at Dallas. Dr. Yen’s research interests include fault-tolerant computing, security systems and algorithms, distributed systems, Internet technologies, E-commerce, and self-stabilizing systems. She had published over 100 technical papers in these research areas and received many research awards from NSF, DOD, NASA, and several industry companies. She has served as Program Committee member for many conferences and Program Chair/Co-Chair for the IEEE Symposium on Application-Specific Software and System Engineering & Technology, IEEE High Assurance Systems Engineering Symposium, IEEE International Computer Software and Applications Conference, and IEEE International Symposium on Autonomous Decentralized Systems. She is a member of the IEEE. Zhonghang Xia received the B.S. degree in applied mathematics from Dalian University of Technology in 1990, the M.S. degree in Operations Research from Qufu Normal University in 1993, and the Ph.D. degree in computer science from the University of Texas at Dallas in 2004. He is now an assistant professor in the Department of Computer Science, Western Kentucky University, Bowling Green, KY. His research interests are in the area of multimedia computing and networking, distributed systems, and data mining.     

Modular construction of an efficient 1-bit Byzantine agreement protocol

This paper presents a new Byzantine agreement protocol that toleratest processor faults usingO(t·logt) processors,t + 1 rounds,O(t ² +o·t) total message bits (whereo is the number of processors that must decide), and messages of maximum size 1 bit. It is the first Byzantine agreement protocol that is simultaneously optimal in rounds, message bits, and message size. The new Byzantine agreement protocol is actually a protocol for the (slightly) more general Byzantine relay problem—a problem which we formulate in this paper. The Byzantine relay protocol is the result of a general recursive construction. Each step of the construction combines two smaller (in terms of number of faults tolerated) Byzantine relay protocols into one larger Byzantine relay protocol. The base case is a collection of very simple Byzantine relay protocols, each tolerant of a small constant number of processor faults. A key new feature of the protocol construction technique presented in this paper is that it does not add unproductive overhead rounds: given two constituent protocols that are optimal in the number of rounds, the composite protocol that is constructed is also optimal in the number of rounds.The work of Jennifer Welch was supported in part by NSF Grant CCR-9010730 and an IBM Faculty Development Award. This work was done while she was at the University of North Carolina at Chapel Hill.     

Implementation of hierarchical F-channels for high-performance distributed computing

Summary High performance distributed computing systems require high performance communication systems.F-channels andHierarchical F-channels address this need by permitting a high level of concurrency like non-FIFO channels while retaining the simplicity of FIFO channels critical to the design and proof of many distributed algorithms. In this paper, we present counter-based implementations for F-channels and Hierarchical F-channels using message augmentation-appending control information to a message. These implementations guarantee that no messages are unnecessarily delayed at the receiving end. Keith Shafer received the B.A. degree in computer science and mathematics in 1986 from Mount Vernon Nazarene College, Mount Vernon, Ohio, USA, and the M.S. and Ph.D. degrees in computer science from The Ohio State University, Columbus, Ohio, USA, in 1988 and 1992, respectively. He is currently a Senior Research Scientist at OCLC Online Computer Library Center Inco, Dublin, OH, USA. His research interests include tools for comparing logical channels and methods for automatically constructing corpus grammars from tagged documents as an aid for database preparation and document conversion. Dr. Shafer is a member of the IEEE Computer Society. Mohan Ahuja received the M.A. degree in 1983 and the Ph.D. degree in 1985, both in computer science, from the University of Texas at Austin. He is currently with Department of Computer Science and Engineering, Univ. of California, San Diego. His recent research contributions include Global Flushing, message receipt in Receive-Phases, Incremental Publication of a Partial Order, Design of Highways (a high-performance distributed programming system) and — in collaboration with others — Passive-space and Time View, Performance evaluation of F-Channels, and Units of Computation in Fault-Tolerant Distributed Systems. His current research interests are in high-performance distributed communication and computing architectures, building high-performance systems, distributed operating systems, distributed algorithms, fault tolerance, and performance evaluation.Parts of this paper appeared in two conference papers, (1) Distributed Modeling and Implementation of High Performance Communication Architectures, in proceedings of the Thirteenth IEEE International Conference on Distributed Computing Systems, papes 56–65, 1993 and (2) Process-Channel_agem-Process model of asynchronous distributed communication, in proceedings of the Twelfth IEEE International Conference on Distributed Computing Systems, pages 4–11, 1992     

Multiagent learning towards RoboCup

This article describes the issues in multiagent learning towards RoboCup,^1≈3) especially for the real robot leagues. First, the review of the issue in the context of the related area is given, then related works from several viewpoints are reviewed. Next, our approach towards RoboCup Initiative is introduced and finally future issues are given. Minoru Asada, Ph.D.: He received B.E., M.Sc., and Ph.D., degrees in control engineering from Osaka University, in 1977, 1979, and 1982, respectively. From 1982 to 1988, he was a research associate of Control Engineering, Osaka University. In 1989, he became an associate professor of Mechanical Engineering for Computer-Controlled Machinery, Osaka University. In 1995 he became a professor of the department of Adaptive Machine Systems at the same university. From 1986 to 1987, he was a visiting researcher of Center for Automation Research, University of Maryland, College Park, MD. He received the 1992 best paper award of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS92), and the 1996 best paper award of RSJ (Robotics Society of Japan). Also, his paper was one of the finalists of IEEE Robotics and Automation Society 1995 Best Conference Paper Award. He was a general chair of IEEE/RSJ 1996 International Conference on Intelligent Robots and Systems (IROS96). Since early 1990, he has been involved in RoboCup activities and his team was the first champion team with USC team in the middle size league of the first RoboCup held in conjunction with IJCAI-97, Nagoya, Japan. Eiji Uchibe, Ph.D.: He received a Ph.D. degree in mechanical engineering from Osaka University in 1999. He is currently a research associate of the Japan Society for the Promotion of Science, in Research for the Future Program titled Cooperative Distributed Vision for Dynamic Three Dimensional Scene Understanding. His research interests are in reinforcement learning, evolutionary computation, and their applications. He is a member of IEEE, AAAI, RSJ, and JSAI.     

A study of the model and algorithms for handling location-dependent continuous queries

Advances in wireless and mobile computing environments allow a mobile user to access a wide range of applications. For example, mobile users may want to retrieve data about unfamiliar places or local life styles related to their location. These queries are called location-dependent queries. Furthermore, a mobile user may be interested in getting the query results repeatedly, which is called location-dependent continuous querying. This continuous query emanating from a mobile user may retrieve information from a single-zone (single-ZQ) or from multiple neighbouring zones (multiple-ZQ). We consider the problem of handling location-dependent continuous queries with the main emphasis on reducing communication costs and making sure that the user gets correct current-query result. The key contributions of this paper include: (1) Proposing a hierarchical database framework (tree architecture and supporting continuous query algorithm) for handling location-dependent continuous queries. (2) Analysing the flexibility of this framework for handling queries related to single-ZQ or multiple-ZQ and propose intelligent selective placement of location-dependent databases. (3) Proposing an intelligent selective replication algorithm to facilitate time- and space-efficient processing of location-dependent continuous queries retrieving single-ZQ information. (4) Demonstrating, using simulation, the significance of our intelligent selective placement and selective replication model in terms of communication cost and storage constraints, considering various types of queries. Manish Gupta received his B.E. degree in Electrical Engineering from Govindram Sakseria Institute of Technology & Sciences, India, in 1997 and his M.S. degree in Computer Science from University of Texas at Dallas in 2002. He is currently working toward his Ph.D. degree in the Department of Computer Science at University of Texas at Dallas. His current research focuses on AI-based software synthesis and testing. His other research interests include mobile computing, aspect-oriented programming and model checking. Manghui Tu received a Bachelor degree of Science from Wuhan University, P.R. China, in 1996, and a Master's Degree in Computer Science from the University of Texas at Dallas 2001. He is currently working toward the Ph.D. degree in the Department of Computer Science at the University of Texas at Dallas. Mr. Tu's research interests include distributed systems, wireless communications, mobile computing, and reliability and performance analysis. His Ph.D. research work focuses on the dependent and secure data replication and placement issues in network-centric systems. Latifur R. Khan has been an Assistant Professor of Computer Science department at University of Texas at Dallas since September 2000. He received his Ph.D. and M.S. degrees in Computer Science from University of Southern California (USC) in August 2000 and December 1996, respectively. He obtained his B.Sc. degree in Computer Science and Engineering from Bangladesh University of Engineering and Technology, Dhaka, Bangladesh, in November of 1993. Professor Khan is currently supported by grants from the National Science Foundation (NSF), Texas Instruments, Alcatel, USA, and has been awarded the Sun Equipment Grant. Dr. Khan has more than 50 articles, book chapters and conference papers focusing in the areas of database systems, multimedia information management and data mining in bio-informatics and intrusion detection. Professor Khan has also served as a referee for database journals, conferences (e.g. IEEE TKDE, KAIS, ADL, VLDB) and he is currently serving as a program committee member for the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD2005), ACM 14th Conference on Information and Knowledge Management (CIKM 2005), International Conference on Database and Expert Systems Applications DEXA 2005 and International Conference on Cooperative Information Systems (CoopIS 2005), and is program chair of ACM SIGKDD International Workshop on Multimedia Data Mining, 2004. Farokh Bastani received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, and the M.S. and Ph.D. degrees in Computer Science from the University of California, Berkeley. He is currently a Professor of Computer Science at the University of Texas at Dallas. Dr. Bastani's research interests include various aspects of the ultrahigh dependable systems, especially automated software synthesis and testing, embedded real-time process-control and telecommunications systems and high-assurance systems engineering. Dr. Bastani was the Editor-in-Chief of the IEEE Transactions on Knowledge and Data Engineering (IEEE-TKDE). He is currently an emeritus EIC of IEEE-TKDE and is on the editorial board of the International Journal of Artificial Intelligence Tools, the International Journal of Knowledge and Information Systems and the Springer-Verlag series on Knowledge and Information Management. He was the program cochair of the 1997 IEEE Symposium on Reliable Distributed Systems, 1998 IEEE International Symposium on Software Reliability Engineering, 1999 IEEE Knowledge and Data Engineering Workshop, 1999 International Symposium on Autonomous Decentralised Systems, and the program chair of the 1995 IEEE International Conference on Tools with Artificial Intelligence. He has been on the program and steering committees of several conferences and workshops and on the editorial boards of the IEEE Transactions on Software Engineering, IEEE Transactions on Knowledge and Data Engineering and the Oxford University Press High Integrity Systems Journal. I-Ling Yen received her B.S. degree from Tsing-Hua University, Taiwan, and her M.S. and Ph.D. degrees in Computer Science from the University of Houston. She is currently an Associate Professor of Computer Science at University of Texas at Dallas. Dr. Yen's research interests include fault-tolerant computing, security systems and algorithms, distributed systems, Internet technologies, E-commerce and self-stabilising systems. She has published over 100 technical papers in these research areas and received many research awards from NSF, DOD, NASA and several industry companies. She has served as Program Committee member for many conferences and Program Chair/Cochair for the IEEE Symposium on Application-Specific Software and System Engineering & Technology, IEEE High Assurance Systems Engineering Symposium, IEEE International Computer Software and Applications Conference, and IEEE International Symposium on Autonomous Decentralized Systems. She has also served as a guest editor for a theme issue of IEEE Computer devoted to high-assurance systems.     

Fast evaluation of Bounded Slice-line Grid

Bounded Slice-line Grid (BSG) is an elegant representation of block placement, because it is very intuitionistic and has the advantage of handling various placement constraints. However, BSG has attracted little attention because its evaluation is very time-consuming. This paper proposes a simple algorithm independent of the BSG size to evaluate the BSG representation in O(nloglogn) time, where n is the number of blocks. In the algorithm, the BSG-rooms are assigned with integral coordinates firstly, and then a linear sorting algorithm is applied on the BSG-rooms where blocks are assigned to compute two block sequences, from which the block placement can be obtained in O(n log logn) time. As a consequence, the evaluation of the BSG is completed in O(nloglogn) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n^2) algorithm. The experimental results demonstrate the efficiency of the algorithm.     

A challenge towards next-generation research infrastructure for advanced life science

Recently, life scientists have expressed a strong need for computational power sufficient to complete their analyses within a realistic time as well as for a computational power capable of seamlessly retrieving biological data of interest from multiple and diverse bio-related databases for their research infrastructure. This need implies that life science strongly requires the benefits of advanced IT. In Japan, the Biogrid project has been promoted since 2002 toward the establishment of a next-generation research infrastructure for advanced life science. In this paper, the Biogrid strategy toward these ends is detailed along with the role and mission imposed on the Biogrid project. In addition, we present the current status of the development of the project as well as the future issues to be tackled. Haruki Nakamura, Ph.D.: He is Professor of Protein Informatics at Institute for Protein Research, Osaka University. He received his B.S., M.A. and Ph.D. from the University of Tokyo in 1975, 1977 and 1980 respectively. His research field is Biophysics and Bioinformatics, and has so far developed several original algorithms in the computational analyses of protein electrostatic features and folding dynamics. He is also a head of PDBj (Protein Data Bank Japan) to manage and develop the protein structure database, collaborating with RCSB (Research Collaboratory for Structural Bioinformatics) in USA and MSD-EBI (Macromolecular Structure Database at the European Bioinformatics Institute) in EU. Susumu Date, Ph.D.: He is Assistant Professor of the Graduate School of Information Science and Technology, Osaka University. He received his B.E., M.E. and Ph.D. degrees from Osaka University in 1997, 2000 and 2002, respectively. His research field is computer science and his current research interests include application of Grid computing and related information technologies to life sciences. He is a member of IEEE CS and IPSJ. Hideo Matsuda, Ph.D.: He is Professor of the Department of Bioinformatic Engineering, the Graduate School of Information Science and Technology, Osaka University. He received his B.S., M.Eng. and Ph.D. degrees from Kobe University in 1982, 1984 and 1987 respectively. For M.Eng. and Ph.D. degrees, he majored in computer science. His research interests include computational analysis of genomic sequences. He has been involved in the FANTOM (Functional Annotation of Mouse) Project for the functional annotation of RIKEN mouse full-length cDNA sequences. He is a member of ISCB, IEEE CS and ACM. Shinji Shimojo, Ph.D.: He received M.E. and Ph.D. degrees from Osaka University in 1983 and 1986 respectively. He was an Assistant Professor with the Department of Information and Computer Sciences, Faculty of Engineering Science at Osaka University from 1986, and an Associate Professor with Computation Center from 1991 to 1998. During the period, he also worked as a visiting researcher at the University of California, Irvine for a year. He has been Professor with Cybermedia Center (then Computation Center) at Osaka University since 1998. His current research work focus on a wide variety of multimedia applications, peer-to-peer communication networks, ubiquitous network systems and Grid technologies. He is a member of ACM, IEEE and IEICE.     

Auto-generation of IEC standard PLC code using t-MPSG

The objective of this paper is to reduce the development time of a PLC (Programmable Logic Controller) by automating the task of code generation. For this purpose, we applied t-MPSG (Timed-Message Based Part State Graph). The t-MPSG is an extended finite state automata used to model and generate an execution module for a real-time shop floor controller system. In our proposed method, t-MPSG is used to model the formal specification of the controller system that can be translated into textual structure. After the verification of the t-MPSG model, it can be used as an input to the plc-builder tool. The plc-builder tool is an extended version of a conventional MPSG simulator. It can be used to translate the textual structure of the t-MPSG into an IEC standard PLC code. Finally, the generated code can be downloaded to a PLC emulator or a PLC device for the purpose of simulation and execution. The similarity in the hierarchical structure of the t-MPSG and the IEC standard PLC program has made it convenient to transform from one form to another. Furthermore, an illustration of the methodology to auto-generate IEC standard PLC code using t-MPSG is explained with a suitable example. Recommended by Editorial Board member Young Soo Suh under the direction of Editor Jae Weon Choi. This work was partially supported by Defense Acquisition Program Administration and Agency for Defense Development under the contract (UD080042AD). Devinder Thapa is a Postdoc Research Fellow in the Department of Industrial & information systems at Ajou University, Korea. He completed his Ph.D. from Ajou University in Industrial and Information Systems Engineering. His area of research is related to manufacturing automation and intelligent decision support systems. Chang Mok Park is a Professor in the Department of Technology & Systems Management at Induk Institute of Technology. He completed his Ph.D. in 2002 from Ajou University in Industrial Engineering. His research interest is related to manufacturing optimization, discrete event system simulation and signal analysis. Sang C. Park is an Associate Professor in the Department of Industrial & Information Systems Engineering at Ajou University. He received his B.S., M.S., and Ph.D. degrees from KAIST in 1994, 1996, and 2000, respectively, all in Industrial Engineering. His research interests include geometric algorithms in CAD/CAM, process planning, engineering knowledge management, and discrete event system simulation. Gi-Nam Wang is the Head and a Professor in the Department of Industrial & Information Systems Engineering at Ajou University, Korea. He completed his Ph.D. in 1992 from Texas A&M University, in Industrial Engineering. He has worked as Visiting Professor at University of Texas at Austin during 2000–2001. His area of research is related to Intelligent Information & manufacturing systems, system integration & automation, e-Business solutions and image processing.     

Easy impossibility proofs for distributed consensus problems

Easy proofs are given, of the impossibility of solving several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in certain communication graphs.It is shown that, in the presence ofm faults, no solution to these problems exists for communication graphs with fewer than 3m+1 nodes or less than 2m+1 connectivity. While some of these results had previously been proved, the new proofs are much simpler, provide considerably more insight, apply to more general models of computation, and (particularly in the case of clock synchronization) significantly strengthen the results.Michael J. Fischer is currently Professor of Computer Science at Yale University, New Haven, CT, where he heads the Theory of Computation Group. He is also Editor-in-Chief of the Journal of the Association for Computing Machinery. His research interests include theory of distributed systems, cryptographic protocols, and computational complexity.Dr. Fischer received the B. S. degree in matheamtics from the University of Michigan, Ann Arbor, in 1963, and the M. A. and Ph. D. degrees in applied mathematics from Harvard University, Cambridge, MA, in 1965 and 1968, respectively. He has taught previously at Carnegie-Mellon University, the Massachusetts Institute of Technology, and University of Washington.Nancy Lynch is currently Associate professor of Computer Science at M.I.T., and heads the Theory of Distributed Systems group in M.I.T.'s Laboratory for Computer Science. Her interests are in all aspects of distributed computing theory, including formal models, algorithms, analysis, and correctness proofs. Dr. Lynch received the B.S. degree in mathematics from Brooklyn College in 1968 and the Ph. D. degree in mathematics from M.I.T. in 1972. She has served on the faculty of Tufts University, the University of Southern California, Florida International University, Georgia Tech.Michael Merritt is currently a member of the technical staff with AT&T Bell Laboratories. During the 1984 –85 academic year, he was a visiting lecturer at M.I.T., sponsered by Bell Labs. His research interests include distributed computation, cryptography and security. Dr. Merritt received the B. S. degree in computer science and philosophy from Yale in 1978 and the M. Sc. and Ph. D. degrees in 1980 and 1983, respectively, both in information and computer science from Georgia Tech. He is a member of SIGACT and of Computer Professionals for Social Responsibility.This paper has appeared in the ACM Conference Proceedings of PODC 1985. © 1985, Association for Computing Machinery, reprinted by permission     

Test Resource Partitioning Based on Efficient Response Compaction for Test Time and Tester Channels Reduction

This paper presents a test resource partitioning technique based on an efficient response compaction design called quotient compactor(q-Compactor). Because q-Compactor is a single-output compactor, high compaction ratios can be obtained even for chips with a small number of outputs. Some theorems for the design of q-Compactor are presented to achieve full diagnostic ability, minimize error cancellation and handle unknown bits in the outputs of the circuit under test (CUT). The q-Compactor can also be moved to the load-board, so as to compact the output response of the CUT even during functional testing. Therefore, the number of tester channels required to test the chip is significantly reduced. The experimental results on the ISCAS ‘89 benchmark circuits and an MPEG 2 decoder SoC show that the proposed compactionscheme is very efficient.     

A new fast algorithm for multitarget tracking in dense

A fast joint probabilistic data association （FJPDA） algorithm is proposed in tiffs paper. Cluster probability matrix is approximately calculated by a new method, whose elements βi^t（K） can be taken as evaluation functions. According to values of βi^t（K）, N events with larger joint probabilities can be searched out as the events with guiding joint probabilities, tiros, the number of searching nodes will be greatly reduced. As a result, this method effectively reduces the calculation load and nnkes it possible to be realized on real-thne, Theoretical ,analysis and Monte Carlo simulation results show that this method is efficient.     

Adaptive group scheduling mechanism using mobile agents in peer-to-peer grid computing environment

Peer-to-peer grid computing is an attractive computing paradigm for high throughput applications. However, both volatility due to the autonomy of volunteers (i.e., resource providers) and the heterogeneous properties of volunteers are challenging problems in the scheduling procedure. Therefore, it is necessary to develop a scheduling mechanism that adapts to a dynamic peer-to-peer grid computing environment. In this paper, we propose a Mobile Agent based Adaptive Group Scheduling Mechanism (MAAGSM). The MAAGSM classifies and constructs volunteer groups to perform a scheduling mechanism according to the properties of volunteers such as volunteer autonomy failures, volunteer availability, and volunteering service time. In addition, the MAAGSM exploits a mobile agent technology to adaptively conduct various scheduling, fault tolerance, and replication algorithms suitable for each volunteer group. Furthermore, we demonstrate that the MAAGSM improves performance by evaluating the scheduling mechanism in Korea@Home. SungJin Choi is a Ph.D. student in the Department of Computer Science and Engineering at Korea University. His research interests include mobile agent, peer-to-peer computing, grid computing, and distributed systems. Mr. Choi received a M.S. in computer science from Korea University. He is a student member of the IEEE. MaengSoon Baik is a senior research member at the SAMSUNG SDS Research & Develop Center. His research interests include mobile agent, grid computing, server virtualization, storage virtualization, and utility computing. Dr. Baik received a Ph.D. in computer science from Korea University. JoonMin Gil is a professor in the Department of Computer Science Education at Catholic University of Daegu, Korea. His recent research interests include grid computing, distributed and parallel computing, Internet computing, P2P networks, and wireless networks. Dr. Gil received his Ph.D. in computer science from Korea University. He is a member of the IEEE and the IEICE. SoonYoung Jung is a professor in the Department of Computer Science Education at Korea University. His research interests include grid computing, web-based education systems, database systems, knowledge management systems, and mobile computing. Dr. Jung received his Ph.D. in computer science from Korea University. ChongSun Hwang is a professor in the Department of Computer Science and Engineering at Korea University. His research interests include distributed systems, distributed algorithms, and mobile computing. Dr. Hwang received a Ph.D. in statistics and computer science from the University of Georgia.     

An inexpensive unstructured platform for wireless mobile peer-to-peer networks

In this paper, we propose an unstructured platform, namely I nexpensive P eer-to- P eer S ubsystem (IPPS), for wireless mobile peer-to-peer networks. The platform addresses the constraints of expensive bandwidth of wireless medium, and limited memory and computing power of mobile devices. It uses a computationally-, memory requirement- and communication- wise inexpensive gossip protocol as the main maintenance operation, and exploits location information of the wireless nodes to minimize the number of link-level messages for communication between peers. As a result, the platform is not only lightweight by itself, but also provides a low cost framework for different peer-to-peer applications. In addition, further enhancements are introduced to enrich the platform with robustness and tolerance to failures without incurring any additional computational and memory complexity, and communication between peers. In specific, we propose schemes for a peer (1) to chose a partner for a gossip iteration, (2) to maintain the neighbors, and (3) to leave the peer-to-peer network. Simulation results are given to demonstrate the performance of the platform.

GigaE PM: a high performance communication facility using a Gigabit Ethernet

A high performance communication facility, called theGigaE PM, has been designed and implemented for parallel applications on clusters of computers using a Gigabit Ethernet. The GigaE PM provides not only a reliable high bandwidth and low latency communication, but also supports existing network protocols such as TCP/IP. A reliable communication mechanism for a parallel application is implemented on the firmware on a NIC while existing network protocols are handled by an operating system kernel. A prototype system has been implemented using an Essential Communications Gigabit Ethernet card. The performance results show that a 58.3 μs round trip time for a four byte user message, and 56.7 MBytes/sec bandwidth for a 1,468 byte message have been achieved on Intel Pentium II 400 MHz PCs. We have implemented MPICH-PM on top of the GigaE PM, and evaluated the NAS parallel benchmark performance. The results show that the IS class S performance on the GigaE PM is 1.8 times faster than that on TCP/IP. Shinji Sumimoto: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He received BS degree in electrical engineering from Doshisha University. His research interest include parallel and distributed systems, real-time systems, and high performance communication facilities. He is a member of Information Processing Society of Japan. Hiroshi Tezuka: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include real-time systems and operating system kernel. He is a member of the Information Processing Society of Japan, and Japan Society for Software Science and Technology. Atsushi Hori, Ph.D.: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His current research interests include parallel operating system. He received B.S. and M.S. degrees in Electrical Engineering from Waseda University, and received Ph.D. from the University of Tokyo. He worked as a researcher in Mitsubishi Research Institute from 1981 to 1992. Hiroshi Harada: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include distributed/parallel systems and distributed shared memory. He received BS degree in physics from Science University of Tokyo. He is a member of ACM and Information Processing Society of Japan. Toshiyuki Takahashi: He is a Researcher at Real World Computing Partnership since 1998. He received his B.S. and M.S. from the Department of Information Sciences of Science University of Tokyo in 1993 and 1995. He was a student of the Information Science Department of the University of Tokyo from 1995 to 1998. His current interests are in meta-level architecture for programming languages and high-performance software technologies. He is a member of Information Processing Society of Japan. Yutaka Ishikawa, Ph.D.: He is the chief of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He is currently temporary retirement from Electrotechnical Laboratory, MITI. His research interests include distributed/parallel systems, object-oriented programming languages, and real-time systems. He received the B.S., M.S. and Ph.D degrees in electrical engineering from Keio University. He is a member of the IEEE Computer Society, ACM, Information Processing Society of Japan, and Japan Society for Software Science and Technology.     

Handicapping attacker's confidence: an alternative to <Emphasis Type="Italic">k</Emphasis>-anonymization

We present an approach of limiting the confidence of inferring sensitive properties to protect against the threats caused by data mining abilities. The problem has dual goals: preserve the information for a wanted data analysis request and limit the usefulness of unwanted sensitive inferences that may be derived from the release of data. Sensitive inferences are specified by a set of “privacy templates". Each template specifies the sensitive property to be protected, the attributes identifying a group of individuals, and a maximum threshold for the confidence of inferring the sensitive property given the identifying attributes. We show that suppressing the domain values monotonically decreases the maximum confidence of such sensitive inferences. Hence, we propose a data transformation that minimally suppresses the domain values in the data to satisfy the set of privacy templates. The transformed data is free of sensitive inferences even in the presence of data mining algorithms. The prior k-anonymization k has been italicized consistently throughout this article. focuses on personal identities. This work focuses on the association between personal identities and sensitive properties. Ke Wang received Ph.D. from Georgia Institute of Technology. He is currently a professor at School of Computing Science, Simon Fraser University. Before joining Simon Fraser, he was an associate professor at National University of Singapore. He has taught in the areas of database and data mining. Dr. Wang’s research interests include database technology, data mining and knowledge discovery, machine learning, and emerging applications, with recent interests focusing on the end use of data mining. This includes explicitly modeling the business goal (such as profit mining, bio-mining and web mining) and exploiting user prior knowledge (such as extracting unexpected patterns and actionable knowledge). He is interested in combining the strengths of various fields such as database, statistics, machine learning and optimization to provide actionable solutions to real-life problems. He is an associate editor of the IEEE TKDE journal and has served program committees for international conferences. Benjamin C. M. Fung received B.Sc. and M.Sc. degrees in computing science from Simon Fraser University. Received the postgraduate scholarship doctoral award from the Natural Sciences and Engineering Research Council of Canada (NSERC), Mr. Fung is currently a Ph.D. candidate at Simon Fraser. His recent research interests include privacy-preserving data mining, secure distributed computing, and text mining. Before pursuing his Ph.D., he worked in the R&D Department at Business Objects and designed reporting systems for various Enterprise Resource Planning (ERP) and Customer Relationship Management (CRM) systems, including BaaN, Siebel, and PeopleSoft. Mr. Fung has published in data engineering, data mining, and security conferences, journals, and books, including IEEE ICDE, IEEE ICDM, IEEE ISI, SDM, KAIS, and the Encyclopedia of Data Warehousing and Mining. Philip S. Yu received B.S. degree in E.E. from National Taiwan University, M.S. and Ph.D. degrees in E.E. from Stanford University, and M.B.A. degree from New York University. He is with IBM T.J. Watson Research Center and currently manager of the Software Tools and Techniques group. Dr. Yu has published more than 450 papers in refereed journals and conferences. He holds or has applied for more than 250 US patents. Dr. Yu is a Fellow of the ACM and the IEEE. He has received several IBM honors including two IBM Outstanding Innovation Awards, an Outstanding Technical Achievement Award, two Research Division Awards and the 85th plateau of Invention Achievement Awards. He received a Research Contributions Award from IEEE International Conference on Data Mining in 2003 and also an IEEE Region 1 Award for “promoting and perpetuating numerous new electrical engineering concepts” in 1999. Dr. Yu is an IBM Master Inventor.