Controller Area Network (CAN) schedulability analysis: Refuted,revisited and revised

Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times of CAN messages could be calculated and hence guarantees provided that message response times would not exceed their deadlines. This seminal research has been cited in over 200 subsequent papers and transferred to industry in the form of commercial CAN schedulability analysis tools. These tools have been used by a large number of major automotive manufacturers in the design of in-vehicle networks for a wide range of cars, millions of which have been manufactured during the last decade. This paper shows that the original schedulability analysis given for CAN messages is flawed. It may provide guarantees for messages that will in fact miss their deadlines in the worst-case. This paper provides revised analysis resolving the problems with the original approach. Further, it highlights that the priority assignment policy, previously claimed to be optimal for CAN, is not in fact optimal and cites a method of obtaining an optimal priority ordering that is applicable to CAN. The paper discusses the possible impact on commercial CAN systems designed and developed using flawed schedulability analysis and makes recommendations for the revision of CAN schedulability analysis tools. Robert I. Davis received a DPhil in Computer Science from the University of York in 1995. Since then he has founded three start-up companies, all of which have succeeded in transferring real-time systems research into commercial product. At Northern Real-Time Technologies Ltd. (1995–1997) he was responsible for development of the Volcano CAN software library. At LiveDevices Ltd. (1997–2001) he was responsible for development of the Real-Time Architect suite of products, including an OSEK RTOS and schedulability analysis tools. In 2002, Robert returned to the University of York, and in 2004 he was involved in setting up a spin out company, Rapita Systems Ltd., aimed at transferring worst-case execution time analysis technology into industry. Robert is a member of the Real-Time Systems Research Group at the University of York, and a director of Rapita Systems Ltd. His research interests include scheduling algorithms and schedulability analysis for real-time systems. Alan Burns is head of the Real-Time Systems Research Group at the University of York. His research interests cover a number of aspects of real-time systems including the assessment of languages for use in the real-time domain, distributed operating systems, the formal specification of scheduling algorithms and implementation strategies, and the design of dependable user interfaces to real-time applications. He has authored/co-authored over 370 papers and 10 books, with a large proportion of them concentrating on real-time systems and the Ada programming language. Professor Burns has been actively involved in the creation of the Ravenscar Profile, a subset of Ada”s tasking model, designed to enable the analysis of real-time programs and their timing properties. Reinder J. Bril received a B.Sc. and an M.Sc. (both with honours) from the University of Twente, and a Ph.D. from the Technische Universiteit Eindhoven, the Netherlands. He started his professional career in January 1984 at the Delft University of Technology. From May 1985 until August 2004, he was with Philips, and worked in both Philips Research as well as Philips’ Business Units. He worked on various topics, including fault tolerance, formal specifications, software architecture analysis, and dynamic resource management, and in different application domains, e.g. high-volume electronics consumer products and (low volume) professional systems. In September 2004, he made a transfer back to the academic world, to the System Architecture and Networking (SAN) group of the Mathematics and Computer Science department of the Technische Universiteit Eindhoven. His main research interests are currently in the area of reservation-based resource management for networked embedded systems with real-time constraints. Johan J. Lukkien has been head of the System Architecture and Networking Research group at Eindhoven University of Technology since 2002. He received an M.Sc. and a Ph.D. from Groningen University in the Netherlands. In 1991, he joined Eindhoven University, after two years leave at the California Institute of Technology. His research interests include the design and performance analysis of parallel and distributed systems. Until 2000 he was involved in large-scale simulations in physics and chemistry. Since 2000, his research focus has shifted to the application domain of networked resource-constrained embedded systems. Contributions of the SAN group are in the area of component-based middleware for resource-constrained devices, distributed co-ordination, Quality of Service in networked systems and schedulability analysis in real-time systems.     

Reliable broadcasts and communication models: tradeoffs and lower bounds

Reliable Broadcast is a mechanism by which a processor in a distributed system disseminates a value to all other processors in the presence of both communication and processor failures. Protocols to achieve Reliable Broadcast are at the heart of most fault-tolerant applications. We characterize the execution time of Reliable Broadcast protocols as a function of the communication model. This model includes familiar communication structures such as fully-connected point-to-point graphs, linear chains, rings, broadcast networks (such as Ethernet) and buses. We derive a parameterized protocol that implements Reliable Broadcast for any member within this class. We obtain lower bound results that show the optimality of our protocols. The lower bound results identify a time complexity gap between systems where processors may only fail to send messages, and systems where processors may fail both to send and to receive messages. The tradeoffs that our results reveal between performance, resiliency and network cost offer many new alternatives previously not considered in designing fault-tolerant systems. Özalp Babaoglu is Associate Professor in the Department of Computer Science at Cornell University, Ithaca, New York. His research interests include distributed systems, fault tolerance, performance evaluation and modeling. He received a BS in electrical engineering from George Washington University, Washington, D.C. in 1976. From the University of California, Berkeley, he received a MS in 1977 and a PhD in 1981, both in computer science. While at Berkeley, he designed and implemented the virtual memory extensions to VAX Unix that came to be known as 3. Obsd. Pat Stephenson is a Doctoral Candidate in the Computer Science Department at Cornell University, Ithaca, New York. His research interests include distributed systems and fault tolerance. In 1983, he received a B.A. (Mod.) in computer science from Trinity College, Dublin, Ireland. He received his MS in computer science from Cornell in 1986. He is currently working on new tradeoffs in the design of fault-tolerant algorithms. Rogério Drummond is Assistant Professor in the Computer Science Department at the Universidade Estadual de Campinas (UNICAMP), São Paulo, Brazil. His interests include distributed computing, fault tolerance and operating systems. He received a BS and a MS in computer science from the Universidade Estadual de Campinas in 1978 and 1980, respectively. In 1986 he received a PhD in computer science from Cornell University. He is currently working on integrated environments for the development of software and hardware.Partial support for this work was provided by the National Science Foundation under Grants DCR-86-01864 and MCS-82-10356 and AT&T under a Foundation GrantSupported partially by the Defense Advanced Research Projects Agency (DoD) under ARPA order 5378, Contract MDA 903-85-C-0124, and partially by an IBM graduate fellowship. The views, opinions and findings contained in this report are solely those of the authors and should not be construed as an official Department of Defense position, policy, or decisionSupported partially by the CAPES and CNPq agencies of the Ministry of Education of Brazil     

