Accessibility maps are key to support individuals with disabilities to actively participate in the society. The Americans with Disabilities Act (ADA) defines minimum requirements for roads and other public accommodation spaces to be accessible. Yet, it is sufficient to have one accessible route in a place, and available digital-maps lack accessibility information to help finding that accessible route.In this paper, we present the AccessMap system to automatically extend road-maps with accessibility semantics. It enables indoor and outdoor spaces to be automatically marked as visually-impaired and/or wheel-chaired accessible/inaccessible. AccessMap passively crowdsources measurements from sensors available in the users' smartphones to detect accessibility semantics. It employs a probabilistic framework to build and update the map with the semantics. Evaluation of AccessMap in different countries shows that it can passively detect a wide-range of accessibility semantics with high precision and recall (on average around 89.8% and 86.3% respectively). Furthermore, its probabilistic crowdsourcing framework increases the generated map’s average precision and recall to 98.7% and 99% with as few as seven encounters per semantic.

In this paper, we present Hapi, a novel system that uses off-the-shelf standard WiFi to provide pseudo-3D indoor localization---it estimates the user's floor and her 2D location on that floor. Hapi is calibration-free, only requiring the building's floorplans and its WiFi APs' installation location for deployment. Our analysis shows that while a user can hear APs from nearby floors as well as her floor, she will typically only receive signals from spatially closer APs in distant floors, as compared to APs in her floor. This is due to signal attenuation by floors/ceilings along with the 3D distance between the APs and the user. Hapi leverages this observation to achieve accurate and robust location estimates.

Designing indoor and outdoor spaces to become accessible for people with disabilities is of paramount importance. Accessibility leads to improvements in human rights and business outcomes; due to inclusion of a broader range of the population. For example, adding braille writing to signs and installing ramps allow visually-impaired people and the wheel-chaired to navigate on their own.

Machine-to-machine communication (M2M) technology enables large-scale device communication and networking, including home devices and appliances. A critical issue for home M2M networks is how to efficiently integrate existing home consumer devices and appliances into an IP-based wireless M2M network with least modifications. Due to its popularity and widespread use in closed spaces, Wi-Fi is a good alternative as a wireless technology to enable M2M networking for home devices. This paper addresses the energy-efficient integration of home appliances into a Wi-Fi- and IP-based home M2M network. Toward this goal, we first propose an integration architecture that requires least modifications to existing components. Then, we propose a novel long-term sleep scheduling algorithm to be applied with the existing 802.11 power save mode. The proposed scheme utilizes the multicast DNS protocol to maintain device and service availability when devices go into deep sleep mode. We prototyped our proposed architecture and algorithm to build a M2M network testbed of home appliances. We performed various experiments on this testbed to evaluate the operation and energy savings of our proposal. We also did simulation experiments for larger scale scenarios. As a result of our test-bed and simulation experiments, we observed significant energy savings compared to alternatives while also ensuring device and service availability.

In order to make context-aware systems more effective and provide timely, personalized and relevant information to a user, the context or situation of the user must be clearly defined along several dimensions. To this end, the system needs to simultaneously recognize multiple dimensions of the user'

Recent multi-armed bandit based optimization schemes provide near-optimal balancing of arm exploration against arm exploitation, allowing the optimal arm to be identified with probability arbitrarily close to unity. However, the convergence speed drops dramatically as the number of bandit arms grows large, simply because singling out the optimal arm requires experimentation with all of the available arms. Furthermore, effective exploration and exploitation typically demands computational resources that grow linearly with the number of arms. Although the former problem can be remedied to some degree when prior knowledge about arm correlation is available, the latter problem persists. In this paper we propose a Thompson Sampling (TS) based scheme for exploring an arm space of size K by decomposing it into two separate arm spaces, each of size sqrtK, thus achieving sub-linear scalability. In brief, two dedicated Thompson Samplers explore each arm space separately. However, at each iteration, arm selection feedback is obtained by jointly considering the arms selected by each of the Thompson Samplers, mapping them into the original arm space. This kind of decentralized decision-making can be modeled as a game theory problem, where two independent decision makers interact in terms of a common pay-off game. Our scheme requires no communication between the decision makers, who have complete autonomy over their actions. Thus it is ideal for coordinating autonomous agents in a multi-agent system. Extensive experiments, including instances possessing multiple Nash equilibria, demonstrate remarkable performance benefits. Although TS based schemes already are among the top-performing bandit players, our proposed arm space decomposition scheme provide drastic improvements for large arm spaces, not only in terms of processing speed and memory usage, but also in terms of an improved ability to identify the optimal arm, increasing with the number of bandit arms.

