This paper describes the structure, design and implementation of a building/environment data and information system, called BeDIS for short. It is designed to support fine-scale, location-specific services provided by smart devices and mobile applications in large smart buildings. Structured as a fog, it remains responsive when overloaded and degrades gracefully when network connection is disrupted and parts of it damaged. During normal times, it enables hundreds and thousands of people to locate themselves sufficiently accurately and navigate amidst dense crowd and moving objects via their mobile phones. When triggered by a disaster/emergency alert from responsible government agencies or the building safety system, BeDIS functions as a system of micro data servers for delivering location- and situation-specific emergency response instructions to people and decision support data to active smart devices and applications within fractions of a second to seconds.

The building/environment data and information system (BeDIS) described here is a part of infrastructure needed to support location-specific, active emergency preparedness and responses within large buildings. Building/environment data and information (BeDI) based indoor positioning system (BeDIPS) is one of its components. BeDIPS can provide people in large buildings with sufficiently accurate location data. It is scalable, disaster resilient, and easy to configure, deploy, and maintain. BeDIPS works without Internet and serves both smart phones and most legacy Bluetooth devices. The other component of BeDIS is BeDI mist, a virtual repository of data and information on the building, interior layouts, and facilities. The mist uses micro data servers and smart gateways to deliver fine-scale, location-specific decision support data on a timely basis to hundreds and thousands of active devices and mobile applications.

Many disaster warning and response systems can improve their surveillance coverage of the threatened area by supplementing in situ and remote physical sensor data with crowdsourced human sensor data captured and sent by people in the area. This paper presents fusion methods which enable a crowdsourcing enhanced system to use human sensor data and physical sensor data synergistically to improve its sensor coverage and the quality of its decisions. The methods are built on results of classical statistical detection and estimation theory and use value fusion and decision fusion of human sensor data and physical sensor data in a coherent way. They are the building blocks of a central fusion unit in a crowdsourcing support system for disaster surveillance and early warning applications.

This paper presents Robotic Application Resource Management Services (RARMS), a collection of tools for integrating reusable software components of a wide class of robotic applications on Microsoft Windows, a general-purpose, commodity operating system. RARMS includes (1) a resource allocation tool called RAAPT-HV for partitioning the available processors into a specified number of virtual processors, allocating available resources to virtual processors and assigning robotic software components to virtual processors and (2) a robot-class scheduling service (RC SS) which helps independently developed components prioritize relative to each other in a way that is consistent with their timing requirements. These tools aim to provide time-sensitive components with satisfactory responsiveness in an open environment without serious impact on the performance of other components. To demonstrate the effectiveness of RARMS, we adopted for experimentation and evaluation purposes several commonly-used components of delivery robots, including face detection, speech recognition, video streaming and path planning. The results of our experiments showed that these tools can help to achieve satisfactory performance for these software components of robotic applications.

Out-patient medication administration has been identified as the most error-prone procedure in modern healthcare. Under or over doses due to erratic in-takes, drug-drug or drug-food interactions caused by un-reconciled prescriptions and the absence of in-take enforcement and monitoring mechanisms have caused medication errors to become the common cases of all medical errors. Most medication administration errors were made when patients bought different prescribed and over-the-counter medicines from several drug stores and use them at home without little or no guidance. Elderly or chronically ill patients are particularly susceptible to these mistakes. In this paper, we introduce Wedjat, a smart phone application designed to help patients avoiding these mistakes. Wedjat can remind its users to take the correct medicines on time and record the in-take schedules for later review by healthcare professionals. Wedjat has two distinguished features: (1) it can alert the patients about potential drug-drug/drug-food interactions and plan a proper in-take schedule to avoid these interactions; (2) it can revise the in-take schedule automatically when a dose was missed. In both cases, the software always tries to produce the simplest schedule with least number of in-takes. Wedjat is equipped with user friendly interfaces to help its users to recognize the proper medicines and obtain the correct instructions of taking these drugs. It can maintain the medicine in-take records on board, synchronize them with a datanotbase on a host machine or upload them onto a Personal Health Record (PHR) system. A proof-of-concept prototype of Wedjat has been implemented on Window Mobile platform and will be migrated onto Android for Google Phones. This paper introduces the system concept and design principles of Wedjat with emphasis on its medication scheduling algorithms and the modular implementation of mobile computing application.

This paper describes an embedded workflow framework (EMWF) that enables flexible personal and home automation and assistive devices and service and social robots (collectively referred to as SISARL) to be built on workflow architecture The process definition language supported by EMWF is called SISARL-XPDL. It consists of a subset of the WfMC standard XML Process Definition Language (XPDL) 2.0, together with elements that implement common mechanisms for robot behavior coordination. SISARL-XPDL definitions of workflows are first translated into standard XPDL and execution directives and then are parsed either directly into binary workflow scripts for execution or into intermediate scripts in C. EMWF provides workflow engines for Linux and Windows CE platforms. The engines are written in C in order to keep their memory footprint and runtime overhead small. Performance data show that the overheads introduced by the engine and workflow data are tolerable for most SISARL devices.