Analysis of window-constrained execution time systems

Feasibility tests for hard real-time systems provide information about the schedulability of the task set. However, this information is a yes or a no answer, that is, whether the task set achieves the test or not. From the real-time system design point of view, having more information available would be useful. For example, how much the computation time can vary without jeopardising the system feasibility. This work specifically provides methods to determine off-line how much a task can increase its computation time, by maintaining the system feasibility under a dynamic priority scheduling. The extra time can be determined not only in all the task activations, but in n of a window of m invocations. This is what we call a window-constrained execution time system. The results presented in this work can be used in all kinds of real-time systems: fault tolerance management, imprecise computation, overrun handling, control applications, etc. Patricia Balbastre is an assistant professor of Computer Engineering. She graduated in Electronic Engineering at the Technical University of Valencia, Spain, in 1998. And the Ph.D. degree in Computer Science at the same university in 2002. Her main research interests include real-time operating systems, dynamic scheduling algorithms and real-time control. Ismael Ripoll received the B.S. degree from the Polytechnic University of Valencia, Spain, in 1992; the Ph.D. degree in Computer Science at the Polytechnic University of Valencia, Spain, in 1996. Currently he is Professor in the DISCA Department of the same University. His research interests include embedded and real-time operating systems. Alfons Crespo is Professor of the Department of Computer Engineering of the Technical University of Valencia. He received the PhD in Computer Science from the Technical University of Valencia, Spain, in 1984. He held the position of Associate professor in 1986 and full Professor in 1991. He leads the group of Industrial Informatics and has been the responsible of several European and Spanish research projects. His main research interest include different aspects of the real-time systems (scheduling, hardware support, scheduling and control integration, …). He has published more than 60 papers in specialised journals and conferences in the area of real-time systems.     

Finite-horizon scheduling of radar dwells with online template construction

Timing constraints for radar tasks are usually specified in terms of the minimum and maximum temporal distance between successive radar dwells. We utilize the idea of feasible intervals for dealing with the temporal distance constraints. In order to increase the freedom that the scheduler can offer a high-level resource manager, we introduce a technique for nesting and interleaving dwells online while accounting for the energy constraint that radar systems need to satisfy. Further, in radar systems, the task set changes frequently and we advocate the use of finite horizon scheduling in order to avoid the pessimism inherent in schedulers that assume a task will execute forever. The combination of feasible intervals and online dwell packing allows modular schedule updates whereby portions of a schedule can be altered without affecting the entire schedule, hence reducing the complexity of the scheduler. Through extensive simulations we validate our claims of providing greater scheduling flexibility without compromising on performance when compared with earlier work based on templates constructed offline. We also evaluate the impact of two parameters in our scheduling approach: the template length (or the extent of dwell nesting and interleaving) and the length of the finite horizon. Sathish Gopalakrishnan is a visting scholar in the Department of Computer Science, University of Illinois at Urbana-Champaign, where he defended his Ph.D. thesis in December 2005. He received an M.S. in Applied Mathematics from the University of Illinois in 2004 and a B.E. in Computer Science and Engineering from the University of Madras in 1999. Sathish’s research interests concern real-time and embedded systems, and the design of large-scale reliable systems. He received the best student paper award for his work on radar dwell scheduling at the Real-Time Systems Symposium 2004. Marco Caccamo graduated in computer engineering from the University of Pisa in 1997 and received the Ph.D. degree in computer engineering from the Scuola Superiore S. Anna in 2002. He is an Assistant Professor of the Department of Computer Science at the University of Illinois. His research interests include real-time operating systems, real-time scheduling and resource management, wireless sensor networks, and quality of service control in next generation digital infrastructures. He is recipient of the NSF CAREER Award (2003). He is a member of ACM and IEEE. Chi-Sheng Shih is currently an assistant professor at the Graduate Institute of Networking and Multimedia and Department of Computer Science and Information Engineering at National Taiwan University since February 2004. He received the B.S. in Engineering Science and M.S. in Computer Science from National Cheng Kung University in 1993 and 1995, respectively. In 2003, he received his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign. His main research interests are embedded systems, hardware/software codesign, real-time systems, and database systems. Specifically, his main research interests focus on real-time operating systems, real-time scheduling theory, embedded software, and software/hardware co-design for system-on-a-chip. Chang-Gun Lee received the B.S., M.S. and Ph.D. degrees in computer engineering from Seoul National University, Korea, in 1991, 1993 and 1998, respectively. He is currently an Assistant Professor in the Department of Electrical Engineering, Ohio State University, Columbus. Previously, he was a Research Scientist in the Department of Computer Science, University of Illinois at Urbana-Champaign from March 2000 to July 2002 and a Research Engineer in the Advanced Telecomm. Research Lab., LG Information & Communications, Ltd. from March 1998 to February 2000. His current research interests include real-time systems, complex embedded systems, QoS management, and wireless ad-hoc networks. Chang-Gun Lee is a member of the IEEE Computer Society. Lui Sha graduated with the Ph.D. degree from Carnegie-Mellon University in 1985. He was a Member and then a Senior Member of Technical Staff at Software Engineering Institute (SEI) from 1986 to 1998. Since Fall 1998, he has been a Professor of Computer Science at the University of Illinois at Urbana Champaign, and a Visiting Scientist of the SEI. He was the Chair of IEEE Real Time Systems Technical Committee from 1999 to 2000, and has served on its Executive Committee since 2001. He was a member of National Academy of Science’s study group on Software Dependability and Certification from 2004 to 2005, and is an IEEE Distinguished Visitor (2005 to 2007). Lui Sha is a Fellow of the IEEE and the ACM.     