We describe an abstract, generic and extensible ontology, the Rover Context Model Ontology (RoCoMO), which is currently being designed and developed to model and represent context in an intelligent context-aware middleware system, called Rover II. The Rover Context Model (RoCoM) is the underlying context model for Rover II and is centered on four primitives that can be used to represent a situation: entity, event, activity and relationship. The ontology is expressed using the Web Ontology Language (OWL) and includes two components -- RoCoM Core Ontology and the RoCoM Application Ontology. We also illustrate its usage with the aid of a public safety application called M-Urgency that is currently deployed at the UMD campus.

A major challenge of context models is to balance simplicity, generality, usability and extensibility. It is also important that the model be practical and implementable. In pursuit of this goal, this paper proposes a context model, Rover Context Model (RoCoM), structured around four primitives that can be used to represent and model any situation and activity: entities, events, relationships, and activities. It introduces the notion of templates of context for each primitive and describes, albeit briefly, the RoCoM Ontology (RoCoMO). It also describes the design and architecture of an abstract, generic and intelligent context-aware middleware called Rover II. We propose this framework as a solution to address the context problem as a whole, and be usable in many domains. We also illustrate its application with the aid of a context-aware public safety application that is deployed in the UMD campus.

M-Urgency is a public safety system that (1) redefines how emergency calls are made to a Public Safety Answering Point (PSAP) like the 911 system and (2) is designed to be context-aware of the situation in which it is used. M-Urgency enables mobile users to stream live audio and video from their devices to local PSAP along with the audio stream, the real time location and the relevant context information, enabling appropriate and prompt service. This paper presents a new feature, incorporated in M-Urgency, that enables social contribution whereby users in the vicinity of an emergency event can help operation conducted by the emergency personnel through verbal/visual information useful to them or by providing assistance. Our experiments show a very positive response from the participant to the capabilities of our system. In this paper, we also discuss the social implications such as privacy and security for this system.

The importance of information for the appropriate handling of any situation is well recognized. We, as human beings, use context not only to interpret available information, but also to seek additional relevant, missing information. Most information systems, which support human decision-making, process context inadequately. Moreover, when some context is considered, the structure is often so rigid that, but for very restricted applications, such systems are not usable. In order to integrate context-handling capabilities with an information integration system, we need a context model for representing context that can efficiently acquire, maintain and integrate contextual information and make it available to applications on demand. In this paper, we present such a model and describe the design of Rover II, a situation-handling platform which supports integration of context-aware applications. The system manages context by constructing a situation graph which dynamically reflects the relevant situation information. We illustrate the use of Rover II with M-Urgency, a public safety application providing audio and video support for emergency help. This system is being deployed for the University of Maryland campus community of 44 000 students, faculty and staff.

Wireless networks which support multiple modulation techniques and data rates suffer from the so-called multi-rate anomaly problem resulting in unfair environments; in which all the users, regardless of their data rate choices, observe the same, low throughput values. This situation violates the baseline fairness principle which states that the desired throughput of a node competing against any nodes running at different speeds is equal to the throughput that the node would achieve in an existing single-rate network in which all the competing nodes were running at its own rate. In our work presented here, we propose a novel algorithm which utilizes the retry limit parameter of the CSMA/CA algorithm in order to differentiate different data rate user groups. Our algorithm, MORAL (Multiuser data Rate Adjustment Algorithm), dynamically adjusts the retry limits of the users according to the channel characteristics observed and the neighbor information gathered from previous communications. MORAL chooses the most appropriate retry limit to use in order to establish a more baseline-fair environment.

We present a public safety system that (1) redefines how emergency calls are presently made (2) has been designed to be fully context aware. First, we describe Rover 2.0, a context aware framework which caters to the development of mobile applications. The framework uses a paradigm for handling context information, which could be user specific context, combined with the general context of the system and the environment, to provide relevant functions and support to the users through the applications. More importantly, we present M-Urgency, a public safety application, developed on the Rover 2.0 platform that redefines the way an emergency call is made to the PSAP (Public Safety Answering Point). M-Urgency enables mobile users to stream live video from their devices to local PSAP along with the audio stream, the real time location information and any personal relevant information about the caller. We are in the process of deploying the M-Urgency system at the University of Maryland Police Department for a pilot.

The world is seeing two significant trends today -- (a) most of the decisions and actions are performed based on the information available (b) the increasing popularity of smart phones and mobile apps that function in isolated manner. We present Rover 2.0, framework that caters to the development of context-aware mobile applications. As technology is used to augment human capabilities, it is important that the applications should combine the con-text of the end user, the system and the environment, to provide relevant functions and support to the users. Rover 2.0 is an ongo-ing effort and we present here a brief description of its current state. We also present a public safety application called M- Urgency.