User-centered assistive and automation devices (UCAAD) must be flexible (i.e., configurable, customizable and adaptive). We are concerned with the interface design so as to design and build flexible UCAAD in an effective manner. We design the component interfaces for UCAAD to describe the essential information for component integration during design time and run-time. We propose to make use of the workflow model to integrate hardware and software components into a complete embedded systems. A unified component interface is required for the workflow-based integration process. In particular, we are concerned with resource management for UCAAD systems. This paper presents our approaches, progress to date and future plans.

This paper describes SISARL simulation environment. The environment is built on Microsoft Windows Workflow Foundation to support the design and development of smart devices and systems that aim to enhance life quality and well being of elderly individuals. To evaluate the usability, design, and implementation of a device, the developer provides as an input for each simulation, an operational view specification of the device and a model of the user (or models of multiple users). The specification describes the operations of the device, intended actions of the user(s) and user-machine interactions in terms activities and workflows. The device and the user are simulated when the specification is executed by the workflow engine. The simulation environment provides extensible libraries of reusable components, including device activities, user activities, and workflow definitions, to ease the efforts in writing operational view specifications of new and modified devices. It also provides a library of user models that can be used to simulate user behaviors, as well as tools for the capture, analysis and display of simulation data. In addition to these components of the simulation environment, the paper also describes ways to use simulation results in the design and development process.

This paper describes a component model and component-based architecture of smart devices and systems that are designed to enhance life quality and well being of elderly individuals. In addition to providing the traditional view of hardware, firmware and software components, the model also provides developers with an operational view. The view enables the developer to specify device-user interactions asexecutable workflows and allows the device operations and user actions to be experimented with and their correctness ascertained throughout the design and development process. The paper also presents a simulation environment for this purpose.

The coming decades will likely see tremendous growth in diversity and use of embedded devices and systems targeted for elderly individuals for many reasons, including that global population ages and technology advances make the devices affordable. Such a device can improve the quality of life of its user and assist the user to live independently. It can also serve as a point-of-care tool for care providers when assistance and care become necessary. As examples, medication dispenser may first find its place in a home as a birthday gift to provide information and reminders as assistance to the user in compliance, but when the need arises, it becomes an essential automation tool for the user to be cared at home. A smart walker may be used initially for the enhancement of the user's dexterity but can adapt to provide the user with stability and mobility as the user ages.

Medication errors harm at least 1.5 million people every year in United States, according to the report issued by Committee on Identifying and Preventing Medication Errors in 2007 [1]. Medication use system consists of many sub-systems including prescription entry systems and drug libraries. Integrating medication sub-systems and automating the medication process enhance medication compliance and prevent medication errors, caused by communication mistakes between care-takers and medical institutes. In this paper, we present the workflow-based integration framework for medication use. In the framework, new sub-systems including medicaiton authoring tools and intelligent medication dispensers are designed to automate the process. To integrate the complex and heterogeneous sub-systems, we develop an integration framework and make use of workflow engines. The integration framework defines how each subsystem describes itself and how the each sub-system triggers succeeding actions. Wrokflow-based approach is used to dispatch the works among the distributed sub-systems and provides the flexibility to the system.

Medication dispensers treated in this paper are designed to help improve compliance by users who live at homes and take medications over long periods of time. The paper first presents an overview of medication specifications that define constraints for dispensers and dispenser components that administer medications as specified. When given a specification and constraints defined by it, the dispenser scheduler checks for consistency and feasibility of constraints and schedules medications to meet the constraints. Several basic algorithms needed for these purposes are described and evaluated.

A smart pantry holds non-perishable household supplies and automates the purchasing and delivery of their replenishments. By relieving its user from the chore of keeping the home stocked of essentials, it provides convenience and peace of mind not only to elderly individuals but also busy people of all ages. This paper describes two alternative smart pantry designs and tradeoffs. Underlying methods and technologies used for their implementation are also described.

We describe here the prescription algebra and its implementation for medication authoring tools. The tools are parts of medication use process, which consists of prescription entry systems, medication authoring tool, medication scheduling specification, medication scheduler, and programmable pill dispenser. A medication authoring tool aids the pharmacists to collect and integrate prescriptions, to verify drug-drug interactions amongst prescriptions one took for the prescribed duration, and to generate the scheduling specifications for pill dispensers. We design a prescription algebra for medication authoring tool to correctly complete its work. We have implemented the platform-independent medication authoring tool using JAVA. The screen snapshot are shown in the paper.