Causal memory: definitions,implementation, and programming

Summary The abstraction of a shared memory is of growing importance in distributed computing systems. Traditional memory consistency ensures that all processes agree on a common order of all operations on memory. Unfortunately, providing these guarantees entails access latencies that prevent scaling to large systems. This paper weakens such guarantees by definingcausal memory, an abstraction that ensures that processes in a system agree on the relative ordering of operations that arecausally related. Because causal memory isweakly consistent, it admits more executions, and hence more concurrency, than either atomic or sequentially consistent memories. This paper provides a formal definition of causal memory and gives an implementation for message-passing systems. In addition, it describes a practical class of programs that, if developed for a strongly consistent memory, run correctly with causal memory. Mustaque Ahamad is an Associate Professor in the College of Computing at the Georgia Institute of Technology. He received his M.S. and Ph.D. degrees in Computer Science from the State University of New York at Stony Brook in 1983 and 1985 respectively. His research interests include distributed operating systems, consistency of shared information in large scale distributed systems, and replicated data systems. James E. Burns received the B.S. degree in mathematics from the California Institute of Technology, the M.B.I.S. degree from Georgia State University, and the M.S. and Ph.D. degrees in information and computer science from the Georgia Institute of Technology. He served on the faculty of Computer Science at Indiana University and the College of Computing at the Georgia Institute of Technology before joining Bellcore in 1993. He is currently a Member of Technical Staff in the Network Control Research Department, where he is studying the telephone control network with special interest in behavior when faults occur. He also has research interests in theoretical issues of distributed and parallel computing especially relating to problems of synchronization and fault tolerance.This work was supported in part by the National Science Foundation under grants CCR-8619886, CCR-8909663, CCR-9106627, and CCR-9301454. Parts of this paper appeared in S. Toueg, P.G. Spirakis, and L. Kirousis, editors,Proceedings of the Fifth International Workshop on Distributed Algorithms, volume 579 ofLecture Notes on Computer Science, pages 9–30, Springer-Verlag, October 1991The photograph of Professor J.E. Burns was published in Volume 8, No. 2, 1994 on page 59This author's contributions were made while he was a graduate student at the Georgia Institute of Technology. No photograph and biographical information is available for P.W. Hutto 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 and, in August 1988, he received a Ph.D. in Computer Science, also from Cornell University. On August 20, 1988, Dr. Neiger married Hilary Lombard in Lansing, New York. He is currently a Staff Software Engineer at Intel's Software Technology Lab in Hillsboro, Oregon. Dr. Neiger is a member of the editorial boards of theChicago Journal of Theoretical Computer Science and theJournal of Parallel and Distributed Computing.     

Hiding collaborative recommendation association rules

The concept of Privacy-Preserving has recently been proposed in response to the concerns of preserving personal or sensible information derived from data mining algorithms. For example, through data mining, sensible information such as private information or patterns may be inferred from non-sensible information or unclassified data. There have been two types of privacy concerning data mining. Output privacy tries to hide the mining results by minimally altering the data. Input privacy tries to manipulate the data so that the mining result is not affected or minimally affected. For output privacy in hiding association rules, current approaches require hidden rules or patterns to be given in advance [10, 18–21, 24, 27]. This selection of rules would require data mining process to be executed first. Based on the discovered rules and privacy requirements, hidden rules or patterns are then selected manually. However, for some applications, we are interested in hiding certain constrained classes of association rules such as collaborative recommendation association rules [15, 22]. To hide such rules, the pre-process of finding these hidden rules can be integrated into the hiding process as long as the recommended items are given. In this work, we propose two algorithms, DCIS (Decrease Confidence by Increase Support) and DCDS (Decrease Confidence by Decrease Support), to automatically hiding collaborative recommendation association rules without pre-mining and selection of hidden rules. Examples illustrating the proposed algorithms are given. Numerical simulations are performed to show the various effects of the algorithms. Recommendations of appropriate usage of the proposed algorithms based on the characteristics of databases are reported. Leon Wang received his Ph.D. in Applied Mathematics from State University of New York at Stony Brook in 1984. From 1984 to 1987, he was an assistant professor in mathematics at University of New Haven, Connecticut, USA. From 1987 to 1994, he joined New York Institute of Technology as a research associate in the Electromagnetic Lab and assistant/associate professor in the Department of Computer Science. From 1994 to 2001, he joined I-Shou University in Taiwan as associate professor in the Department of Information Management. In 1996, he was the Director of Computing Center. From 1997 to 2000, he was the Chairman of Department of Information Management. In 2001, he was Professor and director of Library, all in I-Shou University. In 2002, he was Associate Professor and Chairman in Information Management at National University of Kaohsiung, Taiwan. In 2003, he rejoined New York Institute of Technology. Dr.Wang has published 33 journal papers, 102 conference papers, and 5 book chapters, in the areas of data mining, machine learning, expert systems, and fuzzy databases, etc. Dr. Wang is a member of IEEE, Chinese Fuzzy System Association Taiwan, Chinese Computer Association, and Chinese Information Management Association. Ayat Jafari received the Ph.D. degree from City University of New York. He has conducted considerable research in the areas of Computer Communication Networks, Local Area Networks, and Computer Network Security, and published many technical articles. His interests and expertise are in the area of Computer Networks, Signal Processing, and Digital Communications. He is currently the Chairman of the Computer Science and Electrical Engineering Department of New York Institute of Technology. Tzung-Pei Hong received his B.S. degree in chemical engineering from National Taiwan University in 1985, and his Ph.D. degree in computer science and information engineering from National Chiao-Tung University in 1992. He was a faculty at the Department of Computer Science in Chung-Hua Polytechnic Institute from 1992 to 1994, and at the Department of Information Management in I-Shou University from 1994 to 2001. He was in charge of the whole computerization and library planning for National University of Kaohsiung in Preparation from 1997 to 2000, and served as the first director of the library and computer center in National University of Kaohsiung from 2000 to 2001 and as the Dean of Academic Affairs from 2003 to 2006. He is currently a professor at the Department of Electrical Engineering and at the Department of Computer Science and Information Engineering. His current research interests include machine learning, data mining, soft computing, management information systems, and www applications. Springer     