The ability to measure location using time of flight in 802.11 networks is impeded by the standard one microsecond clock resolution, imprecise synchronization of the 802.11 protocol, and the inaccuracy of available clock oscillators. We demonstrate a technique for off-the-shelf 802.11 hardware that enables accurate determination of location of transmitting 802.11 devices using time difference of arrival (TDOA). The technique refines the PinPoint clock model for 802.11 wireless cards, enabling accurate translation of times from one frame of reference to another for free-running clocks and producing accurate location of transmitting nodes to within 3m. This technique can locate nodes regardless of their participation in the location system and may be applied to other wireless communication protocols where send and receive timestamps are available.

First responders need to be able to have the most amount of situational awareness of the operations they perform while not being overwhelmed by all of the information that may be made available to them. This paper presents the Rover integration and fusion platform to alleviate the fusing of multiple information sources, which may not be known prior to the beginning of an operation. Rover can aid fusing sources by providing as much contextual information which often will be forgotten when designing programs, mapping contextual information into a view in which programs and users can use, and automate well-known and designed tasks. All of this occurs while deploying Rover to first responder incident scenes without the need for an existing network infrastructure prior to an incident.

Knowledge of node's locations is an essential requirement for many applications of wireless sensor networks. A major problem with multi-hop location discovery is the accumulated error. In this paper, we analyze the effect of reflection errors and present the Multi-hop Relative Location Estimation (MRLE) algorithm that estimates relative node's positions with low error margins. We capture the impact of different parameters on the accuracy of the estimated position and introduce a new metric, called the CLIQUE factor, that has a very dominant effect on the accuracy of the estimated positions. We further highlight means for trading accuracy for energy consumption and/or computational overhead.

Typical location determination systems require the presence of a physical device that is attached to the person that is being tracked. In addition, they usually require the tracked device to participate actively in the localization process. In this paper, we introduce the concept of Device-free Passive (DfP) localization. A DfP system is envisioned to be able to detect, track, and identify entities that do not carry any device, nor participate actively in the localization process. The system works by monitoring and processing changes in the received physical signals at one or more monitoring points to detect changes in the environment. Applications for DfP systems include intrusion detection and tracking, protecting outdoor assets, such as pipelines, railroad tracks, and perimeters.We describe the DfP system's architecture and the challenges that need to be addressed to materialize a DfP system. We show the feasibility of the system by describing algorithms for implementing different functionalities of a DfP system that works with nominal WiFi equipment. We present two techniques for intrusion detection and a technique for tracking a single intruder. Our results show that the system can achieve very high probability of detection and tracking with very few false positives. We also identify different research directions for addressing the challenges of realizing a DfP system.

Clustering is a standard approach for achieving efficient and scalable performance in wireless sensor networks. Most of the published clustering algorithms strive to generate the minimum number of disjoint clusters. However, we argue that guaranteeing some degree of overlap among clusters can facilitate many applications, like inter-cluster routing, topology discovery and node localization, recovery from cluster head failure, etc. We formulate the overlapping multi-hop clustering problem as an extension to the k-dominating set problem. Then we propose MOCA; a randomized distributed multi-hop clustering algorithm for organizing the sensors into overlapping clusters. We validate MOCA in a simulated environment and analyze the effect of different parameters, e.g. node density and network connectivity, on its performance. The simulation results demonstrate that MOCA is scalable, introduces low overhead and produces approximately equal-sized clusters.

This paper presents the design, implementation and evaluation of the PinPoint location determination system. PinPoint is a distributed algorithm that enables a set of $n$ nodes to determine the RF propagation delays between every pair of nodes, from which the inter-node distances and hence the spatial topology can be readily determined. PinPoint does not require any calibration of the area of interest and thus is rapidly deployable. Unlike existing time-of-arrival techniques, PinPoint does not require an infrastructure of accurate clocks (e.g., GPS) nor does it incur the o(n2) message exchanges of "echoing" techniques. PinPoint can work with nodes having inexpensive crystal oscillator clocks, and incurs a constant number of message exchanges per node to determine the location of $n$ nodes. Each node's clock is assumed to run reliably but asynchronously with respect to the other nodes, i.e., they can run at slightly different rates because of hardware (oscillator) inaccuracies. PinPoint provides a mathematical way to compensate for these clock differences in order to arrive at a very precise timestamp recovery that in turn leads to a precise distance determination. Moreover, each node is able to determine the clock characteristics of other nodes in its neighborhood allowing network synchronization. We present a prototype implementation for PinPoint and discusses the practical issues in implementing the mathematical framework and how PinPoint handles the different sources of error affecting its accuracy. Evaluation of the prototype in typical indoor and outdoor environments shows that PinPoint gives an average accuracy of four to six feet, in different environments, allowing PinPoint to support accurate rapidly deployable localization scenarios.