A team of researchers including computer scientists, electrical and control engineers, architects, industrial designers, human factor engineers, and cognitive scientists in the National Chiao Tung University (NCTU), Taiwan, along with their overseas collaborators launched the project Kannon, a multi-disciplinary effort to develop Adaptive Assistive Technologies that can be deployed incrementally into existing private/public spaces and collaborate opportunistically to offer monitoring, assisting, communicating and rejuvenating services to healthy elders. The team combined the state-of-art information, communication and robotic know-how with the activity oriented method for product design and the modular functional approach in modern architecture in order to devise a holistic support for successful aging. This paper presents the philosophy, approach and first fruits of this project.

Some real-time systems are designed to deliver services to objects that are controlled by external sources. Their services must be delivered on a timely basis, and the system fails when some services are delivered too late. Such a system may fail if the timing requirements, which it is designed to meet are erroneous. It may under-utilize resources and, consequently, be costly or unreliable if the requirements are too stringent. In general, the timing requirements of the system may change when the states of the objects monitored by the system change. Hence, one must identify how changes in object states call for changes in system requirements and how these changes should be incorporated in the design and implementation of the system. We first describe a methodology to determine timing requirements and to take into account of requirement changes at runtime. The method is based on several timing requirement determination schemes. Simulation data show that these schemes are effective for applications such as mobile IP hand-offs. We then discuss how to incorporate this methodology in the design of such systems and in the development process.

This paper presents a new workload model, called the state-dependent deadline model, for applications whose high-level timing requirements may change with time. The problem is how to choose target deadlines for jobs from their time-varying deadlines so that the system can meet its requirements with a high probability. In the clairvoyant case, the deadline of every job is given by a known function of time for all times after the job is released. There is an optimal deadline determination algorithm. When the future values of job deadlines are unknown, it is not possible to make optimal choices of job deadlines. Several heuristics can be used to determine deadlines in this realistic case. Simulation results show that these heuristics allow the system to achieve good processor utilization and high probability of meeting its time-varying requirements.

This paper compares the performance of three classes of scheduling algorithms for real-time systems in which jobs may overrun their allocated processor time potentially causing the system to be overloaded. The first class, which contains classical priority scheduling algorithms as exemplified by DM and EDF provides a baseline. The second class is the Overrun Server Method which interrupts the execution of a job when it has used its allocated processor time and schedules the remaining portion as a request to an aperiodic server. The final class is the Isolation Server Method which executes each job as a request to an aperiodic server to which it has been assigned. The performance of the Overrun Sewer and Isolation Server Methods are worse, in general, than the performance of the baseline algorithms on independent workloads. However under the dependent workloads considered, the performance of the Isolation Server Method, using a server per task scheduled according to EDF, was significantly better than the performance of classical EDF.

This paper describes a hierarchical scheme for scheduling periodic messages of distributed real-time applications in a cluster of PCs connected by a Myrinet. The scheme allows the developer of each real-time application to validate the schedulability of the application as if it were running alone on slower dedicated processors and network. A simple acceptance test is provided. According to the test, the operating system can determine whether to admit a new real-time system application into a system without having to perform detailed global schedulability analysis. Simulation results show that the hierarchical scheduling scheme outperforms the corresponding one-level heuristic algorithms. An open system prototype on a Myrinet cluster PCs running Windows NT uses this hierarchical scheme.

This paper extends the two-level hierarchical scheme in (Deng et al., 1997) for scheduling independently developed real-time applications with non-real-time applications in an open environment. The environment allows the schedulability of each real-time application to be validated independently of other applications in the system. The extended scheme removes the following two restrictions of the scheme: real-time applications that are scheduled preemptively must consist solely of periodic tasks; and applications must not share global resources (i.e., resources used by more than one application). Consequently, the extended scheme can accommodate a much broader spectrum of real-time applications.

This paper describes algorithms for scheduling preemptive, imprecise, composite tasks in real-time. Each composite task consists of a chain of component tasks, and each component task is made up of a mandatory part and an optional part. Whenever a component task uses imprecise input, the processing times of its mandatory and optional parts may become larger. The composite tasks are scheduled by a two-level scheduler. At the high level, the composite tasks are scheduled preemptively on one processor, according to an existing algorithm for scheduling simple imprecise tasks. The low-level scheduler then distributes the time budgeted for each composite task across its component tasks so as to minimize the output error of the composite task.

The workload of many real time systems can be characterized as a set of preemptable jobs with linear precedence constraints. Typically their execution times are only known to lie within a range of values. In addition, jobs share resources and access to the resources must be synchronized to ensure the integrity of the system. The paper is concerned with the schedulability of such jobs when scheduled on a priority driven basis. It describes three algorithms for computing upper bounds on the completion times of jobs that have arbitrary release times and priorities. The first two are simple but do not yield sufficiently tight bounds, while the last one yields the tightest bounds but has the greatest complexity.