Applying language modeling to session identification from database trace logs

A database session is a sequence of requests presented to the database system by a user or an application to achieve a certain task. Session identification is an important step in discovering useful patterns from database trace logs. The discovered patterns can be used to improve the performance of database systems by prefetching predicted queries, rewriting the current query or conducting effective cache replacement.In this paper, we present an application of a new session identification method based on statistical language modeling to database trace logs. Several problems of the language modeling based method are revealed in the application, which include how to select values for the parameters of the language model, how to evaluate the accuracy of the session identification result and how to learn a language model without well-labeled training data. All of these issues are important in the successful application of the language modeling based method for session identification. We propose solutions to these open issues. In particular, new methods for determining an entropy threshold and the order of the language model are proposed. New performance measures are presented to better evaluate the accuracy of the identified sessions. Furthermore, three types of learning methods, namely, learning from labeled data, learning from semi-labeled data and learning from unlabeled data, are introduced to learn language models from different types of training data. Finally, we report experimental results that show the effectiveness of the language model based method for identifying sessions from the trace logs of an OLTP database application and the TPC-C Benchmark. Xiangji Huang joined York University as an Assistant Professor in July 2003 and then became a tenured Associate Professor in May 2006. Previously, he was a Post Doctoral Fellow at the School of Computer Science, University of Waterloo, Canada. He did his Ph.D. in Information Science at City University in London, England, with Professor Stephen E. Robertson. Before he went into his Ph.D. program, he worked as a lecturer for 4 years at Wuhan University. He also worked in the financial industry in Canada doing E-business, where he was awarded a CIO Achievement Award, for three and half years. He has published more than 50 refereed papers in journals, book chapter and conference proceedings. His Master (M.Eng.) and Bachelor (B.Eng.) degrees were in Computer Organization & Architecture and Computer Engineering, respectively. His research interests include information retrieval, data mining, natural language processing, bioinformatics and computational linguistics. Qingsong Yao is a Ph.D. student in the Department of Computer Science and Engineering at York University, Toronto, Canada. His research interests include database management systems and query optimization, data mining, information retrieval, natural language processing and computational linguistics. He earned his Master's degree in Computer Science from Institute of Software, Chinese Academy of Science in 1999 and Bachelor's degree in Computer Science from Tsinghua University. Aijun An is an associate professor in the Department of Computer Science and Engineering at York University, Toronto, Canada. She received her Bachelor's and Master's degrees in Computer Science from Xidian University in China. She received her PhD degree in Computer Science from the University of Regina in Canada in 1997. She worked at the University of Waterloo as a postdoctoral fellow from 1997 to 1999 and as a research assistant professor from 1999 to 2001. She joined York University in 2001. She has published more than 60 papers in refereed journals and conference proceedings. Her research interests include data mining, machine learning, and information retrieval.     

A Prolog simulator for deterministic P systems with active membranes

In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in each step of the evolution as literals of an appropriate language of first order logic. We provide a Prolog program to simulate, the evolution of these P systems and present some auxiliary tools to simulate the evolution of a P system with active membranes using 2-division which solves the SAT problem following the techniques presented in Reference.¹⁰ Andrés Cordón-Franco: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Mathematical Logic, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical (software implementation) point of view. Miguel A. Gutiérrez-Naranjo: He is an assistant professor in the Computer Science and Artificial Intelligence Department at University of Sevilla, Spain. He is also a member of the Research Group on Natural Computing of the University of Seville. His research interest includes Machine Learning, Logic Programming and Membrane Computing, both from a theoretical and a practical point of view. Mario J. Pérez-Jiménez, Ph.D.: He is professor of Department of Computer Science and Artificial Intelligence at University of Seville, where he is the head of the Group of Research on Natural Computing, He has published 8 books of Mathematics and Computation, and more than 90 scientific articles in prestigious scientific journals. He is member of European Molecular Computing Consortium. Fernando Sancho-Caparrini: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Complex Systems, DNA Computing, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical point of view.     

Fast and simple distributed consensus

Summary The problem of fault-tolerant agreement is fundamental to distributed computing. When agreement is to be reached in spite of arbitrary behavior by faulty processors, this problem is calledDistributed Consensus. By requiring that the number of faulty processors be , wheren is the number of processors in the system, we are able to derive two new protocols forDistributed Consensus. Both are simple and use messages that are only one bit in length, and both provide forearly stopping: the fewer failures there are, the fewer rounds of communication are required. One protocol is optimal with respect to the number of rounds of communication required, and the other is asymptotically optimal with respect to the total number of message bits exchanged. James E. Burns received the B.S. degree in mathematics from the California Institute of Technology, the M.B.I.S. degree from Georgia State University, and the M.S. and Ph.D. degrees in information and computer science from the Georgia Institute of Technology. He served on the faculty of Computer Science at Indiana University and the College of Computing at the Georgia Institute of Technology before joining Bellcore in 1993. He is currently a Member of Technical Staff in the Network Control Research Department, where he is studying the telephone control network with special interest in behavior when faults occur. He also has research interests in theoretical issues of distributed and parallel computing, especially relating to problems of synchronization and fault tolerance. 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 Proidence, 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 and, in August 1988, he received a Ph.D. in Computer Science, also from Cornell University. On August 20, 1988, Dr. Neiger married Hilary Lombard in Lansing, New York. Since August 1988, he has been an Assistant Professor in the College of Computing (formely School of Information and Computer Science) at the Georgia Institute of Technology in Atlanta, Georgia. Dr. Neiger is a member of the editorial board of theChicago Journal of Theoretical Computer Science and theJournal of Parallel and Distributed Computing.This author was supported in part by the National Science Foundation under grants CCR-8909663, CCR-9106627, and CCR-9301454.     