In this paper, we propose an enhancement to the existing IEEE 802.11 distributed coordination function (DCF) MAC to improve channel spatial reuse efficiency, and thus improve overall network data throughput. Our modification, named the location enhanced DCF (LED) for IEEE 802.11, incorporates location information in DCF frame exchange sequences so that stations sharing the communication channel are able to make better interference predictions and blocking assessments. Utilizing an underlying physical layer design that supports frame capture, the LED enhanced interference estimation can increase overall network data throughput by permitting more concurrent transmissions. In this paper we also analytically study the potential performance enhancement of the LED over the original IEEE 802.11 DCF. The results are verified using the ns-2 simulator, which shows that up to 35% of DCF blocking decisions are unnecessary and our LED method can achieve up to 22% more throughput than the original DCF.

Wireless sensor networks have recently gained a lot of attention from the research community. Wireless sensor networks are often partitioned into clusters, each managed by a cluster head (gateway). In this paper, we study the performance of the IEEE 802.11 based wireless sensor networks in noisy environments. We show that using the standard binary exponential backoff (BEB) mechanism in noisy clustered sensor networks results in a poor throughput performance due to its inability of differentiating between the causes of unsuccessful packet transmissions and verify the analytical model using the ns-2 simulator. We show the enhanced BEB mechanism in [T. Nadeem et al. (2004)] enhances clustered sensor network performance up to order of magnitudes with respect to the network error rates (noise level). We also study the noise effect on the fairness of IEEE 802.11 and show that our proposed mechanism maintains the channel fairness between the competing sensors.

There has been a growing interest in the applications of wireless sensor networks in unattended environments. In such applications, sensor nodes are usually deployed randomly in an area of interest. Knowledge of accurate node location is essential in order to correlate the gathered data to the origin of the sensed phenomena and assure the relevance of the reported information. In this paper, we present an efficient anchor-free protocol for localization in wireless sensor networks. Each node discovers its neighbors that are within its transmission range and estimates their ranges. Our algorithm fuses local range measurements in order to form a network wide unified coordinate systems while minimizing the overhead incurred at the deployed sensors. Scalability is achieved through grouping sensors into clusters. Simulation results show that the proposed protocol achieves precise localization of sensors and maintains consistent error margins.

We present the design and implementation of the Horus WLAN location determination system. The design of the Horus system aims at satisfying two goals: high accuracy and low computational requirements. The Horus system identifies different causes for the wireless channel variations and addresses them to achieve its high accuracy. It uses location-clustering techniques to reduce the computational requirements of the algorithm. The lightweight Horus algorithm helps in supporting a larger number of users by running the algorithm at the clients.We discuss the different components of the Horus system and its implementation under two different operating systems and evaluate the performance of the Horus system on two testbeds. Our results show that the Horus system achieves its goal. It has an error of less than 0.6 meter on the average and its computational requirements are more than an order of magnitude better than other WLAN location determination systems. Moreover, the techniques developed in the context of the Horus system are general and can be applied to other WLAN location determination systems to enhance their accuracy. We also report lessons learned from experimenting with the Horus system and provide directions for future work.

WLAN location determination systems add to the value of a wireless network by providing the user location without using any extra hardware. Current systems return the estimated user location from a set of discrete locations in the area of interest, which limits the accuracy of such systems to how far apart the selected points are. In this paper, we present two techniques to estimate the user location in the continuous physical space, namely the center of mass technique and time averaging technique. We test the performance of the two techniques in the context of the Horus WLAN location determination system under two different testbeds. Using the center of mass technique, the performance of the Horus system is enhanced by more than 13% for the first testbed and more than 6% for the second testbed. The time-averaging technique enhances the performance of the Horus system by more than 24% for the first testbed and more than 15% for the second testbed. The techniques are general and can be applied to any of the current WLAN location determination systems to enhance their accuracy. Moreover, the two techniques are independent and can be applied together to further enhance the accuracy of the current WLAN location determination systems

Physical layer capture (PLC) in 802.11b refers to the successful reception of the stronger (higher signal strength at receiver) frame in a collision. PLC causes significant imbalance in the throughputs of sources. Existing 802.11b simulators, including ns2 and Qualnet, assume that PLC occurs only if the stronger frame arrives first at the receiver. We show empirically that in reality PLC occurs even if the stronger frame arrives later (but within the physical layer preamble of the first frame). Consequently, throughput unfairness in reality can be significantly (up to 15%) higher than with the former PLC model. We have modified the ns2 simulator to account for this and Qualnet is incorporating a fix in their next release. To identify which frames were involved in collisions, when their transmissions started, and which of them were retrieved, we have devised a novel technique using multiple sniffers and instrumented device drivers to reconstruct from the air interface all tx/rx events in a WLAN to within 4 /spl mu/s accuracy. This allows us to quantify the causal links from the PHY layer through the MAC layer to the observed application layer imbalance. It also shows that the arrival times of colliding frames routinely differ by as much as 20 /spl mu/s due to inherent uncertainties of 802.11b firmware clock synchronization and rx/tx turnaround delays, and that the frame to arrive first can be either the stronger or the weaker with equal likelihood.