In many distributed real-time systems, the workload can be modeled as a set of periodic tasks, each of which consists of a chain of subtasks executing on different processors. Synchronization protocols are used to govern the release of subtasks so that the precedence constraints among subtasks are satisfied and the schedulability of the resultant system is analyzable. Tasks have different worst-case and average end-to-end response times when different protocols are used. In this paper, we consider distributed real-time systems with independent, periodic tasks and fixed-priority scheduling algorithms. We propose three synchronization protocols and conduct simulation to compare their performance with respect to the two timing aspects.

This paper presents the budgeted-weighted-round-robin (BWRR) algorithm for scheduling the transmission of hard-real-time messages in a packet-switched network. The BWRR algorithm provides a bound on the worst case delay of a message through the network. In addition, with the BWRR algorithm, the necessary buffer space at each switch is predictable and can be fixed at the system configuration time. The per switch delay and required buffer space provided by the BWRR algorithm are significantly less than those provided by previous methods. The BWRR algorithm has a simple hardware implementation and admission test, and it does not require a global clock or any explicit flow control messages. It can achieve high utilization of the network under most practical scenarios and reacts predictably under transient overloads.

Hard-real-time schedulability analysis is carried out based on the assumption that the worst-case execution time (WCET) of each task is known. Cycle-stealing Direct Memory Access (DMA) I/O steals bus cycles from an executing program and prolongs the execution time of the program. Because of the difficulty in bounding the interference on the executing program, cycle-stealing DMA I/O is often disabled in hard-real-time systems. This paper presents an analytical method for bounding the WCET of a program executing concurrently with cycle-stealing DMA I/O. This is an extension of our previous work which bounded the WCET of a straight-line sequence of instructions when cycle-stealing operations are allowed. We demonstrate the effectiveness of our method with experiments on several programs.

This paper describes four scheduling algorithms and two packet-dropping algorithms for transmitting soft-real-time variable-bit-rate traffic in a packet-switched network. Simulation results show that the first-come-first-serve algorithm, which is equivalent to the earliest-deadline-first algorithm when all packets have equal relative deadlines, outperforms the timed-token algorithm as well as two other real-time scheduling algorithms. We also simulated the last-in-first-discard (LIFD) algorithm as well as a more complex (1,k) packet-dropping algorithm which, for each stream, tries to drop no more than I packet in any sequence of k packets. We found that although the (1,k) dropping algorithm does significantly reduce the failure rate, the same reduction in this failure rate can be achieved by slightly lowering the network utilization and using the simpler LIFD algorithm.

A DMA controller that operates in the cycle-stealing mode transfers data by "stealing" bus cycles from an executing program. This cycle stealing operation retards the progress of the executing program and extends its execution time. We first present a method that bounds the worst-case execution time of a program executing concurrently with a cycle-stealing DMA I/O operation in the simple case where the execution time of each machine instruction is fixed. We next extend this method to deal with the case of instruction-cache architectures. We demonstrate the effectiveness of our methods by the results of simulations of several programs.

In many real-time systems, the workload can be characterized as a set of jobs with linear precedence constraints among them. Jobs often have variable execution times and arbitrary release times. We describe three algorithms that can be used to compute upper bounds on completion times of such jobs scheduled on a priority-driven basis. The algorithms have different performance and complexity. Simulation was performed to compare their performance.

This paper describes PERTS, a prototyping environment for real-time systems. PERTS provides a comprehensive set of design, validation, and simulation tools that are built on recent theoretical advances. It also provides software modules that implement wellknown and novel real-time scheduling algorithms, task and resource assignment algorithms, and resource access control protocols. Together, the tools and software modules support the systematic and rigorous evaluation of new designs, experimentation with alternative scheduling and resource management strategies, and the evaluation and validation of the resultant real-time system.

This paper describes three algorithms for scheduling preemptive, imprecise tasks on a processor to minimize the total error. Each imprecise task consists of a mandatory task followed by an optional task. Some of the tasks are on-line; they arrive after the processor begins execution. The algorithms assume that when each new on-line task arrives, its mandatory task and the portions of all the mandatory tasks yet to be completed at the time can be feasibly scheduled to complete by their deadlines. The algorithms produce for such tasks feasible schedules whose total errors are as small as possible. The three algorithms are designed for three types of task systems: (1) when every task is on-line and is ready upon its arrival, (2) when every on-line task is ready upon arrival but there are also off-line tasks with arbitrary ready times, and (3) when on-line tasks have arbitrary ready times. Their running times are $O(n\log n)$, $O(n\log n)$, and $O(n\log ^2 n)$, respectively.