Resource access control for dynamic priority distributed real-time systems

Many of today’s complex computer applications are being modeled and constructed using the principles inherent to real-time distributed object systems. In response to this demand, the Object Management Group’s (OMG) Real-Time Special Interest Group (RT SIG) has worked to extend the Common Object Request Broker Architecture (CORBA) standard to include real-time specifications. This group’s most recent efforts focus on the requirements of dynamic distributed real-time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that meet the requirements of dynamic distributed real-time systems as specified by Dynamic Scheduling Real-Time CORBA 2.0 (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. These protocols are based on (i) distributed resource preclaiming that allocates resources in the message-based distributed system for deadlock prevention, (ii) distributed priority inheritance that bounds local and remote priority inversion, and (iii) distributed preemption ceilings that delimit the priority inversion time further. Chen Zhang is an Assistant Professor of Computer Information Systems at Bryant University. He received his M.S. and Ph.D. in Computer Science from the University of Alabama in 2000 and 2002, a B.S. from Tsinghua University, Beijing, China. Dr. Zhang’s primary research interests fall into the areas of distributed systems and telecommunications. He is a member of ACM, IEEE and DSI. David Cordes is a Professor of Computer Science at the University of Alabama; he has also served as Department Head since 1997. He received his Ph.D. in Computer Science from Louisiana State University in 1988, an M.S. in Computer Science from Purdue University in 1984, and a B.S. in Computer Science from the University of Arkansas in 1982. Dr. Cordes’s primary research interests fall into the areas of software engineering and systems. He is a member of ACM and a Senior Member of IEEE.     

Modeling out-of-order processors for WCET analysis

Estimating the Worst Case Execution Time (WCET) of a program on a given processor is important for the schedulability analysis of real-time systems. WCET analysis techniques typically model the timing effects of micro-architectural features in modern processors (such as pipeline, cache, branch prediction) to obtain safe and tight estimates. In this paper, we model out-of-order superscalar processor pipelines for WCET analysis. The analysis is, in general, difficult even for a basic block (a sequence of instructions with single-entry and single-exit points) if some of the instructions have variable latencies. This is because the WCET of a basic block on out-of-order pipelines cannot be obtained by assuming maximum latencies of the individual instructions. Our timing estimation technique for a basic block proceeds by a fixed-point analysis of the time intervals at which the instructions enter/leave a pipeline stage. To extend our estimation to whole programs, we use Integer Linear Programming (ILP) to combine the timing estimates for basic blocks. Timing effects of instruction cache and branch prediction are also modeled within our pipeline analysis framework. This forms a combined timing analysis framework that captures out-of-order pipeline, cache, branch prediction as well as the mutual interaction among these micro-architectural features. The accuracy of our analysis is demonstrated via tight estimates obtained for several benchmarks. Preliminary version of parts of this paper has previously been published as Li et al. (2004). Abhik Roychoudhury received his B.E. in Computer Engineering from Jadavpur University (India) in 1995 and his M.S. / Ph.D. degrees (both in Computer Science) from the State University of New York at Stony Brook in 1997 and 2000 respectively. Since 2001 he has been an Assistant Professor at National University of Singapore. His research interests are in models and methods for reliable development of embedded software and systems, with specific focus on software validation, analysis and comprehension. Xianfeng Li is a postdoctoral researcher in the Department of Computer Science and Technology at Peking University, China. He received his Ph.D. from National University of Singapore in 2005. His research interests include real-time systems, modeling and evaluation of computer architecture, and System-on-Chips. Tulika Mitra is an Assistant Professor in School of Computing at National University of Singapore from January 2001. She received her PhD in Computer Science from SUNY at Stony Brook in December 2000. Tulika received M.E in Computer Science and Automation from Indian Institute of Science in 1997 and her B.E. in Computer Engineering from Jadavpur University, India in 1995. Her current research focuses on design and analysis of embedded and real-time systems.     

Behavioural notions for elementary net systems

We study the relationships between a number of behavioural notions that have arisen in the theory of distributed computing. In order to sharpen the under-standing of these relationships we apply the chosen behavioural notions to a basic net-theoretic model of distributed systems called elementary net systems. The behavioural notions that are considered here are trace languages, non-sequential processes, unfoldings and event structures. The relationships between these notions are brought out in the process of establishing that for each elementary net system, the trace language representation of its behaviour agrees in a strong way with the event structure representation of its behaviour. M. Nielsen received a Master of Science degree in mathematics and computer science in 1973, and a Ph.D. degree in computer science in 1976 both from Aarhus University, Denmark. He has held academic positions at Department of Computer Science, Aarhus University, Denmark since 1976, and was visiting researcher at Computer Science Department, University of Edinburgh, U.K., 1977–79, and Computer Laboratory, Cambridge University, U.K., 1986. His research interest is in the theory of distributed computing. Grzegorz Rozenberg received a master of engineering degree from the Department of Electronics (section computers) of the Technical University of Warsaw in 1964 and a Ph.D. in mathematics from the Institute of Mathematics of the Polish Academy of Science in 1968. He has held acdeemic positions at the Institute of Mathematics of the Polish Academy of Science, the Department of Mathematics of Utrecht University, the Department of Computer Science at SUNY at Buffalo, and the Department of Mathematics of the University of Antwerp. He is currently Professor at the Department of Computer Science of Leiden University and Adjoint Professor at the Department of Computer Science of the University of Colorado at Boulder. His research interests include formal languages and automata theory, theory of graph transformations, and theory of concurrent systems. He is currently President of the European Association for Theoretical Computer Science (EATCS). P.S. Thiagarajan received the Bachelor of Technology degree from the Indian Institute of Technology, Madras, India in 1970. He was awarded the Ph.D. degree by Rice University, Houston Texas, U.S.A, in 1973. He has been a Research Associate at the Massachusetts Institute of Technology, Cambridge a Staff Scientist at the Geosellschaft für Mathematik und Datenverarbeitung, St. Augustin, a Lektor at Århus University, Århus and an Associate Professor at the Institute of Mathematical Sciences, Madras. He is currently a Professor at the School of Mathematics, SPIC Science Foundation, Madras. He research intest is in the theory of distributed computing.     

Temporal disjunctive logic programming

In this paper we introduce the logic programming languageDisjunctive Chronolog which combines the programming paradigms of temporal and disjunctive logic programming. Disjunctive Chronolog is capable of expressing dynamic behaviour as well as uncertainty, two notions that are very common in a variety of real systems. We present the minimal temporal model semantics and the fixpoint semantics for the new programming language and demonstrate their equivalence. We also show how proof procedures developed for disjunctive logic programs can be easily extended to apply to Disjunctive Chronolog programs. Manolis Gergatsoulis, Ph.D.: He received his B.Sc. in Physics in 1983, the M.Sc. and the Ph.D. degrees in Computer Science in 1986 and 1995 respectively all from the University of Athens, Greece. Since 1996 he is a Research Associate in the Institute of Informatics and Telecommunications, NCSR ‘Demokritos’, Athens. His research interests include logic and temporal programming, program transformations and synthesis, as well as theory of programming languages. Panagiotis Rondogiannis, Ph.D.: He received his B.Sc. from the Department of Computer Engineering and Informatics, University of Patras, Greece, in 1989, and his M.Sc. and Ph.D. from the Department of Computer Science, University of Victoria, Canada, in 1991 and 1994 respectively. From 1995 to 1996 he served in the Greek army. From 1996 to 1997 he was a visiting professor in the Department of Computer Science, University of Ioannina, Greece, and since 1997 he is a Lecturer in the same Department. In January 2000 he was elected Assistant Professor in the Department of Informatics at the University of Athens. His research interests include functional, logic and temporal programming, as well as theory of programming languages. Themis Panayiotopoulos, Ph.D.: He received his Diploma on Electrical Engineering from the Department of Electrical Engineering, National Technical Univesity of Athens, in 1984, and his Ph.D. on Artificial Intelligence from the above mentioned department in 1989. From 1991 to 1994 he was a visiting professor at the Department of Mathematics, University of the Aegean, Samos, Greece and a Research Associate at the Institute of Informatics and Telecommunications of “Democritos” National Research Center. Since 1995 he is an Assistant Prof. at the Department of Computer Science, University of Piraeus. His research interests include temporal programming, logic programming, expert systems and intelligent agent architectures.     

Global Control of Robotic Highway Safety Markers: A Real-time Solution

This paper presents the design and implementation of a real-time solution for the global control of robotic highway safety markers. Problems addressed in the system are: (1) poor scalability and predictability as the number of markers increases, (2) jerky movement of markers, and (3) misidentification of safety markers caused by objects in the environment.An extensive analysis of the system and two solutions are offered: a basic solution and an enhanced solution. They are built respectively upon two task models: the periodic task model and the variable rate execution (VRE) task model. The former is characterized by four static parameters: phase, period, worst case execution time and relative deadline. The latter has similar parameters, but the parameter values are allowed to change at arbitrary times.The use of real-time tasks and scheduling techniques solve the first two problems. The third problem is solved using a refined Hough transform algorithm and a horizon scanning window. The approach decreases the time complexity of traditional implementations of the Hough transform with only slightly increased storage requirements.Supported, in part, by grants from the National Science Foundation (CCR-0208619 and CNS-0409382) and the National Academy of Sciences Transportation Research Board-NCHRP IDEA Program (Project #90).Jiazheng Shi received the B.E. and M.E. degrees in electrical engineering from Beijing University of Posts and Telecommunications in 1997 and 2000, respectively. In 2000, he worked with the Global Software Group, Motorola Inc. Currently, he is a Ph.D. candidate in the Computer Science and Engineering Department at the University of Nebraska–Lincoln. His research interests are automated human face recognition, image processing, computer vision, approximate theory, and linear system optimization.Steve Goddard is a J.D. Edwards Associate Professor in the Department of Computer Science & Engineering at the University of Nebraska–Lincoln. He received the B.A. degree in computer science and mathematics from the University of Minnesota (1985). He received the M.S. and Ph.D. degrees in computer science from the University of North Carolina at Chapel Hill (1995, 1998).His research interests are embedded, real-time and distributed systems with emphases in high assurance systems engineering and real-time, rate-based scheduling theory.Anagh Lal received a B.S. degree in Computer Science from the University of Mumbai (Bombay), Mumbai, in 2001. He is currently a graduate research assistant at the University of Nebraska–Lincoln working on a M.S. in Computer Science, and a member of the ConSystLab. His research interests lie in Databases, Constraint Processing and Real Time Systems. Anagh will be graduating soon and is looking for positions at research institutions.Jason Dumpert received a B.S. degree in electrical engineering from the University of Nebraska–Lincoln in 2001. He received a M.S. degree in electrical engineering from the University of Nebraska-Lincoln in 2004. He is currently a graduate research assistant at the University of Nebraska-Lincoln working on a Ph.D. in biomedical engineering. His research interests include mobile robotics and surgical robotics.Shane M. Farritor is an Associate Professor in the University of Nebraska–Lincolns Department of Mechanical Engineering. His research interests include space robotics, surgical robotics, biomedical sensors, and robotics for highway safety. He holds courtesy appointments in both the Department of Surgery and the Department of Orthopaedic Surgery at the University of Nebraska Medical Center, Omaha. He serves of both the AIAA Space Robotics and Automation technical committee and ASME Dynamic Systems and Control Robotics Panel. He received M.S. and Ph.D. degrees from M.I.T.     

Improving WCET by applying worst-case path optimizations

It is advantageous to perform compiler optimizations that attempt to lower the worst-case execution time (WCET) of an embedded application since tasks with lower WCETs are easier to schedule and more likely to meet their deadlines. Compiler writers in recent years have used profile information to detect the frequently executed paths in a program and there has been considerable effort to develop compiler optimizations to improve these paths in order to reduce the average-case execution time (ACET). In this paper, we describe an approach to reduce the WCET by adapting and applying optimizations designed for frequent paths to the worst-case (WC) paths in an application. Instead of profiling to find the frequent paths, our WCET path optimization uses feedback from a timing analyzer to detect the WC paths in a function. Since these path-based optimizations may increase code size, the subsequent effects on the WCET due to these optimizations are measured to ensure that the worst-case path optimizations actually improve the WCET before committing to a code size increase. We evaluate these WC path optimizations and present results showing the decrease in WCET versus the increase in code size. A preliminary version of this paper entitled “Improving WCET by optimizing worst-case paths” appeared in the 2005 Real-Time and Embedded Technology and Applications Symposium. Wankang Zhao received his PhD in Computer Science from Florida State University in 2005. He was an associate professor in Nanjin University of Post and Telecommunications. He is currently working for Datamaxx Corporation. William Kreahling received his PhD in Computer Science from Florida State University in 2005. He is currently an assistant professor in the Math and Computer Science department at Western Carolina University. His research interests include compilers, computer architecture and parallel computing. David Whalley received his PhD in CS from the University of Virginia in 1990. He is currently the E.P. Miles professor and chair of the Computer Science department at Florida State University. His research interests include low-level compiler optimizations, tools for supporting the development and maintenance of compilers, program performance evaluation tools, predicting execution time, computer architecture, and embedded systems. Some of the techniques that he developed for new compiler optimizations and diagnostic tools are currently being applied in industrial and academic compilers. His research is currently supported by the National Science Foundation. More information about his background and research can be found on his home page, http://www.cs.fsu.edu/∼whalley. Dr. Whalley is a member of the IEEE Computer Society and the Association for Computing Machinery. Chris Healy earned a PhD in computer science from Florida State University in 1999, and is currently an associate professor of computer science at Furman University. His research interests include static and parametric timing analysis, real-time and embedded systems, compilers and computer architecture. He is committed to research experiences for undergraduate students, and his work has been supported by funding from the National Science Foundation. He is a member of ACM and the IEEE Computer Society. Frank Mueller is an Associate Professor in Computer Science and a member of the Centers for Embedded Systems Research (CESR) and High Performance Simulations (CHiPS) at North Carolina State University. Previously, he held positions at Lawrence Livermore National Laboratory and Humboldt University Berlin, Germany. He received his Ph.D. from Florida State University in 1994. He has published papers in the areas of embedded and real-time systems, compilers and parallel and distributed systems. He is a founding member of the ACM SIGBED board and the steering committee chair of the ACM SIGPLAN LCTES conference. He is a member of the ACM, ACM SIGPLAN, ACM SIGBED and the IEEE Computer Society. He is a recipient of an NSF Career Award.     

Approximation algorithm for periodic real-time tasks with workload-dependent running-time functions

This paper addresses the problem of resource allocation for distributed real-time periodic tasks, operating in environments that undergo unpredictable changes and that defy the specification of meaningful worst-case execution times. These tasks are supplied by input data originating from various environmental workload sources. Rather than using worst-case execution times (WCETs) to describe the CPU usage of the tasks, we assume here that execution profiles are given to describe the running time of the tasks in terms of the size of the input data of each workload source. The objective of resource allocation is to produce an initial allocation that is robust against fluctuations in the environmental parameters. We try to maximize the input size (workload) that can be handled by the system, and hence to delay possible (costly) reallocations as long as possible. We present an approximation algorithm based on first-fit and binary search that we call FFBS. As we show here, the first-fit algorithm produces solutions that are often close to optimal. In particular, we show analytically that FFBS is guaranteed to produce a solution that is at least 41% of optimal, asymptotically, under certain reasonable restrictions on the running times of tasks in the system. Moreover, we show that if at most 12% of the system utilization is consumed by input independent tasks (e.g., constant time tasks), then FFBS is guaranteed to produce a solution that is at least 33% of optimal, asymptotically. Moreover, we present simulations to compare FFBS approximation algorithm with a set of standard (local search) heuristics such as hill-climbing, simulated annealing, and random search. The results suggest that FFBS, in combination with other local improvement strategies, may be a reasonable approach for resource allocation in dynamic real-time systems. David Juedes is a tenured associate professor and assistant chair for computer science in the School of Electrical Engineering and Computer Science at Ohio University. Dr. Juedes received his Ph.D. in Computer Science from Iowa State University in 1994, and his main research interests are algorithm design and analysis, the theory of computation, algorithms for real-time systems, and bioinformatics. Dr. Juedes has published numerous conference and journal papers and has acted as a referee for IEEE Transactions on Computers, Algorithmica, SIAM Journal on Computing, Theoretical Computer Science, Information and Computation, Information Processing Letters, and other conferences and journals. Dazhang Gu is a software architect and researcher at Pegasus Technologies (NeuCo), Inc. He received his Ph.D. in Electrical Engineering and Computer Science from Ohio University in 2005. His main research interests are real-time systems, distributed systems, and resource optimization. He has published conference and journal papers on these subjects and has refereed for the Journal of Real-Time Systems, IEEE Transactions on Computers, and IEEE Transactions on Parallel and Distributed Systems among others. He also served as a session chair and publications chair for several conferences. Frank Drews is an Assistant Professor of Electical Engineering and Computer Science at Ohio Unversity. Dr. Drews received his Ph.D. in Computer Science from the Clausthal Unversity of Technolgy in Germany in 2002. His main research interests are resource management for operating systems and real-time systems, and bioinformatics. Dr. Drews has numerous publications in conferences and journals and has served as a reviewer for IEEE Transactions on Computers, the Journal of Systems and Software, and other conferences and Journals. He was Publication Chair for the OCCBIO’06 conference, Guest Editor of a Special Issue of the Journal of Systems and Software on “Dynamic Resource Management for Distributed Real-Time Systems”, organizer of special tracks at the IEEE IPDPS WPDRTS workshops in 2005 and 2006. Klaus Ecker received his Ph.D. in Theoretical Physics from the University of Graz, Austria, and his Dr. habil. in Computer Science from the University of Bonn. Since 1978 he is professor in the Department of Computer Science at the Clausthal University of Technology, Germany, and since 2005 he is visiting professor at the Ohio University. His research interests are parallel processing and theory of scheduling, especially in real time systems, and bioinformatics. Prof. Ecker published widely in the above mentioned areas in well reputed journals and proceedings of international conferences as well. He is also the author of two monographs on scheduling theory. Since 1981 he is organizing annually international workshops on parallel processing. He is associate editor of Real Time Systems, and member of the German Gesellschaft fuer Informatik (GI) and of the Association for Computing Machinery (ACM). Lonnie R. Welch received a Ph.D. in Computer and Information Science from the Ohio State University. Currently, he is the Stuckey Professor of Electrical Engineering and Computer Science at Ohio University. Dr. Welch performs research in the areas of real-time systems, distributed computing and bioinformatics. His research has been sponsored by the Defense Advanced Research Projects Agency, the Navy, NASA, the National Science Foundation and the Army. Dr. Welch has twenty years of research experience in the area of high performance computing. In his graduate work at Ohio State University, he developed a high performance 3-D graphics rendering algorithm, and he invented a parallel virtual machine for object-oriented software. For the past 15 years his research has focused on middleware and optimization algorithms for high performance computing. His research has produced three successive generations of adaptive resource management (RM) middleware for high performance real-time systems. The project has resulted in two patents and more than 150 publications. Professor Welch also collaborates on diabetes research with faculty at Edison Biotechnology Institute and on genomics research with faculty in the Department of Environmental and Plant Biology at Ohio University. Dr. Welch is a member of the editorial boards of IEEE Transactions on Computers, The Journal of Scalable Computing: Practice and Experience, and The International Journal of Computers and Applications. He is also the founder of the International Workshop on Parallel and Distributed Real-time Systems and of the Ohio Collaborative Conference on Bioinformatics. Silke Schomann graduated in 2003 with a M.Sc. in Computer Science from Clausthal University Of Technology, where she has been working as a scientific assistant since then. She is currently working on her Ph.D. thesis in computer science at the same university.     

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.     

Distributed optimistic concurrency control with reduced rollback

Concurrency control algorithms have traditionally been based on locking and timestamp ordering mechanisms. Recently optimistic schemes have been proposed. In this paper a distributed, multi-version, optimistic concurrency control scheme is described which is particularly advantageous in a query-dominant environment. The drawbacks of the original optimistic concurrency control scheme, namely that inconsistent views may be seen by transactions (potentially causing unpredictable behavior) and that read-only transactions must be validated and may be rolled back, have been eliminated in the proposed algorithm. Read-only transactions execute in a completely asynchronous fashion and are therefore processed with very little overhead. Furthermore, the probability that read-write transactions are rolled back has been reduced by generalizing the validation algorithm. The effects of global transactions on local transaction processing are minimized. The algorithm is also free from dedlock and cascading rollback problems. Divyakant Agrawal is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Burroughs Limited, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include design of algorithms for concurrent systems, optimistic protocols and distributed systems. Arthur Bernstein is a Professor of Computer Science at the State University of New York at Stony Brook. His research is concerned with the design and verification of algorithms involving asynchronous activity and with languages for expressing such algorithms. Pankaj Gupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received M.S. degree in Electrical Engineering from SUNY at Stony Brook in 1982 and M.S. degree in Computer Science from SUNY at Stony Brook in 1985. His research interests include distributed systems, concurrency control, and databases. Soumitra Sengupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Consultancy Services, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include distributed algorithms, logic databases and concurrency control.This work was supported by the National Science Foundation under grant, DCR-8502161 and the Air Force Office of Scientific Research under grant AFOSR 810197     

Linear logic for deductive databases

This paper deals with deductive databases in linear logic. The semantics of queries, views, constraints, and (view) updates are defineddeclaratively in linear logic. In constrast to classical logic, we can formalise non-shared view, transition constraints, and (view) updates easily. Various proof search strategies are presented along with an algorithm for query evaluation from a bottom-up direction. An additional advantage is that the associated meaning of a given relation can be defined in terms of the validity of a legal update in a given relation. We also defined formally the update principles and showed the correctness of the update translation algorithms. In this approach, we provide virtual view updates along with real view updates, and view DELETIONs are special cases of view REPLACEMENTs. This permits three transactional view update operations (INSERTION, DELETION, REPLACEMENT) in comparison to only (INSERTION, DELETION) in most existing systems. Dong-Tsan Lee, Ph.D.: He is a computer scientist in the Department of Computer Science at University of Western Australia, Perth, Western Australia, Australia. He received the B.S. and M.S. degrees from the Department of Computer Science at National Chiao-Tung University, Taiwan, in 1983 and 1985, respectively, and earned the Ph.D. degree from the Department of Computer Science at University of Western Australia. His research interests include database and artificial intelligence, linear logic, and real-time software engineering. Chin-Ping Tsang, Ph.D.: He is currently an associate professor in the Department of Computer Science at University of Western Australia, Perth, Western Australia, Australia. He received the Ph.D. degree from the University of Western Australia. He was the head of the Department of Computer Science at the University of Western Australia from 1994 to 1997. His research interests include artificial intelligence, non-classicial logic and neural nets.