We present an autoregressive model for modelling samples autocorrelation from the same access point in WLAN location determination systems. Our work is in the context of the Horus system, which is a probabilistic WLAN location determination system. We show that the autocorrelation between consecutive samples from the same access point can be as high as 0.9. Using our model, we describe a technique to use multiple signal strength samples from each access point, taking the high autocorrelation into account, to achieve better accuracy. Implementation of the technique in the Horus system shows that the average system accuracy is increased by more than 50%. Our results show that assuming independence of samples from the same access point can lead to degraded performance as the number of samples used in the estimation algorithm is increased, due to the wrong independence assumption. We also discuss how to incorporate the new technique with other algorithms for enhancing the performance of WLAN location determination systems.

We define techniques to compute energy-efficient paths, using the IEEE 802.11 fragmentation mechanism, within the framework of on-demand routing protocols. We focus on one specific on-demand routing protocol, namely the ad-hoc on-demand vector routing protocol (AODV), and show how it should be adapted to compute energy-efficient paths. The choice of energy-efficient paths depends on link error rates on different wireless links, which in turn depend on channel noise. We show how our scheme accounts for such channel characteristics in computing such paths and how it exploits the IEEE 802.11 fragmentation mechanism to generate optimum energy-efficient paths. We perform a detailed study of the AODV protocol and our energy-efficient variants, under various noise and node mobility conditions. Our results show that our proposed variants of on-demand routing protocols can achieve orders of magnitude improvement in energy-efficiency of reliable data paths.

We study analytically the performance of the IEEE 802.11 DCF (distributed coordination function) for infrastructure networks in noisy environments. We show that using the standard binary exponential backoff (BEB) mechanism in noisy environments results in a poor throughput performance due to its inability to differentiate between the causes of unsuccessful packet transmissions and verify the analytical model using the ns-2 simulator. We propose an enhanced BEB mechanism that enhances IEEE 802.11 with a capability of differentiating between different types of unsuccessful transmissions. We study the proposed mechanism analytically, verify it using ns-2 and show that the new mechanism enhances the network performance by up to orders of magnitude with respect to the network error rates.

We present a WLAN location determination technique, the Joint Clustering technique, that uses: (1) signal strength probability distributions to address the noisy wireless channel, and (2) clustering of locations to reduce the computational cost of searching the radio map. The Joint Clustering technique reduces computational cost by more than an order of magnitude, compared to the current state of the art techniques, allowing non-centralized implementation on mobile clients. Results from 802.11-equipped iPAQ implementations show that the new technique gives user location to within 7 feet with over 90% accuracy.