In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. We call such a task an AND task. In this paper we allow certain tasks to be ready when just one of their predecessors is complete. These tasks are known as OR tasks. We analyze the complexity of two types of real-time AND/OR task scheduling problems. In the first type of problem, all the predecessors of every OR task must eventually be completed, but in the second type of problem, some OR predecessors may be left unscheduled. We show that most problems involving tasks with individual deadlines are NP-complete, and then present two priority-driven heuristic algorithms to minimize completion time on a multiprocessor. These algorithms provide the same level of worst-case performance as some previous priority-driven algorithms for scheduling AND-only task systems.

The job scheduling problems for real-time jobs with temporal distance constraints (JSD) are presented. In JSD, the start times of two related jobs must be within a given distance. The general JSD problem is NP-hard. We define the multilevel unit-time JSD (MUJSD) problem for systems with m chains of unit-time jobs in which neighboring jobs in each chain must be scheduled within c time units. We present an $O(n^{2})$-time algorithm, where n is the total number of jobs in the system, and also an $O(m^{2}c^{2})$-time algorithm. Some other variations of the JSD problems are also investigated.

We consider the problem of scheduling tasks in the imprecise computation model to minimize the maximum error. Given a task system and a schedule of it, the maximum error of the task system is equal to the error of the task that has the largest error when the task system is executed according to the schedule. We describe two preemptive algorithms for scheduling on a processor n dependent tasks with rational ready times, deadlines, and processing times. Each schedule found by our algorithms is an optimal schedule with the minimum total error, and according to this schedule the maximum error is minimized. The run times of our algorithms are O(n/sup 3/) and O(n/sup 2/).>

We study the performance of concurrency control algorithms in maintaining temporal consistency of shared data in hard real time systems. In our model, a hard real time system consists of periodic tasks which are either write only, read only or update transactions. Transactions may share data. Data objects are temporally inconsistent when their ages and dispersions are greater than the absolute and relative thresholds allowed by the application. Real time transactions must read temporally consistent data in order to deliver correct results. Based on this model, we have evaluated the performance of two well known classes of concurrency control algorithms that handle multiversion data: the two phase locking and the optimistic algorithms, as well as the rate monotonic and earliest deadline first scheduling algorithms. The effects of using the priority inheritance and stack based protocols with lock based concurrency control are also studied.>

In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors is likely to achieve better performance. However, analytical and efficient validation methods to determine whether all the timing constraints are met do not exist for systems using modern dynamic scheduling strategies, and exhaustive simulation and testing are unreliable and expensive. This paper describes several worst-case bounds and efficient algorithms for validating systems in which jobs have arbitrary timing constraints and variable execution times and are scheduled on processors dynamically in a priority-driven manner. The special cases of the validation problem considered here are concerned with independent jobs that are (1) preemptable and migratable, or (2) preemptable and nonmigratable, or (3) nonpreemptable.>

The broadband integrated services digital network provides communication services with different requirements, including real-time services such as voice and video. Real-time services are affected by the probabilistic behavior of such a network. In particular, when the network becomes congested, the end-to-end packet delay may exceed the maximum allowed. Fortunately, many real-time services are willing to trade service quality for information timeliness. The imprecise-computation technique, in combination with layered coding schemes, makes this tradeoff possible.

The imprecise computation technique has been proposed as a way to handle transient overload and to enhance fault tolerance of real-time systems. In a system based on this technique, each time-critical task is designed in such a way that it can produce a usable, approximate result in time whenever a failure or overload prevents it from producing the desired, precise result. This paper describes ways to implement imprecise computations, models to characterize them and algorithms for scheduling them. An imprecise mechanism for the generation and use of approximate results can be integrated in a natural way with a traditional fault-tolerance mechanism. An architectural framework for this integration is described.>

A new scheduling algorithm for dataflow graphs with nested conditional branches is presented. The algorithm employs a bottom-up approach to transform a dataflow graph with conditional branches into an "equivalent" one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived. Our approach is particularly effective when there is a large number of nested conditional branches in a dataflow graph.>

The real-time performance of several existing local area network medium-access protocols under high-speed data transfer rates is studied. the goal is to determine the limitations in the ability of the protocols to guarantee on-time delivery of messages for different types of multimedia applications.

PERTS is a prototyping environment for real-time systems. It contains schedulers and resource access protocols for time-critical applications, together with a comprehensive set of tools for the analysis, validation, and evaluation of real-time systems built on the scheduling paradigms supported by these building blocks. This paper describes the underlying models of real-time systems supported by PERTS, as well as its capabilities and intended use. A key component is the schedulability analyzer. The basic version of this system of tools supports the validation and evaluation of real-time systems built on the framework of the periodic-task model. This system of tools is now available.>

