To: (Members of the IEEE-CS TC-RTS mailing list) Bcc: IEEE-RTTC-mailing-list@cs.bu.edu From: Bestavros@cs.bu.edu (Azer Bestavros, TC-RTS maintainer) Reply-To: IEEE-RTTC@cs.bu.edu (E-mail address for Newsletter posts) Return-Path: IEEE-RTTC-request@cs.bu.edu (E-mail address for service requests) Subject: IEEE-CS TC-RTS Newsletter for Tue Oct 11, 1994 _______________________________________________________________________________ __ _ __ ___ ___ __ __ I E E E Technical Committee |\ | |_ | | (_' | |_ | | |_ |_) C S on Real-Time Systems | \| |__ |/\| ,_) |__ |__ | | |__ | \ _______________________________________________________________________________ Table of Contents Line ----------------- ---- 1. best@cs.bu.edu (Azer Bestavros) (27 lines) Real-time Computing: A critical enabling technology................ 3 2. krithi@iitm.iitm.ernet.in (Krithi Ramamritham) (875 lines) RTSS'94 abstracts.................................................. 30 Session 1: SCHEDULING AND RESOURCE ALLOCATION I.................... 33 SESSION 2: DATABASES AND RESOURCE MANAGEMENT....................... 106 SESSION 3: COMMUNICATIONS I........................................ 172 SESSION 4: COMPILERS............................................... 265 SESSION 5: FORMAL METHODS.......................................... 382 SESSION 6: EXPERIMENTAL SYSTEMS AND APPLICATIONS................... 452 SESSION 7: TOOLS................................................... 502 SESSION 8: SCHEDULING AND RESOURCE ALLOCATION II................... 601 SESSION 9: COMMUNICATIONS II....................................... 677 SESSION 11: OPERATING SYSTEMS AND COMMUNICATIONS................... 824 3. Frank Mueller (58 lines) Dissertation on cache predictability avail. via ftp................ 905 4. Mike Jones (96 lines) CFP: HOT TOPICS IN OPERATING SYSTEMS.............................. 963 5. howe@research.att.com (Doug Howe) (146 lines) LICS'95 Call for Papers............................................ 1059 6. "Kang G. Shin" (153 lines) Call for papers: IPDS'95........................................... 1205 7. Walk@Pine.Ece.Utexas.Edu (129 lines) RCS-4 Call for Papers.............................................. 1358 8. rich@cs.UMD.EDU (Richard Gerber) (239 lines) CALL FOR PAPERS: CONCUR '95........................................ 1486 CFP: ACM SIGPLAN Languages, Compilers & Tools for Real-Time Syste.. 1614 9. best@cs.bu.edu (Azer Bestavros) (168 lines) CFP: JOINT WORKSHOP ON PARALLEL AND DISTRIBUTED REAL-TIME SYSTEMS.. 1726 ------------------------------------------------------------------------------ <<<<<<<<<<<<<<<<<<* START OF THE IEEE-CS TC-RTS NEWSLETTER *>>>>>>>>>>>>>>>>>> ------------------------------------------------------------------------------ Message 1; Postmarked Wed Oct 3 10:12:12 1994 From: best@cs.bu.edu (Azer Bestavros) Subject: Real-time Computing: A critical enabling technology A PostScript document entitled "Real-time Computing: A critical enabling technology" co-authored by: Jack Stankovic Kang Shin Herman Kopetz Krithi Ramamritham Lui Sha Doug Locke Jane Liu Al Mok Susan Davidson Insup Lee Jay Strosnider is now available via FTP (or WWW) from the IEEE-RTS archives at URL: cs-ftp://IEEE-RTTS/public/rtfunding.ps --Azer ------------------------------------------------------------------------------ Message 2; Postmarked Wed Oct 5 10:20:25 1994 From: krithi@iitm.iitm.ernet.in (Krithi Ramamritham) Subject: RTSS'94 abstracts Subject: Session 1: SCHEDULING AND RESOURCE ALLOCATION I Efficient Aperiodic Service under Earliest Deadline Scheduling Marco Spuri and Giorgio C. Buttazzo Scuola Superiore S.Anna via Carducci, 40 - 56100 Pisa - Italy spuri@pegasus.sssup.it, giorgio@sssup1.sssup.it In this paper we present four new on-line algorithms for servicing soft aperiodic requests in real-time systems, where a set of hard periodic tasks is scheduled using the Earliest Deadline First (EDF) algorithm. All the proposed solutions can achieve full processor utilization and enhance aperiodic responsiveness, still guaranteeing the execution of the periodic tasks. Operation of the algorithms, performance, schedulability analysis, and implementation complexity are discussed and compared with classical alternative solutions, such as background and polling service. Extensive simulations show that algorithms with contained run-time overhead present nearly optimal responsiveness. A valuable contribution of this work is to provide the real--time system designer with a wide range of practical solutions which allow to balance efficiency against implementation complexity. -------------------------------------------------------------------- Mechanisms for Enhancing the Flexibility and Utility of Hard Real-Time Systems N. C. Audsley, R. I. Davis and A. Burns. Real-Time Systems Research Group, Dept. of Computer Science, University of York, UK. Adaptive and dynamic behaviour is seen as one of the key characteristics of next generation hard real-time systems. Whilst fixed priority pre-emptive scheduling is rapidly becoming a de facto standard in real-time systems engineering, it remains inflexible in its purest form. One method of increasing flexibility is via the incorporation of optional components into processes with hard deadlines. Such components are not guaranteed off-line, but may be accepted at run-time if sufficient spare capacity becomes available. This paper describes new mechanisms which are required to schedule effectively optional components: mechanisms which enable spare capacity to be detected early and on-line guarantees to be given. -------------------------------------------------------------------- Algorithms for Scheduling Hard Aperiodic Tasks in Fixed-Priority Systems using Slack Stealing Sandra R. Thuel AT&T Bell Laboratories, Holmdel, NJ 07733 John P. Lehoczky Department of Statistics Carnegie Mellon University, Pittsburgh, PA 15213 This paper discusses the problem of jointly scheduling hard deadline periodic tasks and hard deadline aperiodic tasks using fixed priority methods. The approach is based on the slack stealing algorithm developed by the authors, and it assumes that the periodic deadlines must all be met. The paper develops a hard aperiodic acceptance test algorithm for guaranteeing tasks at any priority level, and it corrects an error in the original guarantee algorithm presented in RTSS93. It is shown that there is no optimal priority assignment for hard aperiodic tasks, but guidelines are given for choosing a good priority assignment. -------------------------------------------------------------------- Subject: SESSION 2: DATABASES AND RESOURCE MANAGEMENT Timeliness via Speculation for Real-Time Databases Azer Bestavros and Spyridon Braoudakis Department of Computer Science Boston University Boston, MA 02215 Various concurrency control algorithms differ in the time when conflicts are detected, and in the way they are resolved. In that respect, the Pessimistic and Optimistic Concurrency Control (PCC and OCC) alternatives represent two extremes. PCC locking protocols detect conflicts as soon as they occur and resolve them using blocking. OCC protocols detect conflicts at transaction commit time and resolve them using rollbacks (restarts). For real-time databases, blockages and rollbacks are hazards that increase the likelihood of transactions missing their deadlines. We propose a Speculative Concurrency Control (SCC) technique that minimizes the impact of blockages and rollbacks. SCC relies on the use of added system resources to speculate on potential serialization orders and to ensure that if such serialization orders materialize, the hazards of blockages and roll-backs are minimized. We present a number of SCC-based algorithms that differ in the level of speculation they introduce, and the amount of system resources (mainly memory) they require. We show the performance gains (in terms of number of satisfied timing constraints) to be expected when a representative SCC algorithm (SCC-2S) is adopted. -------------------------------------------------------------------- Resource Management for Continuous Multimedia Database Applications Jiandong Huang Honeywell Technology Center 3660 Technology Drive Minneapolis, MN 55418 huang@htc.honeywell.com Ding-Zhu Du Department of Computer Science University of Minnesota Minneapolis, MN 55455 dzd@cs.umn.edu The uniqueness of continuous multimedia database applications lies in the fact that they require system support for steady flow of media access data. In this paper, we address the problem of system resource management for such applications. We introduce a session-based scheduling paradigm that, unlike traditional task scheduling, enables scheduling of all processing entities (threads, I/O processes, and buffers) across multiple system resources for guarantee of steady media flow. Under this paradigm, we develop an approach to on-line generation of session resource requirements based on resource allocation tradeoffs. Further, we develop a multidimensional "bin-packing" approach to allocation and scheduling of multiple resources for concurrent sessions. The goal is to minimize resource overheads and maximize the number of concurrent sessions while meeting session timing constraints and resource capacity constraints. ---------------------------------------------------------------- Subject: SESSION 3: COMMUNICATIONS I Scaling and Performance of a Priority Packet Queue for Real-Time Applications Dan Picker and Ronald D. Fellman (University of California, San Diego) E-mail: rfellman@ucsd.edu Real-time multiprocessor applications are typically characterized by hard deadlines which severely constrain interprocessor communications. Contention for communication resources and the use of first-in-first-out (FIFO) buffering can introduce priority inversion, resulting in missed deadlines. This paper investigates the scaling and performance of a novel 1.2um CMOS Priority Packet Queue (PPQ) design. Its unique segmented architecture effectively exploits the packetized nature of traffic within most real-time networks and achieves 96% the speed of a high-speed packet FIFO. The PPQ can either perform priority inheritance or overwrite lower priority packets during queue overflow, and robustly handles asynchronous read and write clocks of widely disparate frequencies. Comparison results show that the PPQ offers over twice the speed of the conventional design, and promises even greater relative speed improvements for larger designs. --------------------------------------------------------------- A Priority Forwarding Router Chip for Real-Time Interconnection Networks Kenji TODA, Kenji NISHIDA, Eiichi TAKAHASHI, and Yoshinori YAMAGUCHI Electrotechnical Laboratory 1-1-4 Umezono, Tsukuba 305, Japan (toda@etl.go.jp) The design and performance of a priority forwarding router chip are presented. The chip has 4 input and 4 output ports, employs clock-synchronized packet switching, and facilitates 32-bit priority arbitration by means of a priority forwarding scheme that prevents priority inversion and enables accurate priority control within a network. Packets are of fixed size, each having three 38-bit segments. Each input port has an 8-packet priority queue that enables virtual cut-through routing and pipelined-simultaneous-output to at most three different output ports. The chip has two 25-ns pipeline stages and its data transmission rate is 190 MByte/s per port. Clock level simulation shows that the chip can attain high throughput: 9 GByte/s and 34 GByte/s at 64-node and 256-node omega networks with random communication, and excellent real-time performance: very small laxities are required for in-time-delivery of all input packets where the packets exhibit a degree of deadline distribution. -------------------------------------------------------------------- Multiple Route Real-Time Channels in Packet-Switched Networks Kai Chiu Kwan Parameswaran Ramanathan Department of Electrical and Computer Engineering University of Wisconsin-Madison Madison, WI 53706--1691 parmesh@ece.wisc.edu, (608) 263-0557 A real-time channel is a communication mechanism commonly used to guarantee timely delivery of messages between two nodes of a distributed system. It is established at the request of an application task. In the request, the task specifies its worst-case traffic pattern and the required timing constraints. The system accepts the request only if it can guarantee the requested timing constraints without jeopardizing the guarantees provided to the established channels. The main objective of the scheme proposed in this paper is to increase the fraction of channel establishment requests accepted by the system. The proposed scheme increases the fraction of accepted requests by exploiting the existence of multiple routes between two nodes of a distributed system. In particular, unlike existing schemes, it carefully partitions a message and sends the message partitions along different routes to guarantee their timely delivery. In partitioning the message, it also ensures that the overhead of re-sequencing the partitions sent along different routes is minimal. The end result is a better channel establishment procedure for guaranteeing sequenced, timely delivery of messages in a real-time application. ------------------------------------------------------------------------- Subject: SESSION 4: COMPILERS Busy-Idle Profiles and Compact Task Graphs: Compile-time Support for Interleaved and Overlapped Scheduling of Real-Time Tasks Rajiv Gupta Madalene Spezialetti University of Pittsburgh Lehigh University gupta@cs.pitt.edu mspezial@csee.lehigh.edu A new task graph representation, namely the compact task graph (CTG), is developed to aid in the scheduling of a set of communicating periodic real-time tasks. This representation exposes the potential for parallelism across tasks as well as the idle times that may be encountered within a task. Therefore using a CTG a real-time scheduler can generate schedules that are able to meet deadlines by interleaving the execution of tasks on a single processor and/or overlapping the execution of tasks on multiple processors. The construction of a CTG is based upon the busy-idle execution profiles for the tasks generated by the compiler. The profiles are computed assuming that sufficient resources are available for parallel execution of all tasks. Thus, they expose all opporunities for overlapped and interleaved execution. The compiler analyzes the profiles to identify useful opportunities for interleaving and expresses them in the CTG without explicitly partitioning the tasks. The CTG is powerful because it expresses schedules that are not expressed by existing approaches for constructing task graphs. Schedules can be generated efficiently since a CTG's construction does not require the splitting of tasks. We also demonstrate the usefulness of our techniques by developing an approach for non-intrusive monitoring of real-time tasks. ------------------------------------------------------------------------- An Accurate Worst Case Timing Analysis Technique for RISC Processors Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-Do Rhee Sang Lyul Min, Heonshik Shin, Kunsoo Park, Chong Sang Kim Dept. of Computer Engineering Seoul National University Seoul 151-742, Korea Chang Yun Park Dept. of Computer Engineering Chung-Ang University Seoul 156-756, Korea An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, this paper proposes extensions of the original timing schema where the timing information associated with each program construct is a simple time-bound. We associate with each program construct what we call a WCTA (Worst Case Timing Abstraction), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. This paper also reports on preliminary results of WCET analyses for a pipelined processor. Our results show that up to 50 % tighter WCET bounds can be obtained by using the revised timing schema. ---------------------------------------------------------------- Compiler Transformations For Speculative Execution in a Real-Time System Mohamed F. Younis, Real-Time Computing Laboratory, Department of Computer and Information Science New Jersey Institute of Technology, Newark, New Jersey 07102 USA younis@cis.njit.edu Thomas J. Marlowe Department of Mathematics and Computer Science Seton Hall University, South Orange, NJ 07079 USA marlowe@earth.njit.edu and Alexander D. Stoyenko Real-Time Computing Laboratory, Department of Computer and Information Science New Jersey Institute of Technology, Newark, New Jersey 07102 USA alex@vienna.njit.edu Deterministic worst-case execution to satisfy hard-real-time constraints, and speculative execution with rollback to improve average-case throughput, appear to lie on opposite ends of a spectrum of performance requirements and strategies. Nonetheless, we show there are situations in which speculative execution can provably improve the performance of a hard-real-time system, either by improving average performance while not affecting the worst-case, or by actually decreasing worst-case execution time. We also show how related strategies for partial or total precomputation can lead to improved performance. Finally, we discuss possible compiler transformations to detect chances of profitable speculative execution. ---------------------------------------------------------------- Subject: SESSION 5: FORMAL METHODS The Generalized Railroad Crossing: A Case Study in Formal Verification of Real-Time Systems Constance Heitmeyer Code 5546 Naval Research Laboratory Washington, DC 20375 Nancy Lynch Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 heitmeyer@itd.nrl.navy.mil A new solution to the Generalized Railroad Crossing problem, based on timed automata, invariants and simulation mappings, is presented and evaluated. The solution shows formally the correspondence between four system descriptions: an axiomatic specification, an operational specification, a discrete system implementation, and a system implementation that works with a continuous gate model. ---------------------------------------------------------------- Modeling and Analysis of Real-Time Ada Tasking Programs James C. Corbett Department of Information and Computer Science University of Hawaii at Manoa corbett@hawaii.edu We propose a model for real-time Ada tasking programs that naturally represents such features as processor sharing, priority preemption, and process suspension. We describe a semi-decision procedure for proving properties of the model that uses linear programming to determine the feasibility of paths explored during a state-space search of the program. We demonstrate the feasibility of this procedure by applying a prototype analyzer to several examples. ---------------------------------------------------------------- Response-Time Bounds of Rule-Based Programs under Rule Priority Structure Rwo-Hsi Wang, Aloysius K. Mok Department of Computer Sciences University of Texas at Austin Austin, TX 78712-1188 rhwang@cs.utexas.edu, mok@cs.utexas.edu A key index of the performance of a rule-based program used in real-time monitoring and control is its response time, defined by the maximum number of rule firings before a fixed point of the program is reached from a start state. Previous work in computing the response-time bounds for rule-based programs assumes that if two rules are enabled, then either one of them may be scheduled for firing. This assumption may be too conservative in the case programmers choose to impose a priority structure on the set of rules. In this paper, we discuss how to get tighter bounds by taking rule-priority information into account. We show that the rule-suppression relation we previously introduced can be extended to incorporate rule-priority information. A bound-derivation algorithm for programs whose potential-trigger relations satisfy an acyclicity condition is presented, followed by its correctness proof and an analysis example. ---------------------------------------------------------------- Subject: SESSION 6: EXPERIMENTAL SYSTEMS AND APPLICATIONS A Solution to an Automotive Control System Benchmark H. Kopetz - Technical University of Vienna, Austria The Society of Automotive Engineers (SAE) has recently published a set of requirements and a control benchmark to be able to compare the effectiveness of new protocol proposals for safety critical automotive systems. This paper presents a solution to this benchmark problem that is based on the Time Triggered Protocol (TTP). TTP integrates all services required for the implementation of fault-tolerant hard real-time systems, while trying to minimize the bandwidth requirements. ---------------------------------------------------------------- Applying RMA to improve a high-speed, real time data acquisition system David del Val and Angel Vina Departamento de Ingenieria Informatica Universidad Autonoma de Madrid Unlike other real-time systems, data acquisition applications spend most of their time performing suynchronous and asynchronous I/O operations. This fact, that affects tasks' ability to meet deadlines, can be modelled with some extensions to the classic rate monotonic schedulability test. In this paper we address this issue by investigating a case study for the application of rate monotonic analysis to data acquisition applications. We describe a technique for modelling tasks that perform asynchronous I/O at the end of their executing period; and we also show the logistic and technical problems that can arise when applying the rate monotonic analysis at different stages during the development process of an application. We illustrate our ideas with a real-time data acquisition system that we have developed, characterized by a very heterogeneous arquitecture whose technological components have been pushed to the limits of their performance and capacity. ---------------------------------------------------------------- ARINC 659 Scheduling: Problem Definition T. Carpenter, K. Driscoll, K. Hoyme, and J. Carciofini (Honeywell) abstract not received ----------------------------------------------------------------- Subject: SESSION 7: TOOLS Bounding Worst-Case Instruction Cache Performance Robert Arnold, Frank Mueller, David Whalley Computer Science Department Florida State University Tallahassee, FL 32306-4019 whalley@cs.fsu.edu Marion Harmon Computer and Information Systems Department Florida A&M University Tallahassee, FL 32307-3101 harmon@vm.cc.famu.edu The use of caches poses a difficult tradeoff for architects of real-time systems. While caches provide significant performance advantages, they have also been viewed as inherently unpredictable since the behavior of a cache reference depends upon the history of the previous references. The use of caches will only be suitable for real-time systems if a reasonably tight bound on the performance of programs using cache memory can be predicted. This paper describes an approach for bounding the worst-case instruction cache performance of large code segments. First, a new method called Static Cache Simulation is used to analyze a program's control flow to statically categorize the caching behavior of each instruction. A timing analyzer, which uses the categorization information, then estimates the worst-case instruction cache performance for each loop and function in the program. ---------------------------------------------------------------- Deterministic Upperbounds of the Worst-Case Execution Times of Cached Programs Jyh-Charn Liu, Hung-Ju Lee Department of Computer Science Texas A&M University College Station, TX 77843--3112 E-mail: [jcliu,hjlee]@cs.tamu.edu This paper proposes analysis techniques to derive the worst case execution time (WCET) of cached programs. We focus the analysis on one single program which runs on a direct-mapped cache, so that no external interferences could occur to the program execution. It is known that the analysis complexity of the worst case execution time of (uncached) programs is NP-complete. For nested loop program structures, we derive some sufficient conditions in deriving the deterministic bounds of the worst case execution time of different loop constructs in a cached program. The sufficient conditions allow us to make a flexible trade-off between tightness of the WCET bounds and the run time of the bound search routine. xoIndex Terms: direct-mapped cache, hard real-time, worst case execution time ---------------------------------------------------------------- Guaranteeing End-to-End Timing Constraints by Calibrating Intermediate Processes R. Gerber, S. Hong and M. Saksena Department of Computer Science University of Maryland College Park, MD 20742 USA {rich,sshong,manas}@cs.umd.edu This paper presents a comprehensive design methodology for guaranteeing end-to-end requirements of real-time systems. Applications are structured as a set of process components connected by asynchronous channels, in which the endpoints are the system's external inputs and outputs. Timing constraints are then postulated between these inputs and outputs; they express properties such as end-to-end propagation delay, temporal input-sampling correlation, and allowable separation times between updated output values. The automated design method works as follows: First the end-to-end requirements are transformed into a set of intermediate rate constraints on the tasks, and new tasks are created to correlate related inputs. The intermediate constraints are then solved by an optimization algorithm, whose objective is to minimize CPU utilization. If the algorithm fails, a restructuring tool attempts to eliminate bottlenecks by transforming the application, which is then re-submitted into the assignment algorithm. The final result is a schedulable set of fully periodic tasks, which collaboratively maintain the end-to-end constraints. ---------------------------------------------------------------- Subject: SESSION 8: SCHEDULING AND RESOURCE ALLOCATION II Scheduling Adaptive Tasks in Real-Time Systems Kai Wang Tein--Hsiang Lin Radar System Group Department of Electrical and Computer Engineering Hughes Aircraft Company State University of New York at Buffalo Los Angeles, CA 90009 Buffalo, New York 14260 In a real-time system, a repetitive task can be scheduled as a periodic task or an adaptive task to meet its timing requirement. For a periodic task, the deadline is always one period interval from the ready time and the current deadline will become the ready time for the next task instance. Whereas for an adaptive task, the deadline is set to one period interval from the completion of the previous task instance and the ready time can be set anywhere before the deadline. Periodic task scheduling has be researched extensively in the past. In this paper, we will study the scheduling of adaptive tasks. This study is motivated by the study of resource allocation for a radar system with adaptive sensors, where the resources would be used more efficiently if the sensor tasks are scheduled as adaptive tasks. ---------------------------------------------------------------- Dynamic End-to-end Guarantees in Distributed Real Time Systems Marco Di Natale John A. Stankovic Department of Computer Science Department of Computer Science University of Massachusetts University of Massachusetts Amherst, Mass. 01003 Amherst, Mass. 01003 Scuola Superiore S.Anna Pisa, Italy 56100 Many distributed real-time applications are structured as a set of processes communicating through synchronous channels. Unfortunately, process interactions and especially synchronous communications make the problem of predictably scheduling the tasks more complex. In distributed systems the local and remote tasks as well as the messages over the network must be properly scheduled and synchronized to meet the deadlines of the application. To find such a schedule is not an easy task, in fact, this problem is NP complete even if we have complete knowledge of the future arrival times for all the processes in the system. The objective of this paper is to develop a scheme that allows for the dynamic scheduling and guaranteeing of distributed processes communicating via synchronous primitives. For efficiency reasons, a combination of off-line and on-line scheduling is performed. Precedence and communication constraints are converted off-line into pseudo-deadlines for each task, enabling efficient on-line processing. The on-line scheduling operates in parallel at the sites involved in the distributed computation, further obtaining efficiency. The overall end-to-end scheduling includes the joint and coordinated scheduling of tasks and messages in a reflective memory distributed architecture. ---------------------------------------------------------------- On-Line Scheduling to Maximize Task Completions Sanjoy Baruah -- The University of Vermont Jayant Haritsa and Nitin Sharma -- Indian Institute of Science (Contact author's electronic-mail address: sanjoy@cs.uvm.edu) The problem of uniprocessor scheduling under conditions of overload is investigated. The system objective is to maximize the number of tasks that complete by their deadlines. For this performance metric we prove that, in general, any on-line algorithm may perform arbitrarily poorly as compared to a clairvoyant scheduler. We identify restricted instances of the general problem for which on-line schedulers can provide a guaranteed level of performance, and present on-line algorithms for these special cases. ---------------------------------------------------------------- Subject: SESSION 9: COMMUNICATIONS II Probabilistic Bounds on Message Delivery for the Totem Single-Ring Protocol L. E. Moser and P. M. Melliar-Smith Department of Electrical and Computer Engineering University of California, Santa Barbara, CA 93106 moser@ece.ucsb.edu, pmms@ece.ucsb.edu For fault-tolerant real-time distributed systems, the probability that a message is not delivered within its real-time deadline must be small enough that it does not adversely affect system reliability. We investigate the delivery of messages for the Totem Protocol, a reliable ordered broadcast protocol that we have developed for fault-tolerant distributed systems with physical broadcasts over a local-area network. The total order on broadcast messages, constructed by the Totem Protocol, supports the maintenance of consistency of replicated information as, for example, in a replicated database. We present a methodology for determining the probability of satisfying bounds on the latency from message origination to ordered delivery in the presence of communication faults. ------------------------------------------------------------------ Real-Time Communication Services in a DQDB Network Rosa L. R. Carmo, Francisco Vasques and Guy Juanole LAAS du CNRS 7, Avenue du Colonel Roche - 31077 Toulouse Cedex FRANCE email: carmo,vasques,juanole@laas.fr This paper addresses the problem of transmitting real-time periodic traffic in a DQDB network. In a DQDB network, connection-oriented isochronous services use the Pre-Arbitrated (PA) access. The standard specifies that isochronous connections must have guaranteed periodic bandwidth but mechanisms to provide it, such as the slot allocation scheme, are not described. We propose a Real-Time Service Provider (RTSP) based on the use of the PA access. The RTSP consists of an off-line centralized scheduling algorithm and an on-line mode change algorithm which allows to take into account load changes. Means are also provided to guarantee a minimum fairness level for the asynchronous traffic. ---------------------------------------------------------------- Analysing Real-Time Communications: Controller Area Network (CAN) K. W. Tindell, H. Hansson A. J. Wellings Department of Computer Systems Department of Computer Science University of Uppsala, Sweden University of York, England ken@docs.uu.se, hansh@docs.uu.se andy@minster.york.ac.uk The increasing use of communication networks in time critical applications presents engineers with fundamental problems with the determination of response times of communicating distributed processes. Although there has been some work on the analysis of communication protocols, most of this is for idealised networks. Experience with single processor scheduling analysis has shown that models which abstract away from implementation details are at best very pessimistic and at worst lead to unschedulable system being deemed schedulable. In this paper, we derive idealised scheduling analysis for the CAN network, and then study two actual interface chips to see how the analysis can be applied. ----------------------------------------------------------------- Computing Quantitative Characteristics of Finite-State Real-Time Systems S. Campos E. Clarke W. Marrero M. Minea campos@cs.cmu.edu emc@cs.cmu.edu marrero@cs.cmu.edu marius@cs.cmu.edu School of Computer Science Carnegie Mellon University H. Hiraishi hiraishi@kyoto-su.ac.jp Dept of Information & Communication Sciences Kyoto Sangyo University This paper presents a general method for computing quantitative information about finite-state real-time systems. We have developed algorithms that compute exact bounds on the delay between two specified events and on the number of occurrences of an event in a given interval. This technique allows us to determine performance measures such as schedulability, response time, and system load. Our algorithms produce more detailed information than traditional methods. This information leads to a better understanding of system behavior, in addition to determining its correctness. The algorithms presented in this paper are efficiently implemented using binary decision diagrams and have been incorporated into the SMV symbolic model checker. Using this method, we have verified a model of an aircraft control system with 10E15 states. The results obtained demonstrate that our method can be successfully applied in the verification of real-time system designs.} ---------------------------------------------------------------- Verifying an Intelligent Structural Control System: A Case Study Wael M. Elseaidy Department of Civil Engineering N.C. State University Raleigh, NC 27695-7908 USA email: wmelseai@eos.ncsu.edu Rance Cleaveland Department of Computer Science N.C. State University Raleigh, NC 27695-8206 USA email: rance@csc.ncsu.edu John W. Baugh Jr. Department of Civil Engineering N.C. State University Raleigh, NC 27695-7908 USA email: jwb@eos.ncsu.edu This paper describes the formal verification of the timing properties of the design of an intelligent structural control system using the Concurrency Workbench, an automatic verification tool for finite-state processes. The high-level design of the system is first given in Modechart, a graphical specification language for real-time systems, and then translated into a temporal process algebra supported by the Workbench. The facilities provided by this tool are then used to analyze the system and ultimately show it correct. ---------------------------------------------------------------- Flexible Real-time SQL Transactions Paul J. Fortier Victor Fay Wolfe J.J.Prichard U. Mass. at Dartmouth U. of Rhode Island PFORTIER@umassd.edu name@cs.uri.edu This paper presents flexible transaction structuring capabilities that allow relaxed ACID properties for better support of real-time transactions. The specification of these flexible transaction structures is demonstrated through proposed extensions to the standard SQL database language. ---------------------------------------------------------------- Subject: SESSION 11: OPERATING SYSTEMS AND COMMUNICATIONS Supporting Real-Time Traffic on Ethernet. Tzi-cker Chiueh, Chitra Venkatramani Dept. of Computer Science SUNY at Stony Brook Stony Brook, NY 11794. email - {chiueh, chitra}@cs.sunysb.edu Ethernet has been the dominant local area network architecture in the last decade, and we believe that it will continue to be so because of its cost-effectiveness and the availability of higher-bandwidth Ethernets. We propose and evaluate a software-based protocol called RETHER (Real-time ETHERnet) that provides real-time performance guarantees to multimedia applications *without* modifying existing Ethernet hardware. RETHER features a hybrid mode of operation to reduce the performance impact on non-real-time network packets, a race-condition-free distributed admission control mechanism, and an efficient token-passing scheme that protects the network against token loss due to node failures. ---------------------------------------------------------------- Modeling DSP Operating Systems for Multimedia Applications Dan I. Katcher, Kevin Katcher and Jay K. Strosnider Department of Electrical and Computer Engineering Carnegie Mellon University strosnider@ece.cmu.edu Real-time scheduling theory attempts to guarantee that a real-time task set will always meet its deadlines. Real-time systems are typically implemented via real-time operating systems (RTOSs). However, there currently exists a wide gap between real-time scheduling theory and the reality of its implementation via RTOSs. Bridging the gap requires effort on two fronts. First, real-time scheduling theory must be extended such that implementation realities may be correctly incorporated. Second, the high level of sophistication required to apply real-time scheduling theory to RTOSs bars practitioners from creating scheduling (timing) models of their operating systems. This paper summarizes recent work on developing an engineering methodology that allows relatively unsophisticated users and developers to accurately model and evaluate RTOSs. Specifically, we recount the experiences of a CMU undergraduate class's experience in modeling and analyzing three commercial Digital Signal Processor (DSP) operating systems. ---------------------------------------------------------------- Emulating Soft Real-Time Scheduling Using Traditional Operating System Schedulers Brad Adelberg EE Dept. Stanford University Hector Garcia-Molina CS Dept. Stanford University Ben Kao CS Dept. Princeton University adelberg@cs.stanford.edu Real-time scheduling algorithms are usually only available in the kernels of real-time operating systems, and not in more general purpose operating systems, like Unix. For some soft real-time problems, a traditional operating system may be the development platform of choice. This paper addresses methods of emulating real-time scheduling algorithms on top of standard time-share schedulers. We examine (through simulations) three strategies for priority assignment within a traditional multi-tasking environment. The results show that the emulation algorithms are comparable in performance to the real-time algorithms and in some instances outperform them. -- ------------------------------------------------------------------------------ Message 3; Postmarked Mon Sep 19 12:56:14 1994 From: Frank Mueller Subject: Dissertation on cache predictability avail. via ftp The following dissertation (related to compilers and real-time systems) is now available via ftp and WWW: "Static Cache Simulation and its Applications" by F. Mueller, Ph.D. Dissertation, Florida State University, Jul 1994 ftp-site: ftp.cs.fsu.edu internet#: 128.186.121.27 directory: /pub/whalley/papers file: mueller_diss94.ps.Z mail-list: mueller@uzu.cs.fsu.edu Subject: subscribe-pthreads WWW: http://www.cs.fsu.edu/~mueller Abstract: ========= This work takes a fresh look at the simulation of cache memories. It introduces the technique of {\em static cache simulation} that statically predicts a large portion of cache references. To efficiently utilize this technique, a method to perform efficient on-the-fly analysis of programs in general is developed and proved correct. This method is combined with static cache simulation for a number of applications. The application of fast instruction cache analysis provides a new framework to evaluate instruction cache memories that outperforms even the fastest techniques published. Static cache simulation is shown to address the issue of predicting cache behavior, contrary to the belief that cache memories introduce unpredictability to real-time systems that cannot be efficiently analyzed. Static cache simulation for instruction caches provides a large degree of predictability for real-time systems. In addition, an architectural modification through bit-encoding is introduced that provides fully predictable caching behavior. Even for regular instruction caches without architectural modifications, tight bounds for the execution time of real-time programs can be derived from the information provided by the static cache simulator. Finally, the debugging of real-time applications can be enhanced by displaying the timing information of the debugged program at breakpoints. The timing information is determined by simulating the instruction cache behavior during program execution and can be used, for example, to detect missed deadlines and locate time-consuming code portions. Overall, the technique of static cache simulation provides a novel approach to analyze cache memories and has been shown to be very efficient for numerous applications. -- Frank Mueller Florida State University E-Mail : mueller@cs.fsu.edu WWW: http://www.cs.fsu.edu/~mueller ------------------------------------------------------------------------------ Message 4; Postmarked Tue Sep 13 19:55:40 1994 From: Mike Jones Subject: CFP: HOT TOPICS IN OPERATING SYSTEMS Call for Participation FIFTH WORKSHOP ON HOT TOPICS IN OPERATING SYSTEMS (HotOS-V) (Formerly: Workshop on Workstation Operating Systems (WWOS)) Sponsored by the IEEE Computer Society's Technical Committee on Operating Systems and Application Environments Orcas Island, Washington, USA May 4-5, 1995 The Fifth Workshop on Hot Topics in Operating Systems will bring together researchers and practitioners in operating systems working in a range of computing environments, including workstations, notebooks, and hand-held computers. The purpose of HotOS-V is to examine controversial issues in operating systems and to provide a forum for discussing ideas and sharing information and experiences. The workshop is designed to encourage full participation of each attendee; both presenters and participants will be active contributors throughout the workshop. We request submissions of position papers that describe ongoing or completed research and development experiences, as well as those that propose new directions, advocate non-traditional approaches, or generate controversy and discussion. This year's workshop will pay special attention to issues relevant to the next generation computing systems, including: - Application-extensible operating systems - Real-time, continuous media, and multimedia - System requirements for virtual reality platforms - OS support for embedded systems - Distributed object frameworks - Mobile and "ubiquitous" computing - Mostly connected/disconnected computing - Wireless networking - Global information access - Global, widely accessible, storage system To assure a productive workshop, attendance will be limited to 60 participants active in the field. Each potential participant should submit eight copies of a 1-5 page position paper. Submissions should be mailed to the program chair. Contact the registration chair for registration information. SUBMISSION DEADLINE: DECEMBER 2, 1994 Notification of acceptance: January 31, 1995 Final position papers due: April 1, 1995 PROGRAM CHAIR: Henry M. Levy Dept. of Computer Science and Engineering, FR-35 University of Washington Seattle, WA 98195 (206) 543-9204 levy@cs.washington.edu GENERAL CHAIR: Michael B. Jones Microsoft Research, Microsoft Corporation One Microsoft Way, Bldg. 9S/1047 Redmond, WA 98052 (206) 936-8846 mbj@microsoft.com FINANCE/REGISTRATION CHAIR: Joseph Boykin GTE Laboratories 40 Sylvan Road Waltham, MA 02254 (617) 466-2803 boykin@gte.com PROGRAM COMMITTEE: Henry Levy (chair) University of Washington Paulo Guedes INESC, Portugal Kevin Jeffay University of North Carolina Paul Leach Microsoft Corporation Kai Li Princeton University Michael Powell Sun Microsystems David Reed Interval Research Corporation Robbert van Renesse Cornell University Current information on HotOS-V is accessible via the URL http://www.research.microsoft.com/research/os/HotOS/. ------------------------------------------------------------------------------ Message 5; Postmarked Tue Sep 20 13:45:12 1994 From: howe@research.att.com (Doug Howe) Subject: LICS'95 Call for Papers [Postscript and Latex versions of this announcement are available through the LICS WWW page at http://www.research.att.com/lics/ and via anonymous ftp from research.att.com, directory /dist/lics.] Tenth Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE June 26-29, 1995 San Diego, California CALL FOR PAPERS The LICS Symposium aims to attract original papers of high quality on theoretical and practical topics in computer science that relate to logic in a broad sense, including algebraic, categorical and topological approaches. Suggested, but not exclusive, topics of interest include: abstract data types, automated deduction, categorical models, concurrency, constraint programming, constructive mathematics, database theory, domain theory, finite model theory, hybrid systems, logics of knowledge, lambda and combinatory calculi, linear logic, logical aspects of computational complexity, logics in artificial intelligence, logic programming, modal and temporal logics, model checking, program logic and semantics, rewriting, logical aspects of symbolic computing, software specification, type systems, verification. DATES: Submission deadline: December 7, 1994 Notification: February 14, 1995 Final papers due: April 5, 1995 Conference: June 26-29, 1995 PAPER SUBMISSION: Send 12 copies of an extended abstract (not a full paper) to the program chair to be received by December 7, 1994. This deadline is firm; late submissions will not be considered. Authors without access to copiers may submit a single copy. Authors will be notified of acceptance or rejection by February 14, 1995. Accepted papers in a specified format for the proceedings will be due April 5, 1995. The first page of the extended abstract should include the title of the paper, names and affiliations of authors, a brief synopsis, and the contact author's name, address, phone number, fax number, and email address, if available. The extended abstract may not exceed 10 typed pages in no less than 11-point font. It must be in English and provide sufficient detail to allow the program committee to assess the merits of the paper. It should begin with a succinct statement of the issues, a summary of the main results, and a brief explanation of their significance and relevance to the conference, all phrased for the non-specialist. References and comparisons with related work should be included. Technical development directed to the specialist should follow. Submissions departing significantly from these guidelines risk rejection. The results must be unpublished and not submitted for publication elsewhere, including the proceedings of other symposia or workshops. All authors of accepted papers will be expected to sign copyright release forms. One author of each accepted paper will be expected to present the paper at the conference. The symposium is sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing in cooperation with the Association for Symbolic Logic, the European Association for Theoretical Computer Science, and the Association for Computing Machinery. The symposium is hosted by the University of California, San Diego. Kleene Award for Best Student Paper: An award of $500, in honor of the late S.C. Kleene, will be given to the best paper, as judged by the program committee, written solely by one or more students. A submission is eligible if all authors are full-time students at the time of submission. This should be indicated in the submission letter. The program committee may decline to make the award or may split it among several papers. LICS GENERAL CHAIR: Moshe Y. Vardi Department of Computer Science Rice University Houston, Texas 77251-1892, USA vardi@cs.rice.edu PROGRAM CHAIR: Dexter Kozen Attn: LICS Computer Science Department Upson Hall Cornell University Ithaca, New York 14853-7501, USA lics95@cs.cornell.edu Phone: (607) 255-9209 Fax: (607) 255-4428 PROGRAM COMMITTEE: Martin Abadi, DEC Leo Bachmair, SUNY Stony Brook Carolyn Brown, Univ. of Sussex Edmund Clarke, CMU E. Allen Emerson, UT Austin Ursula Goelz, Univ. of Hildesheim Thomas Henzinger, Cornell Phokion Kolaitis, UC Santa Cruz Dexter Kozen (chair), Cornell Dale Miller, Univ. of Pennsylvania C.-H. Luke Ong, Oxford and Natl. Univ. Singapore A. P. Sistla, Univ. of Illinois, Chicago Val Tannen, Univ. of Pennsylvania and Univ. of Paris-Sud Jerzy Tiuryn, Univ. of Warsaw CONFERENCE CO-CHAIRS: Samuel R. Buss, Jeffrey B. Remmel Department of Mathematics University of California, San Diego La Jolla, CA 92013-0112, USA sbuss@ucsd.edu, jremmel@ucsd.edu ORGANIZING COMMITTEE: M. Abadi, S. Abramsky, S. Artemov, E. Boerger, A. Borodin, W. Brauer, A. Bundy, S. Buss, E. Clarke, R. Constable, A. Felty, U. Goltz, D. Howe, G. Huet, J.-P. Jouannaud, D. Kapur, C. Kirchner, P. Kolaitis, D. Kozen, T. Leighton, D. Leivant, A.R. Meyer, D. Miller, J. Mitchell, Y. Moschovakis, M. Okada, P. Panangaden, J. Remmel, J. Riecke, S. Ronchi della Rocca, A. Scedrov, D. Scott, J. Tiuryn, M.Y. Vardi (chair) PUBLICITY CO-CHAIRS: Amy Felty and Douglas Howe AT&T Bell Laboratories 600 Mountain Avenue, Murray Hill, NJ 07974, USA felty@research.att.com, howe@research.att.com ------------------------------------------------------------------------------ Message 6; Postmarked Mon Sep 26 17:13:02 1994 From: "Kang G. Shin" Subject: Call for papers: IPDS'95 CALL FOR PAPERS =============== _/ _/_/_/_/ _/_/_/ _/_/_/_/ _/_/ _/_/_/ _/_/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/ _/ _/ _/_/_/_/ _/_/_/ _/_/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/ _/_/_/_/ _/_/_/ _/_/_/ IEEE International Computer Performance and Dependability Symposium =================================================================== April 24-26, 1995 Erlangen, Germany Sponsored by: IEEE Computer Society Technical Committee on Fault-Tolerant Computing IFIP Working Group 7.3 on Performance Evaluation IFIP Working Group 10.4 on Dependable Computing and Fault Tolerance In cooperation with: University of Erlangen-Nurnberg, Germany University of Illinois at Urbana-Champaign, USA Steering Committee: ------------------ J. Abraham, University of Texas, Austin, USA A. Avizienis, University of California, Los Angeles, USA G. Balbo, Politecnico di Milano, Italy P.-J. Courtois, AV-Nuclear, Brussels, Belgium D. Ferrari, University of California, Berkeley, USA J.-C. Laprie, LAAS-CNRS, Toulouse, France E. McCluskey, Stanford University, USA J. Meyer, University of Michigan, Ann Arbor, USA B. Randell, University of Newcastle Upon Tyne, UK A. Reuter, University of Stuttgart, Germany H. Schwartzel, Siemens AG, Munich, Germany K. Sevcik, University of Toronto, Canada D. Siewiorek, Carnegie-Mellon University, Pittsburgh, USA K. Trivedi, Duke University, Durham, USA Co-General Chairs: ----------------- Mario Dal Cin Institute for Computer Sciences, Univ. of Erlangen- Nurnberg, D-91058 Erlangen - Germany E-mail: dalcin@immd3.informatik.uni-erlangen.de Tel.: +(49) 9131 85 7003 Fax: +(49) 9131 85 7239 Ulrich Herzog Institute for Computer Sciences, Univ. of Erlangen- Nurnberg, D-91058 Erlangen - Germany E-mail: herzog@immd7.informatik.uni-erlangen.de Tel.: +(49) 9131 857041 Fax: +(49) 9131 857409 Program Chair: ------------- Ravishankar K. Iyer CRHC - Coordinated Science Laboratory, Univ. of Illinois at Urbana-Champaign, Urbana, IL 61801 - USA E-mail: iyer@crhc.uiuc.edu Tel.: +(1) 217 333 9732 Fax: +(1) 217 244 5686 Program Vice-Chair: ------------------ Martin Reiser IBM, Zurich, Switzerland E-mail: reiser@zurich.ibm.com Finance Chair: Wolfgang Hohl, Univ. of Erlangen-Nurnberg, Germany ------------- Publicity Chair: Jean Arlat, LAAS-CNRS, Toulouse, France --------------- Registration Chair: Hermann Hellwagner, Siemens AG, Munich, Germany ------------------ Local Arrangements Chair: Kurt Freudenthaler, Siemens AG, Erlangen, Germany ------------------------ Publication Chair: William H. Sanders, Univ. of Arizona, USA ----------------- Program Committee: ----------------- J. Arlat, LAAS-CNRS (F) F. Baccelli, INRIA (F) H. Beilner, Dortmund U. (D) A. Bode, TU Munich (D) R. Candlin, Edinburgh U. (UK) G. Chiola, Torino U. (I) L. Dowdy, Vanderbilt U. (USA) R. Geist, Clemson U. (USA) J. Goldberg, SRI (USA) K. Goswami, U. of Illinois (USA) A. Goyal, IBM (USA) G. Haring, U. of Vienna (A) K. Kanoun, LAAS-CNRS (F) T. Kikuno, Osaka U. (J) J. Lala, Draper Labs (USA) S. Lavenberg, AT&T (USA) D. Lenoski, Silicon Graphics (USA) Y. Levendel, AT&T (USA) J. Liu, U. of Illinois (USA) R. Marie, IRISA (F) I. Mitrani, U. of Newcastle (UK) D. Reed, U. of Illinois (USA) A. Reibman, AT&T (USA) D. Rennels, UCLA (USA) W. Sanders, U. of Arizona (USA) R. Schlichting, U. of Arizona (USA) H. Schwetman, U. of Texas (USA) L. Sha, CMU (USA) K. Shin, U. of Michigan (USA) S. Shrivastava, Newcastle U. (UK) M. Singhal, Ohio State U. (USA) A. Smith, UC Berkeley (USA) J. Stankovic, Massachusetts U. (USA) J. Torrellas, U. of Illinois (USA) S. Tripathi, U. of Maryland (USA) Objectives: ---------- Until recently the questions of performance and dependability of computer systems have largely evolved separately. With the advent of high performance computers with massive parallelism and high speed networks the two issues have become closely related. Both design and evaluation methods must consider the relationships between the occurrence of errors/failures and their consequent impact on performance. This symposium is intended to bring together researchers in the two areas with emphasis on integrating theory and practice. Relating analytical techniques to simulations, actual measurements and experiments will be the broad theme of the symposium. Research relating to hardware and software issues in parallel and distributed systems will be emphasized. The topics include: o Analytical Techniques o Simulation o Software Reliability/Performance o Instrumentation/Measurements o Real-Time Issues o Design Tools o Evaluation Tools o Case Studies Important Information for Authors: --------------------------------- Four copies of the papers (not more than 20 pages, double-space including figures) should be submitted to the Program Chair: Prof. Ravishankar K. Iyer E-mail: iyer@crhc.uiuc.edu CRHC - Coordinated Science Laboratory Telephone: +(1) 217 333 9732 University of Illinois FAX: +(1) 217 244 5686 1308 W. Main St. Urbanna IL 61801 - USA ************************************************* * IMPORTANT DATES * * Paper Submission: October 15, 1994 * * Acceptance Notification: December 16, 1994 * * Camera-ready Copies: February 10, 1995 * ************************************************* About Erlangen: -------------- Erlangen has one of the largest computer science departments in Germany. It traditionally had strong research groups in the area of dependability and performance evaluation. It is situated near the medieval city of Nurnberg and the beautiful Franconian Forest. Erlangen is also the location of a large research and development facility of Siemens. ------------------------------------------------------------------------------ Message 7; Postmarked Mon Sep 26 18:23:24 1994 From: Walk@Pine.Ece.Utexas.Edu Subject: RCS-4 Call for Papers CALL FOR PAPERS FOURTH INTERNATIONAL WORKSHOP ON RESPONSIVE COMPUTER SYSTEMS March 29 - 31, 1995 Berlin, Germany Sponsored by: U.S. Office of Naval Research In Cooperation With: INRIA, France IEEE-CS Technical Committee on Fault-Tolerant Computing IEEE-CS Technical Committee on Real-Time Systems OBJECTIVES The disciplines of parallel/distributed computing, fault-tolerant computing and real-time systems still are, to a large extent, evolving separately. As computer users demand timeliness and dependability to be ensured when using arbitrarily complex system architectures, there is an urgent need to integrate theory and practice of real-time systems, fault-tolerant computing and parallel/distributed computing. We call such integrated systems responsive, as they have to respond to internal guiding programs or external inputs in a timely, dependable and predictable manner. Responsive systems raise a significant number of fundamental issues of theoretical and practical relevance. RCS'95 will focus on concepts, methods, algorithms and tools for such systems. RCS'95 will pay particular attention to new results in the areas of algorithmic proofs and formal approaches addressing issues falling in at least two of the three disciplines. Papers that are purely descriptive are discouraged. We view RCS'95 as an opportunity for participants to gain a clear picture of most recent original results in "difficult" research areas. For example, how to express finite upper bounds on response times in the absence of advance knowledge regarding future operational conditions, is the synchronous model appropriate to solve the 10*-9/hour problem, what would be a complete design methodology that permits to formally PROVE that a pair satisfies user requirement specifications in the case of responsive systems? TOPICS Topics of interest in the workshop include: * Formal methods for specification, design and verification of responsive systems * Proofs of logical or/and timing properties * Algorithms and communication protocols for achieving time-dependent task scheduling, concurrency control and fault tolerance in an integrated manner * Language and tool support for responsive systems * Modeling, analysis, performance evaluation * Application to real systems PARTICIPATION Active researchers in the areas of distributed and parallel systems, fault- tolerant computing and real-time systems are invited to participate. To maximize vigorous exchange of ideas, the workshop attendance will be limited. All prospective attendees who wish to submit a paper are invited to send five copies of a full manuscript not exceeding 5000 words to the Program Chairman by 21 October, 1994. Preprints of full papers will be distributed at the workshop. A digest of papers will be published. DEADLINES Paper Submissions: 21 October, 1994 Notification of Acceptance: 20 January, 1995 Camera-ready Copy: 28 February, 1995 ORGANIZERS General Chairman Program Chairman Radu Popescu-Zeletin Gerard Le Lann GMD - FOKUS INRIA - Projet Reflecs Hardenbergplatz 2 B.P. 105 D-10623 Berlin, GERMANY F-78153 Le Chesnay Cedex, FRANCE Phone: + 49 30 254 99 206 Phone: + 33 1 39 63 53 64 Fax: + 49 30 254 99 202 Fax: + 33 1 39 63 53 30 E-mail: E-mail: Zeletin@fokus.berlin.gmd.d400.de Gerard.Le_Lann@inria.fr Local Arrangements: Volker K. Tschammer GMD - FOKUS Hardenbergplatz 2 D-10623 Berlin, GERMANY Phone: +49 30 254 99 226 Fax: +49 30 254 99 202 E-mail: Tschammer@fokus.berlin.gmd.d400.de PROGRAM COMMITTEE F. Cristian, UCSD (USA) D. Hammer, EUT, Eindhoven (Netherlands) G. Hommel, TU, Berlin (Germany) M. Joseph, U. of Warwick (UK) Y. Kakuda, U. of Osaka (Japan) G. Koob, ONR (USA) H. Kopetz, TU, Vienna (Austria) J. C. Laprie, LAAS, Toulouse (France) N. Lynch, MIT (USA) M. Malek, Humboldt U., Berlin (Germany) A. Mok, U. of Texas, Austin (USA) K. Mori, Hitachi (Japan) J. Rushby, SRI (USA) F. Schneider, Cornell, Ithaca (USA) D. Shasha, NYU (USA) J. Sifakis, IRIMAG, Grenoble (France) S. Toueg, Cornell, Ithaca (USA) ****************************************************************************** ------------------------------------------------------------------------------ Message 8; Postmarked Mon Sep 26 17:13:02 1994 Subject: CALL FOR PAPERS: CONCUR '95 From: rich@cs.UMD.EDU (Richard Gerber) CALL FOR PAPERS CONCUR '95 Sixth International Conference on Concurrency Theory Philadelphia, Pennsylvania, USA August 21-24, 1995 The purpose of CONCUR '95 is to bring together researchers, developers, and students in order to advance the science of concurrency theory and promote its application. Submissions are invited in all areas of semantics, logics, and verification techniques for concurrent systems. Potential topics include, but are not limited to, process algebras, Petri nets, true concurrency, shared-memory and message-passing formalisms, operational and denotational models, programming language semantics, concurrent logic and constraint programming, fairness, temporal logics, compositional analysis techniques, and verification tools. Submissions will be evaluated by the Program Committee for inclusion in the proceedings, which will be published by Springer-Verlag. Papers must contain original contributions, be clearly written, and include appropriate reference to and comparison with related work. CONCUR '95 will feature for the first time electronic submission of papers. Uuencoded dvi or postscript (tm) files should be e-mailed to: concur95-submit@cs.sunysb.edu When electronic submission is not possible (due, e.g., to lack of internet access), five (5) hardcopies of the paper should be sent to the postal address given below. Submissions should contain a draft of a full paper of no more than 15 typed pages (with normal font sizes, line spacing, margins, etc.) accompanied by a one-page abstract. The mailing addresses (both postal and electronic), telephone number and fax number (if available) of the author to whom correspondence should be sent should be clearly indicated. IMPORTANT DATES Submission of draft paper: 1 March 1995 Notification of acceptance: 1 May 1995 Final version due: 1 June 1995 SUBMISSION ADDRESSES electronic: concur95-submit@cs.sunysb.edu hardcopy: CONCUR '95 Attn: Scott Smolka Dept. of Computer Science SUNY at Stony Brook Stony Brook, NY 11794-4400 USA telephone: +1 516 632 8453 fax: +1 516 632 8334 PROGRAM COMMITTEE B. Bloom (Cornell University) R. Cleaveland (North Carolina State University) P. Degano (University of Pisa) R. van Glabbeek (Stanford University) R. Gerth (Technical University of Eindhoven) S. Graf (University of Grenoble) J.F. Groote (University of Utrecht) C. Heitmeyer (Naval Research Laboratory) T. Henzinger (Cornell University) L. Jategaonkar Jagadeesan (AT&T Bell Labs) A. Jeffrey (Sussex University) I. Lee, co-chair (University of Pennsylvania) J. Parrow (Swedish Institute of Computer Science) A. Rabinovitch (Tel Aviv University) D. Sangiore (University of Edinburgh) S. Schneider (University of London) A. Skou (University of Aalborg) S. Smolka, co-chair (SUNY Stony Brook) E. Stark (SUNY Stony Brook) B. Thomsen (ECRC) M. Young (Purdue University) CONFERENCE CO-CHAIRS Insup Lee Scott A. Smolka Dept. of Computer and Information Sci. Department of Computer Science University of Pennsylvania SUNY at Stony Brook Philadelphia, PA 19104-6389, USA Stony Brook, NY 11794-4400, USA telephone: +1 215 898 3532 telephone: +1 516 632 8453 fax: +1 215 898 0587 fax: +1 516 632 8334 lee@cis.upenn.edu sas@cs.sunysb.edu PUBLICITY CHAIR TUTORIALS CHAIR Rich Gerber Dale Miller Department of Computer Science Dept. of Computer and Information Sci. University of Maryland University of Pennsylvania College Park, MD 20742, USA Philadelphia, PA 19104-6389, USA telephone: +1 301 405 2710 telephone: +1 215 898 1593 e-mail: rich@cs.umd.edu e-mail: dale@cis.upenn.edu FURTHER INFORMATION Plain text, dvi, and postscript versions of this Call For Papers as well as the latest information on CONCUR '95 can be obtained electronically via: E-MAIL: concur95@cis.upenn.edu FTP: cis.upenn.edu (158.130.12.3) -- pub/concur95 WWW: http://www.cis.upenn.edu/concur95/concur95.html ------- End of Forwarded Message Postmarked Tue Oct 4 21:30:03 1994 From: rich@cs.UMD.EDU (Richard Gerber) Subject: CFP: ACM SIGPLAN Languages, Compilers & Tools for Real-Time Systems CALL FOR PAPERS ACM SIGPLAN Workshop on Languages, Compilers and Tools for Real-Time Systems (In Conjunction with ACM SIGPLAN PLDI/PEPM) La Jolla, California June 21-22, 1995 ACM SIGPLAN LCT-RTS '95 is an interface between two dynamic fields of computer science and engineering: programming languages and real-time systems. The time is right for this workshop: top researchers in these areas are addressing many similar problems, but with slightly different perspectives and technologies. LCT-RTS provides a forum where these researchers can share their results and directions, and where they can potentially form new collaborations based on common interests. MOTIVATION: Until recently real-time systems development was the province of experienced specialists, who were trained to deal both at very high and low levels of abstraction. Programmers were faced with a variety of custom kernels, non-standard languages and vendor-specific device interfaces. System integration inevitably involved a complicated process of taking timing measurements, hand-tuning the code, and then re-measuring. These ad-hoc techniques have not scaled to support modern systems, which often possess multiple, complex, interacting components. There is a growing desire to adopt advanced design strategies, standard kernels, reusable modules, generic languages and the like. Also, the majority of real-time developers is longer drawn from the ranks of embedded controls experts; rather, it is composed of animators, physicists, video producers, musicians, medical technicians, automotive engineers, manufacturing engineers, etc. New software approaches are necessary to support these new systems, and this new generation of real-time programmers. THE WORKSHOP: ACM SIGPLAN LCT-RTS '95 is devoted to investigating software technologies for contemporary real-time systems. This is the second LCT-RTS workshop; last year's meeting showed that there is significant interest in this area. Original submissions are invited in all areas relevant to this theme, including (but not restricted to) the following list of topics: * Programming Languages for Real-Time: Industrial and Research * Design: Requirements, System Specification, Analysis * Exception Handling: Semantics, Policies, Mechanisms * Prototyping Languages * Timing Analysis: Static and Dynamic Approaches * Scheduling Analysis * Realtime on RISC: Caches, Register Windows, Pipelines * Realtime Memory Management and Garbage Collection * Support for Parallelism and Data Placement * Program Transformation and Optimization for Real-Time Performance * Profiling, Measurement and Debugging * System Integration and Testing Of particular interest are case studies, or experimental results based on application-building experiences; for example in interactive graphics, imaging, manufacturing, etc. Papers should report new research, and should not exceed 5000 words (approximately 10 pages typeset 10-point on 16-point spacing, or 15 typewritten double-spaced pages). Short papers are also welcomed, which describe existing implementations, work-in-progress, or new problems and important issues. Short papers should not exceed 3000 words (6 pages). All accepted papers will be presented at the workshop and published in the proceedings. SUBMISSION: Please submit seven (7) copies of papers, to: ACM SIGPLAN LCT-RTS Attn: Richard Gerber Department of Computer Science University of Maryland College Park, MD 20742 USA Papers will be reviewed the program committee for appropriateness of content and presentation. Proceedings will be distributed at the workshop. IMPORTANT DATES Submission of draft paper: 23 January 1995 Notification of acceptance: 22 March 1995 Final version due: 15 May 1995 PROGRAM COMMITTEE Alan Burns (University of York) Richard Gerber, Co-Chair (University of Maryland) Rajiv Gupta (Univ of Pittsburgh) Mary Hall (Caltech) Connie Heitmeyer (Naval Research Lab) Insup Lee (University of Pennsylvania) Al Mok (University of Texas at Austin) Thomas Marlowe, Co-Chair (Seton Hall University, NJIT RTCL) Steve Tjiang (Synopsys Inc.) PROGRAM CO-CHAIRS Richard Gerber Thomas Marlowe Department of Computer Science Department of Mathematics University of Maryland Seton Hall University College Park, MD 20742, USA South Orange NJ 07079, USA telephone: +1 301 405 2710 telephone: +1 201 761 9784 fax: +1 301 405 6707 fax: +1 201 761 9596 rich@cs.umd.edu marlowe@cs.rutgers.edu ------------------------------------------------------------------------------ Message 9; Postmarked Tue Oct 11 17:24:09 1994 From: best@cs.bu.edu (Azer Bestavros) Subject: CFP: JOINT WORKSHOP ON PARALLEL AND DISTRIBUTED REAL-TIME SYSTEMS CALL FOR PAPERS JOINT WORKSHOP ON PARALLEL AND DISTRIBUTED REAL-TIME SYSTEMS (3rd Workshop on Parallel and Distributed Real-Time Systems and 7th International Real-Time Ada Issues Workshop) April 24-26, 1995 Santa Barbara, California Program Co-Chairs: Theodore Baker, Florida State Univ. (for Ada and Ada 9X) Dieter K. Hammer, Eindhoven Univ. of Technology (for Europe and Africa) Yoshiaki Kakuda, Osaka University (for the Pacific Rim) Lonnie R. Welch, New Jersey Inst. of Technology (for the Americas) Program Committee: John Barnes, UK Maarten Boasson, Hollands Signaal, The Netherlands Alan Burns, University of York, U.K. Steve Case, Computing Devices Int., USA Klaus Ecker, Technical University of Clausthal, Germany Loe Feijs, Philips Research, The Netherlands Borko Furht, Florida Atlantic University, USA Anthony Gargaro, Computer Sciences Corporation, USA Michael Gonzalez, Spain John Goodenough, Software Engineering Institute Robert Harrison, Naval Surface Warfare Center, USA Guenter Hommel, Technical University of Berlin, Germany Keith Hopper, New Zealand Norm Howes, Institute for Defense Analyses, USA Mathai Joseph, University of Warwick, U.K. Joerg Kaiser, GMD, Germany Mike Kamrad, Computing Devices Int., USA Jan van Katwijk, Delft University of Technology, The Netherlands Jyh C. Liu, Texas A&M University, USA Jane W. S. Liu, University of Illinois, USA Douglass Locke, Loral Federal Systems Division, USA Michael W. Masters, Naval Surface Warfare Center, USA Mike Rodd, University of Wales, U.K. Kang G. Shin, University of Michigan, USA Behrooz Shirazi, University of Texas, USA Sang Son, University of Virginia, USA John A. Stankovic, University of Massachusetts, USA Robert Steigerwald, U. S. Air Force Academy, USA Alfred Strohmeier, Swiss Fed Inst of Technology, Switzerland Kenji Toda, MITI Electrotechnical Lab., Japan Morikazu Takegaki, Mitsubishi Electric Company, Japan Joyce Tokar, Tartan Laboratories, USA Richard Volz, Texas A&M University, USA Andrew Wellings, University of York Mark Wilson, Naval Surface Warfare Center, USA Tomohiro Yoneda, Tokyo Institute of Technology, Japan Wei Zhao, Texas A&M University, USA Real-time systems frequently employ parallel and distributed computer platforms in order to meet timing constraints and to achieve fault tolerance and availability. In order to come to a usable solution, the issues of concurrency and dependability must be considered simultaneously. However, it is often the case that researchers focus on problems relevant to concurrent processing while overlooking timeliness. Similarly, real-time computing research efforts are often focused on producing techniques that apply only to single processor systems. To address this unfortunate state of affairs, the 3rd Workshop on Parallel and Distributed Real-Time Systems (WPDRTS3) will be held April 24-26, 1995, in conjunction with the The 9th IEEE International Parallel Processing Symposium (IPPS). Furthermore, in an effort to focus on problems of importance to those who are building concurrent real-time systems in Ada, WPDRTS3 will be held jointly with the 7th International Real-Time Ada Issues Workshop. Thus, in addition to considering issues relevant to concurrent real-time systems in general, the workshop will also focus on issues pertinent to concurrent, real-time Ada and Ada 9X. A partial list of topics of interest include: -Architecture, hardware, communication systems and protocols -Operating systems -Hard and soft real-time systems -Fault tolerance, reliability and security -Scheduling, resource allocation, and optimization -Programming languages and compiler techniques -Complex systems engineering and reengineering -Object-based techniques -Design and requirements -Applications (including multimedia, databases, artificial intelligence, command and control, and transportation) -Comparison of Ada/Ada 9X with other languages for real-time programming -Implementation/performance of Ada/Ada 9X real-time and concurrent features and Annexes -Advances in real-time Ada/Ada 9X runtime systems -Using Ada/Ada 9X for real-time concurrent computing To submit a manuscript for presentation at the workshop, send a copy by electronic mail (either in PostScript or ASCII format), or send three copies by surface mail, by Oct. 31, 1994 to the appropriate program co-chair. Manuscripts pertaining to Ada or to Ada 9X should be submitted to T. Baker. All other submissions should be sent to the program chair located in your geographic region. Manuscripts should not exceed 2500 words (about 10 pages). The format of the workshop will be a mixture of paper presentations, panel discussions, and problem-solving discussions. In addition to the workshop proceedings, a special issue of The ISMM International Journal of Mini and Microcomputers is planned, in which selected papers from the workshop will be published. Program Co-Chair (for Ada-related papers): Theodore Baker Florida State University Internet: baker@cs.fsu.edu Program Co-Chair (for Europe and Africa) Dieter K. Hammer Dept. of Mathematics and Computing Science Eindhoven Univ. of Technology P. O. Box 513 NL-5600 MB Eindhoven The Netherlands +31 40 474416 Internet: hammer@win.tue.nl Program Co-Chair (for the Pacific Rim) Yoshiaki Kakuda Dept. of Information and Computer Sciences Faculty of Engineering Science Osaka University 1-3, Machikaneyama-cho, Toyonaka-shi Osaka 560, Japan +81 6 844 1151 ext.4841 Internet: kakuda@ics.es.osaka-u.ac.jp Program Co-Chair (for The Americas) Lonnie R. Welch Dept. of Computer and Information Science New Jersey Institute of Technology University Heights Newark, NJ 07102 (201) 596-5683 Internet: welch@vienna.njit.edu IPPS is sponsored by The IEEE Computer Society Technical Committee on Parallel Processing in cooperation with ACM SIGARCH. The joint workshop on is sponsored by The U.S. Naval Surface Warfare Center, and is held in cooperation with The IEEE Computer Society Technical Committee on Parallel Processing, and with The IEEE Computer Society Technical Committee on Real-Time Systems. Cooperation with ACM SIGAda is also pending. ------------------------------------------------------------------------------ <<<<<<<<<<<<<<<<<<<* END OF THE IEEE-CS TC-RTS NEWSLETTER *>>>>>>>>>>>>>>>>>>> ------------------------------------------------------------------------------ The TC-RTS repository is maintained by Azer Bestavros at Boston University Internet address for anonymous FTP to the TC-RTS repository is: cs.bu.edu Contributions to this forum should be sent via E-mail to: IEEE-RTTC@cs.bu.edu Requests / inquiries should be sent via E-mail to: IEEE-RTTC-request@cs.bu.edu ------------------------------------------------------------------------------