Packet error in the IEEE 802.11 network is one source of performance degradation and its variability. Most of the previous works study how collision avoidance and hidden terminals affect the IEEE 802.11 performance metrics, such as probability of a collision and saturation throughput. In this paper we focus on the effect of packet errors on capacity and variability of the IEEE 802.11 MAC protocol. We develop a new analytical model, called p/sub e/-model, by extending the existing model (Tay and Chun's model) to incorporate packet error probability p/sub e/. With p/sub e/-model, we successfully analyze the capacity and variability of the IEEE 802.11 MAC protocol. The variability analysis shows that increasing packet error probability by /spl Delta/p/sub e/ has more effect on saturation throughput than adding 0.5 W /spl Delta/p/sub e/ stations, where W is the minimum contention window size. We also show the numerical validation of p/sub e/-model with the IEEE 802.11 MAC-level simulator.

We define energy-efficient broadband and multicast schemes for reliable communication in multi-hop wireless networks. Unlike previous techniques, the choice of neighbors in the broadband and multicast trees in these schemes, are based not only on the link distance, but also on the error rates associated with the link. Our schemes can be implemented using both positive and negative acknowledgement based reliable broadcast techniques in the link layer. Through simulations, we show that our scheme achieves up to 45% improvement over previous schemes on realistic 100-node network topologies. A positive acknowledgment based implementation is preferred. Our simulations show that the additional benefits of a positive acknowledgement based implementation is marginal (1-2%). Therefore a negative acknowledgement based implementation of our schemes is equally applicable in constructing energy-efficient reliable and multicast data delivery paths.

To limit the radio map size and the time required to build the radio map, current WLAN location determination system do not handle small-scale variations. This contributes to most of the estimation error in the current systems. We propose a general technique, the perturbation technique, to handle the small-scale variations problem. The system uses user history to detect small-scale variations and then perturbs the signal strength vector entries to overcome it. The results obtained show that the accuracy can be increased by more than 8%. Moreover, the worst-case error is enhanced by more than 60%. We also show that the perturbation technique can help in enhancing the accuracy due to temporal variations in case of change in the environment conditions, thus increasing the accuracy of the current WLAN location determination systems beyond their limits.

Clustered ILP processors are characterized by a large number of non-centralized on-chip resources grouped into clusters. Traditional code generation schemes for these processors consist of multiple phases for cluster assignment, register allocation and instruction scheduling. Most of these approaches need additional re-scheduling phases because they often do not impose finite resource constraints in all phases of code generation. These phase-ordered solutions have several drawbacks, resulting in the generation of poor performance code. Moreover the iterative/back-tracking algorithms used in some of these schemes have large turning times. In this paper we present CARS, a code generation framework for Clustered ILP processors, which combines the cluster assignment, register allocation, and instruction scheduling phases into a single code generation phase, thereby eliminating the problems associated with phase-ordered solutions. The CARS algorithm explicitly takes into account all the resource constraints at each cluster scheduling step to reduce spilling and to avoid iterative re-scheduling steps. We also present a new on-the-fly register allocation scheme developed for CARS. We describe an implementation of the proposed code generation framework and the results of a performance evaluation study using the SPEC95/2000 and MediaBench benchmarks.

Proposes a novel model to characterize the behavior of individual programs in the presence of cache memory. The model goes beyond the traditional hit/miss ratios often used in the current literature to describe program-cache interactions. Instead, it looks at the characteristics of the sequences of hits and misses during a program execution. The model includes several distributions that describe the hit and miss sequences. Several program characteristics which are otherwise not identified by the traditional models are discovered using our model. We then discuss how the model can be effectively used to tune the performance of a program, to allocate cache to a process, or to choose a cache architecture.

No abstract available.

We consider the schedulability-oriented replication problem of a set of periodic real-time tasks where each task can be decomposed into several modules and intermodule communications. The objective is to find an allocation in which there exists a feasible schedule for the given task set. In this paper, we adopt a communication model where the replication of modules is not for the sake of fault tolerance but for increasing the degree of schedulability. To solve the problem, we develop a replication technique and embed the technique in a simulated annealing algorithm. Experimental results show that such replication may lead to a higher degree of schedulability and obtain a feasible solution.

A simple experiment designed to capture the end-to-end behavior of the Internet is described. The measurements indicate that the IP level service provided in the network yields high losses, duplicates, and reorderings of packets. In addition, the round-trip transit delay varies significantly. These measurements indicate that the network may have several problems which still need to be analyzed in order to improve the efficiency of protocols and control mechanisms that it uses.>

A model for a virtual circuit in the form of a tandem of servers that process incoming packets using a FIFO (first-in, first-out) discipline is proposed. The service times are assumed to be known completely. These may differ from packet to packet and from server to server. The model permits a variety of buffer or transit time constraints to be incorporated into the model. Several results that help one to understand the transient behavior of a virtual circuit are presented. On the basis of these results, a number of schemes that may be used to determine the time when the next packet must be sent over the network are presented. Transit delay and throughput are used to evaluate a given schedule. Solutions are given for maximum throughput, minimum transit delay, and maximum throughput under transit delay constraints. It is expected that these results will have a substantial bearing on the study of congestion control policies in computer networks, particularly those based on predicting network behavior.>

The authors model a virtual circuit in a computer network as a sequence of servers in tandem. They explicitly take into account cross traffic at the servers from other virtual circuits. The analysis of the model leads them to propose a novel flow control scheme, which they term send-time control. A measure to evaluate the performance of flow control schemes, called the packet performance index, is proposed. They compare the send-time control scheme with the window-based flow control scheme of transmission control protocol (TCP) using simulation. The results obtained show that send-time control is superior to the window-based scheme.>

A model is given for developing application with fault-tolerance requirements and real-time constraints. Applications in this model are specified using computation graphs, in which vertices represent tasks and arcs represent precedence constraints. Tasks are replicated to provide required fault tolerance and ensure that a real-time application will meet its deadlines despite failures. The authors develop an analytical model to calculate the probability of successful execution of applications with task replications. They propose an efficient algorithm for the analysis of applications that are composed of subgraphs, each of which has a single source and a single sink. The results of the analysis can be used with information from allocation/scheduling to develop applications with desired timing and fault-tolerance requirements.>

Operating systems prototypes are becoming more attractive and more widespread because the more laborious and detailed work can be overlooked. The pseudo-implementation permits verification of principles, enhancing the studies of system properties through quick feedback. The authors present their experience in prototyping MARUTI, a distributed fault tolerant real-time operating system on top of UNIX. They report the actual implementation experience in developing the first version of such a prototype. They start by giving some motivation and background on prototyping, and describing the model they used. In the next section, they summarize the design of MARUTI. They describe their strategy of implementing objects as UNIX processes and the language extensions required. They report experience in creating the real-time operating system prototype. And present some future research topics.>

Maruti is a testbed for the design of time-driven hard real-time systems. It uses the technique of prescheduling, where the application is scheduled prior to execution and resources required by the application are reserved, in order to ensure that deadlines are met. A description is given of the features of MPL, a language for Maruti. MPL provides constructs for expressing time constraints, precedence relations, and synchronization directly in the programs. The MPL features are designed to facilitate prescheduling.>

In this paper we employ a deterministic analysis technique to characterize the dynamic queueing aspects of window protocols. The deterministic behavior of these protocols and the deterministic influence of the resources along the physical path are explicitly considered in the evaluation of path queue behavior. Transient and steady state queue behavior of fixed and sliding window protocols are investigated. We discover the existence of significant nonlinearities in the dynamics of queue activity.

A fork-join queue is considered as a typical model of parallel processing systems with arrival and departure synchronizations. An approach for obtaining the transient and the steady-state solutions of the fork-join queue in terms of the virtual waiting times, which can be used to obtain the response time and the delay between the fork and the join instants, is presented. With the restriction of the service time being the Erlangian distribution, the formulations result in a form of a series, the worth of which is in actually computing numerical results. The joint-state-occupancy probabilities can be easily deduced from the results. The approximate solutions in the steady state are presented for the cases where the interarrival time distributions are exponential and hyperexponential, and the service-time distributions are exponential and two-state Erlangian. The parallelism achievable with synchronization constraints is examined from the approximations.>

Abstmcf-The goal of checkpointing in database management systems is to save database slates on a separate secure device so that the database can be recovered when errors and fallures occur. Recently, the possibility of having a checkpointing mechanism whicb does not interfere with the transaction processing has been studied [4], 17. Users are allowed to submit transactions while the checkpointing is in prqres, and the transnctions are performed in the system concurrently with the checkpointing process. This property of noninterferelrc+ is highly desirable to real-time applications, where restricting transaction activity during the checkpointing operation is in many cases not feasible. In this paper, 8 new algorithm for checkpointing in distributed database systems is proposed and its correctness is proved, The practicality of the algorithm is discussed by analyzing the extra workload and the robustness of it with respect to site fallures.

The message complexity of decentralized commit protocols is studied. It is shown that O(kNN/sup 1/k/) messages are necessary if only k rounds of message interchanges are allowed. It is also shown that O(Nln N) is a message lower bound for any decentralized commit protocol. A class of decentralized commit protocols that need O(kNN/sup 1/k/) messages and use k rounds of message interchanges is proposed. If k=ln N, then a decentralized commit protocol that needs O(Nln N) messages only is obtained. The communication scheme is also used to derive some decentralized consensus protocols.>

An allocation scheme is proposed that accomplishes the hard real-time goal of guaranteeing a deadline satisfaction in case the job is accepted. In addition, the scheme supports fault-tolerance objectives in both damage containment and resiliency requirements. It does this in cooperation with a schedulability verification mechanism and with an object architecture in which for each object there exists a calendar that maintains the time of its execution. The scheme can be used for reallocation while increasing the resiliency.>

In this paper, we analyze the performance of a concurrency control algorithm for replicated database systems. We present a model of a distributed database system which provides a framework to study the performance of different concurrency control algorithms. We discuss performance criteria to evaluate different algorithms. We use the model to analyze the performance of an algorithm for concurrency control in replicated database systems. The technique used in analysis is iterative and approximate. We plot a set of performance measures for several values of the model parameters. The results of analysis are compared against a simulation study.

Decentralized consensus protocols are characterized by successive rounds of message interchanges. Protocols which achieve a consensus in one round of message interchange require O(N2) messages, whereNis the number of participants. A communication scheme based on finite projective planes is presented which requires only O(N√N) messages for each round. Using this communication scheme, decentralized consensus protocols which achieve a consensus within two rounds of message interchange are developed. The protocols are symmetric, and the communication scheme does not impose any hierarchical structure. The scheme is illustrated using blocking and nonblocking commit protocols, decentralized extrema finding, and computation of the sum function.

A variation of the tree structure interconnection network for the message switching multiprocessor system is presented in this correspondence. It mainly consists of four binary tree structures, pairs of which are touched by their leaf nodes; in addition, there are four nodes which interface with external environments. The proposed network is left-right and top-down symmetric and is planar. Every node in the interconnection network has the same number of degree, 3. There are multiple paths between any two nodes in the network. Results of the message traffic analysis of the network are presented.

An important analytic model of finite buffer systems is a multiclass single queue with typed servers. In the context of such a model, we address the problem of selecting an optimal buffer sharing policy. We show that with respect to weighted throughput, an optimal policy must be a stationary delayed resolution policy. An iterative procedure based upon the policy iteration method for Markov processes with rewards is used to efficiently search for the optimal delayed resolution policy for a given set of system parameters. A performance comparison of the optimal delayed resolution policy with other well-known buffer sharing policies is also provided.

A class of policies called stationary delayed resolution policies have been proposed recently for sharing finite number of buffers at a store-and-forward node in a message switching network [9]. It has been shown that with respect to the total weighted throughput these policies comprise the optimal class of policies. In this paper, we present methods to obtain an optimal policy from the class of stationary delayed resolution policies for given values of the parameters.

A dynamic control policy known as "threshold queueing" is defined for scheduling customers from a Poisson source on a set of two exponential servers with dissimilar service rates. The slower server is invoked in response to instantaneous system loading as measured by the length of the queue of waiting customers. In a threshold queueing policy, a specific queue length is identified as a "threshold," beyond which the slower server is invoked. The slower server remains busy until it completes service on a customer and the queue length is less than its invocation threshold. Markov chain analysis is employed to analyze the performance of the threshold queueing policy and to develop optimality criteria. It is shown that probabilistic control is sub-optimal to minimize the mean number of customers in the system. An approximation to the optimum policy is analyzed which is computationally simple and suffices for most operational applications.

The virtual waiting time technique is introduced as a solution to the problem of a controller distributing work to servers of different speeds. The servers are considered to be part of a distributed system without feedback. The virtual waiting time technique is shown to minimize the average completion time for a job distributed by the controller. The virtual waiting time technique does not depend on any arrival distribution and is applicable to any service time distribution. The performance of the technique is examined for different arrival and service time distributions.

In this paper we analyze the performance of two predominant ring architectures: the slotted ring and the token-controlled ring. First we describe each of the networks. Then we discuss the simulation models that we developed for them, being careful to point out the assumptions that were made about the networks and their operating environment. Finally we describe the experiments that were run using the simulation models and present their results.

The instruction sets of most contemporary, commercially available computers are designed to provide "general purpose" capabilities. In solving specific problems, the instruction sets of these computers often prove to be inefficient. With a dynamically microprogrammable machine this problem can be alleviated by letting the language processor 1) define a set of "machine" instructions better suited for the particular problem at hand and 2) generate the microprograms to interpret the newly defined instruction set.