APPROXIMATE, a query processor that makes approximate answers available if part of the database is unavailable, or if there is not enough time to produce an exact answer, is described. The processor implements approximate query processing, and the accuracy of the approximate result produced improves monotonically with the amount of data retrieved to produce the result. The monotone query processing algorithm of APPROXIMATE works within a standard relational algebra framework. APPROXIMATE maintains semantic information for approximate query processing at an underlying level, and can be implemented on a relational database system with little change to the relational architecture. It is shown how APPROXIMATE is implemented to make effective use of the semantic support. The additional overhead required by APPROXIMATE is described.>

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. It is shown that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, gamma -1) periods or more, where gamma is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than (1+n(2/sup 1/n/-1))/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity.>

Algorithms for scheduling a class of systems in which all the tasks execute on different processors in turn in the same order are described. This end-to-end scheduling problem is known as the flow-shop problem. Two cases in which the problem is tractable are presented, and a heuristic for the NP-hard general case is evaluated. The traditional flow-shop model is generalized in two directions. First, an algorithm for scheduling flow shops in which tasks can be serviced more than once by some processors is presented. Second, a heuristic algorithm for scheduling flow shops with periodic tasks is described. Scheduling systems with more than one flow shop are considered.>

The results of a simulation study in which the real-time performances of a high-speed token ring network and a multiple-ring network were compared are described. The medium access protocols and the interconnection topologies of the multiple-ring network evaluated are discussed. The characteristic of the workload used in this simulation experiment is described. The simulation results are given.>

Three algorithms for scheduling preemptive, imprecise tasks on a processor to minimize the total error are described. Each imprecise task consists of a mandatory task followed by an optional task. Some of the tasks are online; they arrive after the processor begins execution. The algorithms assume that when each new online task arrives, its mandatory task and the portions of all the mandatory tasks yet to be completed at the time can be feasibly scheduled to be computed by their deadlines. The algorithms produce for such tasks feasible schedules whose total errors are as small as possible. The three algorithms are designed for three types of task systems: (1) when every task is online and is ready upon its arrival; (2) when every task is online and is ready upon arrival but there are also offline tasks with arbitrary ready times; and (3) when online tasks have arbitrary ready times. Their running times are O(n log n), O(n log n), and O(n log/sup 2/ n), respectively.>

A novel scheduling algorithm for dataflow graphs with nested conditional branches is presented. The algorithm employs a bottom-up approach to transform a dataflow graph with conditional branches into an 'equivalent' one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived. Experimental results demonstrated that such an approach is quite effective. The proposed bottom-up hierarchical approach is computationally more effective than a global nonhierarchical one.>

Simulation experiments show that the token ring protocol gave a lower average message delay at low transfer rates, but the token bus protocol gave a better overall performance for applications where only average delay is of interest. On the other hand, in hard real-time systems, the criterion of importance is not the average message delay, but the maximum message delay and the ability to meet deadlines. Slotted ring in this case is a much better protocol than the others because of its low maximum message delay and more predictable message delay. Because of this, and because the average performance of the slotted ring remains good as the size or the transfer rate of the network increases, the slotted ring protocol is preferred over the token ring and token bus protocols for hard real-time systems.>

An object-oriented query processor is described that makes approximate answers available if there is not enough time to product an exact answer or if part of the database is unavailable. The accuracy of the approximate result produced improves monotonically with the amount of data retrieved to produce the result. The query-processing algorithm is based on an approximate relational data model and works within a standard relational algebra framework. The query processor maintains an object-oriented view on an underlying level and can be implemented on a relational database system with little change to the relational architecture. It is shown how a monotone query-processing strategy can be implemented, making effective use of semantic information presented by the object-oriented view.>

Here the problem of scheduling tasks, each of which is logically decomposed into a mandatory subtask and an optional subtask, is considered. The mandatory subtask must be executed to completion in order to produce an acceptable result. The optional subtask begins after the mandatory subtask is completed and refines the result in order to reduce the error in the result. The optional subtask can be left incomplete. The error in the result of a task is equal to the processing time of the unfinished portion of the optional subtask. Two preemptive algorithms for scheduling, on a uniprocessor system, n dependent tasks with rational ready times, deadlines, and processing times are described. An algorithm is optimal in the following sense: whenever feasible schedules that meet the ready time and deadline constraints of all tasks exist, it finds one that has the minimum total error of all tasks. One of the algorithms is optimal when the tasks have identical weights, and its time complexity is $O(n\log n)$. The other algorithm has time complexity $O(n^2 )$, but is optimal when tasks have different weights. A schedule is said to satisfy the $0/1$ constraint when every optional subtask is either completed or discarded. The problem of finding an optimal feasible schedule that satisfies the $0/1$ constraints and minimizes the total processing time of the discarded optional subtasks is NP-complete. Two algorithms for finding optimal schedules of dependent tasks on a uniprocessor system for the special case when all optional subtasks have identical processing times are presented.

The authors present a model of typical hard real-time applications and the concepts of age and dispersion of data accessed by the real-time transactions. These are used to evaluate the performance of a class of multiversion lock-based concurrency control algorithms in maintaining temporal consistency of data in a real-time shared-data environment. It is shown that it is easier for such a concurrency control algorithm to maintain temporal consistency of shared data when the conflicting transactions are close in the lengths of their periods. The conflict pattern of the transactions has a more significant effect on the temporal inconsistency of data than the load level of the system. It is also desirable to have the transactions' periods within a small range. The best case was obtained when the faster transactions have higher utilizations. It was also shown that the use of the priority inheritance principle with the lock-based concurrency control algorithms can reduce transactions' blocking times and the number of transactions that access temporally inconsistent data as well as the worst-case age and dispersion of data.>

The problem of scheduling periodic jobs in hard real-time systems that support imprecise computations is discussed. Timing faults are avoided in such systems by making available intermediate, imprecise results of acceptable quality when results of the desired quality cannot be produced on time. Two workload models of imprecise computations are presented. These models differ from traditional models in that a task may be terminated any time after it has produced an acceptable result. Each task is logically decomposed into a mandatory part followed by an optional part. In a feasible schedule, the mandatory part of every task is completed before the deadline of the task. The optional part refines the result produced by the mandatory part to reduce the error in the result.>

A query processing method that produces approximate answers to queries posed in standard relational algebra is presented. This method is monotone in the sense that the accuracy of the approximate result improves with the amount of time spent producing the result. This strategy makes it possible to trade the time to produce the result for the accuracy of the result. An approximate relational model that characterizes approximate relations and a partial order for comparing them is developed. Relational operators which operate on and return approximate relations are defined.>

An examination is made of the worst-case performance of a class of scheduling algorithms commonly known as priority-driven or list-scheduling algorithms. These algorithms have anomalous, unpredictable performance when used to suboptimally schedule nonpreemptive tasks with precedence constraints. A general method is presented for deriving the worst-case performance of these algorithms. This method is easy to use, yet powerful enough to yield tight performance bounds for many classes of scheduling problems. It is demonstrated that the method has wide applicability. Several task systems are presented for which list-scheduling algorithms have worst-case performance, and the general characteristics of these task systems are discussed. It is believed that these task systems are sometimes ignored in simulation studies; consequently, the results of these studies may be overly optimistic.>

Consideration is given to the problem of scheduling tasks each of which is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be executed to completion. If the available processor time is insufficient, the optional subtask can be left incomplete. The error in the result of a task is equal to the processing time of the unfinished portion of the optional subtask. A description is given of a preemptive algorithm for scheduling n dependent tasks with rational ready times, deadlines, and processing times on a uniprocessor system. This algorithm determines whether feasible schedules that meet the timing constraints of all tasks exist; when feasible schedules exist, it finds one that has the minimum total error. The complexity of this algorithm is O(n log n). A schedule is said to satisfy the 0/1 constraint when every optional subtask is either completed or discarded. The problem of finding an optimal feasible schedule that satisfies the 0/1 constraint and minimizes the number of discarded optional subtasks is NP-complete. Two algorithms are presented for finding optimal schedules of dependent tasks on a uniprocessor system for the special case when all optional subtasks have identical processing times.>

Recently, multichannel networks composed of several parallel, medium-speed channels multiplexed on a single high-speed medium have been proposed as a practical way to harness the high bandwidths of optical fibers. In order to limit the cost of network interfaces, a partially-connected multichannel network allows each node access to only a proper subset of the channels, its channel set. Staircase interconnection topologies constitute a family of partially-connected multichannel networks in which every node can still send messages directly to every other node.

Several preemptive, priority-driven algorithms for scheduling periodic jobs on systems that support imprecise computations are described and evaluated. The algorithms are designed to keep the average error in the results produced over consecutive periods small. The approach taken here is to consider each task as consisting of two parts: a mandatory part that must be completed in order for the task to produce an acceptable result, and an optional part that refines the result produced by the mandatory part to reduce the error in the result. The mandatory parts of all tasks have hard deadlines; the rate-monotone algorithm is used to schedule them to meet all deadlines. The optional parts have soft deadlines; different algorithms are used to schedule the optional parts to minimize the average error. The performance of these algorithms is evaluated in terms of the average error over all jobs as a function of their total utilization factor.>

Token ring networks differ in the manner in which acknowledgements are handled. In Newhall rings, acknowledgements of data packets are either sent as independent packets or piggybacked on returned data packets. In acknowledgement rings, there is an acknowledgement field in each data packet. The authors present an empirical formula that predicts the average network access delay in networks where the sender is allowed to transmit only one packet each time it seizes the token and discuss its validity. The performance of the stop-and-wait ARQ (automatic-repeat-request) scheme in token ring networks is treated. The average access delay, optimum window size, and maximum achievable throughput as functions of network and protocol parameters in Newhall rings when the continuous ARW scheme is used are studied. Tradeoffs between average access delay and average buffer occupancy time are examined.>