Several models for line detection in noise are discussed, based on models for the ``simple'' and ``complex'' cells that have been found in the visual cortex. The possibility of obtaining experimental evidence for deciding among the models is briefly considered.

Queueing theoretic models of single and multi-processor computer systems have received wide attention in the computer science literature. Few of these models consider the effect of finite memory size of a machine and its impact on the memory scheduling problem. In an effort to formulate an analytical model for memory scheduling we propose four simple models and examine their characteristics using simulation. In this paper, we discuss some interesting results of these simulations.

This correspondence describes a sequential algorithm which generates the chain coded description of a line "parallel" to and at a fixed distance from another digital line. A few examples are presented along with a comparison with a parallel approach.

The concept of microprogramming has been changing with the development of hardware technology to facilitate dynamic microprogramming and the development of software technology to facilitate user microprogramming. An examination of the status of microprogramming systems leads to a discussion of the design and implementation characteristics for both the hardware and software aspects of microprogramming. The concept of microprogrammability is introduced to measure the facility with which a user can microprogram a machine. Discussing and evaluating contemporary machines and software that have been developed to effect user microprogramming reveals a variety of designs and implementations but also indicates directions for future research and development. Describing some of the contemporary applications of microprogramming indicates the potential for exploiting microprogramming in many areas. A comprehensive list of references serves as a guide to details of microprogramming concepts and recent developments.

The Bayesian learning scheme is computationally infeasible for most of the unsupervised learning problems. This paper suggests a learning scheme, "learning with a probabilistic teacher," which works with unclassified samples and is computationally feasible for many practical problems. In this scheme a sample is probabilistically assigned with a class with appropriate probabilities computed using all the information available: Then the sample is used in learning the parameter values given this assignment of the class. The convergence of the scheme is established and a comparison with the best linear estimator is presented.