Mentat, an object-oriented macro data flow system designed to facilitate parallelism in distributed systems, is presented.The macro data flow model is a model of computation similar to the data flow model with two principle differences: the computational complexity of the actors is much greater than in traditional data flow systems, and there are persistent actors that maintain state information between executions.Mentat is a system that combines the object-oriented programming paradigm and the macro data flow model of computation.Mentat programs use a dynamic structure called a future list to represent the future of computations.

The Report Generation Facility is a high-level interface designed and implemented to support coherent access of data stored in a number of stand-alone, independent, database systems served by it. Specifically, the Report Generation Facility provides a menu which allows a user to request one or more standard reports provided by the individual database systems and the Report Generation Facility, or to formulate a query in an English-like query language without having to specify where the requested data reside or how to retrieve them. The Report Generation Facility translates the user's request or query into subtransactions to the individual database systems and submits the substransactions in order to retrieve and format the data requested by the user. Thus, the Report Generation Facility provides a standard way to produce reports based on data stored in the database systems with minimal user effort and expertise. This paper describes its capabilities and architecture.

This paper describes the mutual consistency maintenance mechanism used in a prototype Data Traffic Management System (DTMS), which was designed and implemented to integrate several independent and stand-alone data systems owned by the U. S. Army, Corp of Engineers (CE). The major design constraints were that no modification to the data systems involved were allowed and that the update to each duplicate copy was to be handled as automatically as possible and in a manner approved by the manager of the system containing the copy. The capabilities of the prototype DTMS and the Mutual Consistency Maintenance Subsystem are discussed. The linkage directory used to support mutual consistency maintenance and the mutual consistency maintenance mechanism are described.

The time-slot assignment problem for a satellite-switched time-division multiple access system where only a restricted set of all possible switching modes is to be used is studied. An efficient algorithm for finding an optimal assignment is proposed. Also, methods for selecting restricted sets of switching modes are presented.

We are concerned here with the design of intelligent magnetic bubble memories which may be used to support high-level data base management functions. They may also be used to provide users with large work spaces in which elementary file processing operations may be performed without external intervention. It is our intent to explore ways of incorporating in the design of these memories the novel chip organizations and unique features of magnetic bubble memories. In particular, we evaluate the performance of various memory organizations and storage organizations for different magnetic bubble chips. Retrieval times per word and per page are the parameters used to evaluate the different memory organizations. Performance of hierarchical bubble memory systems are discussed. The data rearrangement operations capable of being carried out in bubble memories are incorporated in the design of elementary file processing operations and basic relational algebraic operations. An architecture of intelligent magnetic bubble memory designed to support the relational data model and to enhance a relational algebraic interface is described.

In this paper, we are concerned with the design of intelligent magnetic bubble memories. It is our intent to explore ways of incorporating the novel bubble chip organizations and bubble movement operations in the design of such memories. In particular, we evaluate the improvements in performance of various file processing algorithms and memory organizations which can be achieved through their use. Retrieval times per word and per page are the parameters used to evaluate the different memory organizations. Performance of hierarchical memory systems using bubble memories are discussed. The unique features of magnetic bubble memories are used in designing algorithms for elementary file processing operations such as sorting and merging and for basic relational algebraic operations.

In this paper, we study several probabilistic models of inverted file information retrieval systems. In particular, the portion of the system which performs the tasks of list accessing and merging is modeled. The average response times of the system for three different methods of managing the disk access and merge processor queues are discussed.

In an inverted file system a query is in the form of a Boolean expression of index terms. In response to a query the system accesses the inverted lists corresponding to the index terms, merges them, and selects from the merged list those records that satisfy the search logic. Considered in this paper is the problem of determining a Boolean expression which leads to the minimum total merge time among all Boolean expressions that are equivalent to the expression given in the query. This problem is the same as finding an optimal merge tree among all trees that realize the truth function determined by the Boolean expression in the query. Several algorithms are described which generate optimal merge trees when the sizes of overlaps between different lists are small compared with the length of the lists.

We are concerned with the detection of a set ofMmessages that are transmitted over a channel disturbed by chaotic thermal noise when quantum effects in the communication systems are taken into account. Our attention is restricted to the special case in which the density operators specifying the state of the received field are commutative. In particular, the performance of two special communication systems is evaluated. For a system in which orthogonal signals with known amplitudes and random phases are transmitted over an additive white Gaussian channel, the structure of an optimum receiver is found. Expressions for the system reliability function and channel capacity are derived. For a system in which orthogonal signals are transmitted over a Rayleigh fading channel, the optimum performance is obtained. The optimum degree of diversity for an equal-strength diversity system is found numerically as a function of the average thermal-noise energy and information rate.