Mobile platforms make use of dynamic voltage and frequency scaling (DVFS) to trade off runtime performance and power consumption for their systems-on-chip (SoCs). State-of-the-art governors in the OS use application-based characteristics to control the SoC's DVFS settings for CPU cores, as well as the GPU in some SoCs. Through experimental characterization of real-world mobile platforms, we find that key SoC components have a complex relationship with one another, which directly affects their performance and power usage. This relationship is dependent on the architecture of the SoC as it is caused by the interaction of processing elements such as the CPU and GPU through a shared main memory. Unfortunately, existing application-oriented governors do not explicitly capture this design-induced relationship.

Actors are lightweight reactive processes that communicate by asynchronous message-passing. Actors address common problems like concurrency control and fault tolerance, but resource management remains challenging: in all four of the most popular actor frameworks (Pekko, Akka, Erlang, and Elixir) programmers must explicitly kill actors to free up resources. To simplify resource management, researchers have devised actor garbage collectors (actor GCs) that monitor the application and detect when actors are safe to kill. However, existing actor GCs are impractical for distributed systems where the network is unreliable and nodes can fail. The simplest actor GCs do not collect cyclic garbage, whereas more sophisticated actor GCs are not fault-recovering : dropped messages and crashed nodes can cause actors to become garbage that never gets collected. We present Conflict-free Replicated Garbage Collection (CRGC): the first fault-recovering cyclic actor GC. In CRGC, actors and nodes record information locally and broadcast updates to the garbage collectors running on each node. CRGC does not require locks, explicit memory barriers, or any assumptions about message delivery order, except for reliable FIFO channels from actors to their local garbage collector. Moreover, CRGC is simple: we concisely present its operational semantics, which has been formalized in TLA + , and prove both soundness (non-garbage actors are never killed) and completeness (all garbage actors are eventually killed, under reasonable assumptions). We also present a preliminary implementation in Apache Pekko and measure its performance using two actor benchmark suites. Our results show the performance overhead of CRGC is competitive with simpler approaches like weighted reference counting, while also being much more powerful.

Rapid detection and mitigation of issues that impact performance and reliability are paramount for large-scale online services. For real-time detection of such issues, datacenter operators use a stream processor and analyze streams of monitoring data collected from servers (referred to as data source nodes) and their hosted services. The timely processing of incoming streams requires the network to transfer massive amounts of data, and significant compute resources to process it. These factors often create bottlenecks for stream analytics. To help overcome these bottlenecks, current monitoring systems employ near-data processing by either computing an optimal query partition based on a cost model or using model-agnostic heuristics. Optimal partitioning is computationally expensive, while model-agnostic heuristics are iterative and search over a large solution space. We combine these approaches by using model-agnostic heuristics to improve the partitioning solution from a model-based heuristic. Moreover, current systems use operator-level partitioning: if a data source does not have sufficient resources to execute an operator on all records, the operator is executed only on the stream processor. Instead, we perform data-level partitioning—i.e., we allow an operator to be executed both on a stream processor and data sources. We implement our algorithm in a system called Jarvis, which enables quick adaptation to dynamic resource conditions. Our evaluation on a diverse set of monitoring workloads suggests that Jarvis converges to a stable query partition within seconds of a change in node resource conditions. Compared to current partitioning strategies, Jarvis handles up to 75% more data sources while improving throughput in resource-constrained scenarios by 1.2-4.4×.

Automatic garbage collection (GC) prevents certain kinds of bugs and reduces programming overhead. GC techniques for sequential programs are based on reachability analysis. However, testing reachability from a root set is inadequate for determining whether an actor is garbage: Observe that an unreachable actor may send a message to a reachable actor. Instead, it is sufficient to check termination (sometimes also called quiescence): an actor is terminated if it is not currently processing a message and cannot receive a message in the future. Moreover, many actor frameworks provide all actors with access to file I/O or external storage; without inspecting an actor's internal code, it is necessary to check that the actor has terminated to ensure that it may be garbage collected in these frameworks. Previous algorithms to detect actor garbage require coordination mechanisms such as causal message delivery or nonlocal monitoring of actors for mutation. Such coordination mechanisms adversely affect concurrency and are therefore expensive in distributed systems. We present a low-overhead deferred reference listing technique (called DRL) for termination detection in actor systems. DRL is based on asynchronous local snapshots and message-passing between actors. This enables a decentralized implementation and transient network partition tolerance. The paper provides a formal description of DRL, shows that all actors identified as garbage have indeed terminated (safety), and that all terminated actors--under certain reasonable assumptions--will eventually be identified (liveness).

Automatic garbage collection (GC) prevents certain kinds of bugs and reduces programming overhead. GC techniques for sequential programs are based on reachability analysis. However, testing reachability from a root set is inadequate for determining whether an actor is garbage because an unreachable actor may send a message to a reachable actor. Instead, it is sufficient to check termination (sometimes also called quiescence): an actor is terminated if it is not currently processing a message and cannot receive a message in the future. Moreover, many actor frameworks provide all actors with access to file I/O or external storage; without inspecting an actor’s internal code, it is necessary to check that the actor has terminated to ensure that it may be garbage collected in these frameworks. Previous algorithms to detect actor garbage require coordination mechanisms such as causal message delivery or nonlocal monitoring of actors for mutation. Such coordination mechanisms adversely affect concurrency and are therefore expensive in distributed systems. We present a low-overhead reference listing technique (called DRL) for termination detection in actor systems. DRL is based on asynchronous local snapshots and message-passing between actors. This enables a decentralized implementation and transient network partition tolerance. The paper provides a formal description of DRL, shows that all actors identified as garbage have indeed terminated (safety), and that all terminated actors - under certain reasonable assumptions - will eventually be identified (liveness).

Internet of Things (IoT) applications generate massive amounts of real-time streaming data. IoT data owners strive to make predictions/inferences from these large streams of data often through applying machine learning, and image processing operations. A typical deployment of such applications includes edge devices to provide processing/storage operations closer to the location where the streaming data is captured. An important challenge for IoT applications is deciding which operations to execute on an edge device and which operations should be carried out in the cloud. In this paper, we propose a scalable dynamic programming algorithm called DROPLET, to partition operations in IoT applications across shared edge and cloud resources, while minimizing completion time of the end-to-end operations. We evaluate DROPLET using three real-world applications. Our results show that DROPLET finds a partitioning of operations having overall completion time within 4% of the optimum for these applications. It also scales to thousands of operations and outperforms closest heuristics in the literature, by being 10 times faster in running time while finding partitioning of operations with total completion time that is 20% better for the large applications that we simulated. We analyze DROPLET to show that it scales with total number of operations in log-linear time.

This paper addresses the problem of targeted test generation for actor systems. Specifically, we propose a method to support generation of system-level tests to cover a given code location in an actor system. The test generation method consists of two phases. First, static analysis is used to construct an abstraction of an entire actor system in terms of a message flow graph (MFG). An MFG captures potential actor interactions that are defined in a program. Second, a backwards symbolic execution (BSE) from a target location to an "entry point" of the actor system is performed. BSE uses the MFG constructed in the first phase of our targeted test generation method to guide execution across actors. Because concurrency leads to a huge search space which can potentially be explored through BSE, we prune the search space by using two heuristics combined with a feedback-directed technique. We implement our method in Tap, a tool for Java Akka programs, and evaluate Tap on the Savina benchmarks as well as four open source projects. Our evaluation shows that the Tap achieves a relatively high target coverage (78% on 1,000 targets) and detects six previously unreported bugs in the subjects.

With the popularity of smart phones and the development of mobile computing, indoor positioning services have triggered large scale of technology innovation and commercial cooperation. In the field of Wi-Fi based fingerprinting positioning system, for one thing, we deploy space division method based on Random Forest for dividing the fingerprinting radio map into sub regions freely and classifying candidate points accurately. For another thing, we propose a dimension reduction method, which integrates Maximum Likelihood Estimation for estimating intrinsic dimensionality and Kernel Principal Component Analysis for feature extraction, to tremendously reduce the size of a radio map, thereby saving terminal storage and alleviating error margin. Compared with linear feature extraction methods and manifold learning techniques, the proposed method shows a better performance in low dimension. The experimental results demonstrate that the proposed indoor positioning system, which is based on the given space division and dimension reduction techniques, could achieve 98% space division accuracy, 85% confidence probability with 2m positioning error and reduce 74% size of the radio map in addition to its noise suppression ability.

The fast growth of cloud applications highlights the requirement of appropriate security controls to restrict access to shared resources limited to authorized users. Existing authorization systems are not primarily designed for cloud environments and do not provide the required flexibility, adaptability, elasticity, scalability, or fine-grainedness of cloud applications. This paper outlines an ongoing effort in development of a flexible fine-grained access control system for modern cloud-based applications. Modern cloud applications are distinctive in that the required authorization rules are defined by the organizations owning data and resources, before the application logic can be developed by their programmers. Although this simplifies cloud application development and provides flexibility and adaptability to potential future policy changes, it highlights the need for an adaptive flexible authorization system.

Actor programming languages provide the kind of inherent parallelism that is needed for building applications in the mobile cloud. This is because the Actor model provides encapsulation (isolation of local state), fair scheduling, location transparency, and locality of reference. These properties facilitate building secure, scalable concurrent systems. Not surprisingly, very large-scale applications such as Facebook chat service and Twitter have been written in actor languages. The paper introduces the basics of the actor model and gives a high-level overview of the problem of coordination in actor systems. It then describes several novel methods for reasoning about concurrent systems that are both effective and scalable.

Knowing inputs that cover a specific branch or statement in a program is useful for debugging and regression testing. Symbolic backward execution (SBE) is a natural approach to find such targeted inputs. However, SBE struggles with complicated arithmetic, external method calls, and data-dependent loops that occur in many real-world programs. We propose symcretic execution, a novel combination of SBE and concrete forward execution that can efficiently find targeted inputs despite these challenges. An evaluation of our approach on a range of test cases shows that symcretic execution finds inputs in more cases than concolic testing tools while exploring fewer path segments. Integration of our approach will allow test generation tools to fill coverage gaps and static bug detectors to verify candidate bugs with concrete test cases.

Test input generators using symbolic and concolic execution must solve path conditions to systematically explore a program and generate high coverage tests. However, path conditions may contain complicated arithmetic constraints that are infeasible to solve: a solver may be unavailable, solving may be computationally intractable, or the constraints may be undecidable. Existing test generators either simplify such constraints with concrete values to make them decidable, or rely on strong but incomplete constraint solvers. Unfortunately, simplification yields coarse approximations whose solutions rarely satisfy the original constraint. Moreover, constraint solvers cannot handle calls to native library methods. We show how a simple combination of linear constraint solving and heuristic search can overcome these limitations. We call this technique Concolic Walk. On a corpus of 11 programs, an instance of our Concolic Walk algorithm using tabu search generates tests with two- to three-times higher coverage than simplification-based tools while being up to five-times as efficient. Furthermore, our algorithm improves the coverage of two state-of-the-art test generators by 21% and 32%. Other concolic and symbolic testing tools could integrate our algorithm to solve complex path conditions without having to sacrifice any of their own capabilities, leading to higher overall coverage.

Atomic sets are a synchronization mechanism in which the programmer specifies the groups of data that must be accessed as a unit. The compiler can check this specification for consistency, detect deadlocks, and automatically add the primitives to prevent interleaved access. Atomic sets relieve the programmer from the burden of recognizing and pruning execution paths which lead to interleaved access, thereby reducing the potential for data races. However, manually converting programs from lock-based synchronization to atomic sets requires reasoning about the program's concurrency structure, which can be a challenge even for small programs. Our analysis eliminates the challenge by automating the reasoning. Our implementation of the analysis allowed us to derive the atomic sets for large code bases such as the Java collections framework in a matter of minutes. The analysis is based on execution traces; assuming all traces reflect intended behavior, our analysis enables safe concurrency by preventing unobserved interleavings which may harbor latent Heisenbugs.

Modeling and evaluating the performance of large-scale wireless sensor networks (WSNs) is a challenging problem. The traditional method for representing the global state of a system as a cross product of the states of individual nodes in the system results in a state space whose size is exponential in the number of nodes. We propose an alternative way of representing the global state of a system: namely, as a probability mass function (pmf) which represents the fraction of nodes in different states. A pmf corresponds to a point in a Euclidean space of possible pmf values, and the evolution of the state of a system is represented by trajectories in this Euclidean space. We propose a novel performance evaluation method that examines all pmf trajectories in a dense Euclidean space by exploring only finite relevant portions of the space. We call our method Euclidean model checking . Euclidean model checking is useful both in the design phase—where it can help determine system parameters based on a specification—and in the evaluation phase—where it can help verify performance properties of a system. We illustrate the utility of Euclidean model checking by using it to design a time difference of arrival (TDoA) distance measurement protocol and to evaluate the protocol's implementation on a 90-node WSN. To facilitate such performance evaluations, we provide a Markov model estimation method based on applying a standard statistical estimation technique to samples resulting from the execution of a system.

Saving energy is one of the principal challenges in wireless sensor networks. Dynamic voltage and frequency scaling (DVFS) is often used to reduce energy consumption in systems where sleep is not an option. We show that changing the CPU frequency introduces sudden changes in clock behavior, thereby affecting the time-keeping functionality. This anomalous phenomenon is observed in different sensor platforms and causes a loss of time synchronization among nodes that is unacceptable to applications such as structural health monitoring that require tightly synchronized clocks over extended periods. The paper provides experimental measurements of the clock value shift anomaly in three widely used wireless sensor platforms and its impact on clock synchronization costs. A general framework balancing the need to save energy against the need to keep clocks synchronized is developed. Our system is implemented and evaluated on a network of sensors deployed on a truss bridge and running a high-fidelity structural health monitoring application. Experimental measurements confirm the efficacy of the solution in saving energy while maintaining an acceptable level of synchronization.

Denial of service protection mechanisms usually require classifying malicious traffic, which can be difficult. Another approach is to price scarce resources. However, while congestion pricing has been suggested as a way to combat DoS attacks, it has not been shown quantitatively how much damage a malicious player could cause to the utility of benign participants. In this paper, we quantify the protection that congestion pricing affords against DoS attacks, even for powerful attackers that can control their packets' routes. Specifically, we model the limits on the resources available to the attackers in three different ways and, in each case, quantify the maximum amount of damage they can cause as a function of their resource bounds. In addition, we show that congestion pricing is provably superior to fair queueing in attack resilience.

For a given algorithm, the energy consumed in executing the algorithm has a nonlinear relationship with performance. In case of parallel algorithms, energy use and performance are functions of the structure of the algorithm. We define the asymptotic energy complexity of algorithms which models the minimum energy required to execute a parallel algorithm for a given execution time as a function of input size. Our methodology provides us with a way of comparing the orders of (minimal) energy required for different algorithms and can be used to define energy complexity classes of parallel algorithms.

One of the more popular paradigms for concurrent programming is the Actor model of message passing; it has been adopted in one form or another by a number of languages and frameworks. By avoiding a shared local state and instead relying on message passing, the Actor model facilitates modular programming. An important challenge for message passing languages is to transmit messages efficiently. This requires retaining the pass-by-value semantics of messages while avoiding making a deep copy on sequential or shared memory multicore processors. A key observation is that many messages have an ownership transfer semantics; such messages can be sent efficiently using pointers without introducing shared state between concurrent objects. We propose a conservative static analysis algorithm which infers if the content of a message is compatible with an ownership transfer semantics. Our tool, called SOTER (for Safe Ownership Transfer enablER) transforms the program to avoid the cost of copying the contents of a message whenever it can infer the content obeys the ownership transfer semantics. Experiments using a range of programs suggest that our conservative static analysis method is usually able to infer ownership transfer. Performance results demonstrate that the transformed programs execute up to an order of magnitude faster than the original programs.

We propose a new probabilistic temporal logic, iLTL, which captures properties of systems whose state can be represented by probability mass functions (pmfs). Using iLTL, we can specify reachability to a state (i.e., a pmf), as well as properties representing the aggregate (expected) behavior of a system. We then consider a class of systems whose transitions are governed by a Markov Chain-in this case, the set of states a system may be in is specified by the transitions of pmfs from all potential initial states to the final state. We then provide a model checking algorithm to check iLTL properties of such systems. Unlike existing model checking techniques, which either compute the portions of the computational paths that satisfy a specification or evaluate properties along a single path of pmf transitions, our model checking technique enables us to do a complete analysis on the expected behaviors of large-scale systems. Desirable system parameters may also be found as a counterexample of a negated goal. Finally, we illustrate the usefulness of iLTL model checking by means of two examples: assessing software reliability and ensuring the results of administering a drug.

This paper presents Basset, a tool for systematic testing of JVM-based actor programs. The actor programming model offers a promising approach for developing reliable concurrent and distributed systems. Since the actor model is based on message passing and disallows shared state, it avoids some of the problems inherent in shared-memory programming, e.g., low-level dataraces involving access to shared data. However, actor programs can still have bugs that result from incorrect orders of messages among actors or processing of messages by individual actors. To systematically test an actor program, it is necessary to explore different message delivery schedules that might occur during execution. Basset facilitates such exploration and provides a generic platform that can support actor systems that compile to Java bytecode. Our current implementation of Basset supports testing of programs developed using the ActorFoundry library and the Scala programming language.

Energy consumption by computer systems has emerged as an important concern. However, the energy consumed in executing an algorithm cannot be inferred from its performance alone: it must be modeled explicitly. This paper analyzes energy consumption of parallel algorithms executed on shared memory multicore processors. Specifically, we develop a methodology to evaluate how energy consumption of a given parallel algorithm changes as the number of cores and their frequency is varied. We use this analysis to establish the optimal number of cores to minimize the energy consumed by the execution of a parallel algorithm for a specific problem size while satisfying a given performance requirement. We study the sensitivity of our analysis to changes in parameters such as the ratio of the power consumed by a computation step versus the power consumed in accessing memory. The results show that the relation between the problem size and the optimal number of cores is relatively unaffected for a wide range of these parameters.

The process of determining the physical locations of nodes in a wireless sensor network is known as localization . Self-localization is critical for large-scale sensor networks, because manual or assisted localization is often impractical due to time requirements, economic constraints, or inherent limitations of the deployment scenarios. We propose scalable solutions for reliably localizing wireless sensor networks in environments conducive to several types of ranging errors. We follow a hybrid hardware-software approach for acoustic ranging or radio interferometry to acquire internode distance measurements, and a resilient self-localization algorithm to compute the node location estimates. The acoustic ranging method improves on previous work, extending the practical measurement range up to 35 m in grassy outdoor environments, achieving a distance-invariant median measurement error of about 1% (33 cm). The localization algorithm is based on least-squares scaling with soft constraints. Empirical evaluation using ranging results obtained from sensor network field experiments and simulations confirms that our approach is more resilient than multidimensional scaling (MDS) algorithms against large-magnitude ranging errors and sparse range measurements: conditions that are common in large-scale outdoor sensor network deployments.

This paper analyzes energy characteristics of parallel algorithms executed on scalable multicore processors. Specifically, we provide a methodology for evaluating energy scalability of parallel algorithms while satisfying performance requirements. Four parallel algorithms are analyzed to illustrate our method. We study the sensitivity of our analysis to changes in parameters such as the ratio of power required for computation versus power required for communication. The results suggest that power and performance scalability of a parallel algorithm can be quite different. Our method can be used to determine how many cores to use in order to minimize energy consumption.

The actor programming model offers a promising model for developing reliable parallel and distributed code. Actors provide flexibility and scalability: local execution may be interleaved, and distributed nodes may operate asynchronously. The resulting nondeterminism is captured by nondeterministic processing of messages. To automate testing, researchers have developed several tools tailored to specific actor systems. As actor languages and libraries continue to evolve, such tools have to be reimplemented. Because many actor systems are compiled to Java bytecode, we have developed Basset, a general framework for testing actor systems compiled to Java bytecode. We illustrate Basset by instantiating it for the Scala programming language and for the ActorFoundry library for Java. Our implementation builds on Java PathFinder, a widely used model checker for Java. Experiments show that Basset can effectively explore executions of actor programs; e.g., it discovered a previously unknown bug in a Scala application.

Seamless information processing is gradually being integrated into daily human activities by creating a ubiquitous computing environment. Such information processing requires continuous access to the profiles of users so that the environment can act based on users' preferences. In this paper, we present a design of an experimental study of an agent-based approach to control resource consumption in a ubiquitous environment. A key idea is to explore whether it is feasible to use a mechanism that may help preserve inhabitants' privacy while at the same time provide a smart environment which resolves conflicts based on the preferences of the inhabitants. Experiments will be based on Bosthan, an agent-based simulator for smart spaces that is currently under development. Bosthan can simulate smart environments to investigate and evaluate different ubiquitous applications.

We develop a localization algorithm based on global environmental events observed by a sensor network. Examples of such events include the sound of thunder, the shades of moving clouds, or the vibrations in seismic data. Because our localization method does not generate signals for distance measurements, it saves energy. In fact, the algorithm may use existing sensor recordings to determine the locations of nodes at which the recordings were taken. Moreover, the method does not accumulate errors, making it also effective for large and sparse sensor networks. The localization uses time synchronization; we provide an algorithm to compensate for clock synchronization errors. Versions for both two dimensional and three dimensional localization of the algorithm are presented. Simulation results suggest that the algorithm can provide a high degree of accuracy when many events are recorded.

A compositional method for estimating software reliability of many threaded programs is developed. The method uses estimates of the reliability of individual modules and the probability of transitions between the modules to estimate the reliability of a program in terms of its current state. The reliability of a program is expressed using iLTL, a probabilistic linear temporal logic whose atomic propositions are linear inequalities about transitions of the probability mass function of a discrete time Markov chain. We then use a Markov reward model to estimate software reliability. The technique is illustrated in terms of an example.

Violations of a number of common safety properties of multithreaded programs - such as atomicity and absence of dataraces - cannot be observed by looking at the linear execution trace. We characterize a class of such properties, called robust properties, and define a simple but expressive epistemic logic to specify them. We then develop an efficient algorithm to automatically monitor and predict violations of robust safety properties. Our algorithm is based on capturing the causal structure of a computation through a mechanism similar to vector clock updates. The algorithm automatically synthesizes decentralized monitors to evaluate the information at each thread and to detect and predict safety violations. Based on this approach, a tool named DAME has been developed and evaluated on some simple examples.

We describe the problem of data dissemination in stream-oriented applications where the required filter is a function of the current state. We call such functions dynamic filters. A state aware data dissemination network (SA-DDN) is proposed to support dynamic filters. Two approaches single-level filtering (SF) and multilevel filter decomposition (MFD) are proposed to facilitate the data dissemination. We show how MFD improves performance over SF. We then describe a realization of SA-DDN on top of an improved bi-directional Chord overlay with a built-in multicast mechanism. An application of stock price monitoring is implemented based on SA-DDN and real life stock quotes are collected to demonstrate the feasibility of our system. Extensive simulations are performed to compare the performance of both approaches and provide insight into the advantages of MFD

The process of computing the physical locations of nodes in a wireless sensor network is known as localization. Self-localization is critical for large-scale sensor networks because manual or assisted localization is often impractical due to time requirements, economic constraints or inherent limitations of deployment scenarios. We have developed a service for reliably localizing wireless sensor networks in environments conducive to ranging errors by using a custom hardware-software solution for acoustic ranging and a family of self-localization algorithms. The ranging solution improves on previous work, extending the practical measurement range threefold (20-30m) while maintaining a distance-invariant median measurement error of about 1% of maximum range (33cm). The localization scheme is based on least squares scaling with soft constraints. Evaluation using ranging results obtained from sensor network field experiments shows that the localization scheme is resilient against large-magnitude ranging errors and sparse range measurements, both of which are common in large-scale outdoor sensor network deployments.

The effectiveness of automated system management is dependent on the domain-specific information that is encoded within the management framework. Existing approaches for defining the domain knowledge are categorized into white-box and black-box approaches, each of which has limitations. White-box approaches define detailed formulas for system behavior, and are limited by excessive complexity and brittleness of the information. On the other hand, black-box techniques gather domain knowledge by monitoring the system; they are error-prone and require an infeasible number of iterations to converge in real-world systems. Monitormining is a gray-box approach for creating domain knowledge in automated system management; it combines simple designer-defined specifications with the information gathered using machine learning. The designer specifications enumerate input parameters for the system behavior functions, while regression techniques (such as neural networks, support vector machines) are used to derive the mathematical function that relates these parameters. These functions are constantly refined at run-time, by periodically invoking regression on the newly monitored data. Monitormining has the advantage of reduced complexity of the designer specifications, better accuracy of regression functions due to a reduced parameter set, and self-evolving with the changes in the system. Our initial experimental results of applying monitormining are quite promising.

We propose localized and decentralized protocols to construct and maintain an underlay for sensor networks. An underlay lies in between overlay operations (e.g., data indexing, multicast, etc.) and the sensor network itself. Specifically, an underlay bridges the gap between (a) the unreliability of sensor nodes and communication and availability of only approximate location knowledge, and (b) the maintenance of a virtual geography-based naming structure that is required by several overlay operations. Our underlay creates a coarse naming scheme based on approximate location knowledge, and then maintains it in an efficient and scalable manner. The underlay naming can be used to specify arbitrary regions. The overlay operations that can be executed on the underlay include routing, aggregation, multicast, data indexing, etc. These overlay operations could be region-based. The proposed underlay maintenance protocols are robust, localized (hence scalable), energy and message efficient, have low convergence times, and provide tuning knobs to trade convergence time with overhead and with underlay uniformity. The maintenance protocols are mathematically analyzed by characterizing them as differential equation systems. We present microbenchmark results from a NesC implementation, and results from a large-scale simulation of a Java implementation. The latter experiments also show how routing using the underlay would perform

A number of solutions have been proposed to address the free-riding problem in peer-to-peer file sharing systems. The solutions are either imperfect-they allow some users to cheat the system with malicious behavior, or expensive-they require human intervention, require servers, or incur high mental transaction costs. The authors proposed a method to address these weaknesses. Specifically, a utility function was introduced to capture contributions made by a user and an auditing scheme to ensure the integrity of a utility function's values. The method enabled to reduce cheating by a malicious peer: it is shown that this approach can efficiently detect malicious peers with a probability over 98%.

In unit testing, a program is decomposed into units which are collections of functions. A part of unit can be tested by generating inputs for a single entry function. The entry function may contain pointer arguments, in which case the inputs to the unit are memory graphs. The paper addresses the problem of automating unit testing with memory graphs as inputs. The approach used builds on previous work combining symbolic and concrete execution, and more specifically, using such a combination to generate test inputs to explore all feasible execution paths. The current work develops a method to represent and track constraints that capture the behavior of a symbolic execution of a unit with memory graphs as inputs. Moreover, an efficient constraint solver is proposed to facilitate incremental generation of such test inputs. Finally, CUTE, a tool implementing the method is described together with the results of applying CUTE to real-world examples of C code.

We describe an efficient decentralized monitoring algorithm that monitors a distributed program's execution to check for violations of safety properties. The monitoring is based on formulae written in PT-DTL, a variant of past time linear temporal logic that we define. PT-DTL is suitable for expressing temporal properties of distributed systems. Specifically, the formulae of PT-DTL are relative to a particular process and are interpreted over a projection of the trace of global states that represents what that process is aware of. A formula relative to one process may refer to other processes' local states through remote expressions and remote formulae. In order to correctly evaluate remote expressions, we introduce the notion of Knowledge Vector and provide an algorithm which keeps a process aware of other processes' local states that can affect the validity of a monitored PT-DTL formula. Both the logic and the monitoring algorithm are illustrated through a number of examples. Finally, we describe our implementation of the algorithm in a tool called DIANA.

Summary form only given. Cellular automata (CA) are an abstract model of fine-grain parallelism: the individual node update operations are rather simple, and therefore comparable to the basic operations of the computer hardware, yet the power of the model stems from the interaction and synergy of these simple local node computations that can often generate highly complex global behavior. In classical CA, all the nodes execute their operations in parallel, that is, (logically) simultaneously. We consider herein the sequential version of CA, or SCA, and compare and contrast SCA with the classical, parallel CA. We show that there are 1D CA with simple nonlinear node state update rules that cannot be simulated by any comparable SCA, irrespective of the node update ordering. While the result is trivial if one considers a single automaton's computations, we find this property quite interesting and having important implications when applied to all possible computations of entire nontrivial classes of CA (SCA). We also share some thoughts on how to extend the results herein, and, in particular, we try to motivate the study of genuinely asynchronous cellular automata.

Systems that provide distributed multimedia services are subject to constant evolution; customizable middleware is required to effectively manage this change. Middleware services for resource management execute concurrently with each other, and with application activities, and can, therefore, potentially interfere with each other. To ensure cost-effective QoS in distributed multimedia systems, safe composability of resource management services is essential. In this article, we present a meta-architectural framework, the Two-Level Actor Model (TLAM) for customizable QoS-based middleware, based on the actor model of concurrent active objects. Using TLAM, a semantic model for specifying and reasoning about components of open distributed systems, we show how a QoS brokerage service can be used to coordinate multimedia resource management services in a safe, flexible, and efficient manner. In particular, we show a system in which the multimedia actor behaviors satisfy the specified requirements and provide the required multimedia service. The behavior specification leaves open the possibility of a variety of algorithms for resource management. Furthermore, constraints are identified that are sufficient to guarantee noninterference among the multiple broker resource management services, as well as providing guidelines for the safe composition of additional services.

We present a novel method for tracking the movement of people or vehicles in open outdoor environments using sensor networks. Unlike other sensor network-based methods, which depend on determining distance to the target or the angle of arrival of the signal, our cooperative tracking approach requires only that a sensor be able to determine if an object is somewhere within the maximum detection range of the sensor. We propose cooperative tracking as a method for tracking moving objects and extrapolating their paths in the short term. By combining data from neighboring sensors, this approach enables tracking with a resolution higher than that of the individual sensors being used. We employ statistical estimation and approximation techniques to further increase the tracking precision, and to enable the system to exploit the tradeoff between accuracy and timeliness of the results. We analyze the behavior of the cooperative tracking algorithm through simulation, focusing on the effects of approximation techniques on the quality of estimates achieved. This work focuses on acoustic tracking, however the presented methodology is applicable to any sensing modality where the sensing range is relatively uniform.

Foundational and scalable techniques for runtime safety analysis of multithreaded programs are explored in this paper. A technique based on vector clocks to extract the causal dependency order on state updates from a running multithreaded program is presented, together with algorithms to analyze a multithreaded computation against safety properties expressed using temporal logics. A prototype tool implementing our techniques, is also presented, together with examples where it can predict safety errors in multithreaded programs from successful executions of those programs. This tool is called Java MultiPathExplorer (JMPaX), and available for download on the web. To the best of our knowledge, JMPaX is the first tool of its kind.

1 This work is supported in part by Defense Advanced Research Projects Agency (DARPA contract number F30602-00-2-0586) Abstract Researchers have long focused on dramatically increasing the size of problems that can be solved by exploiting massive parallelism. Considerable work was done on special purpose hardware for building concurrent computers and parallelizing conventional sequential programs. On the other hand, models such as Actors were inspired by the idea that using diversity and parallelism, a community of agents could collectively solve much larger problems than sequential programs. Early work on the Actor model studied the semantics of concurrency and distribution. Later work provided novel ways of implementing actors for efficiently executing and migrating them [1].

We present a coordination language and its semantics for specification and implementation of object-oriented real-time systems. Real-time systems operate under real-time constraints, and our language supports expression thereof. In our language, a system is modeled by two separate but complementary descriptions: A collection of objects define the system's structure and functional behavior and a set of interaction constraints define how these objects may interact. Our language thereby supports development of real-time systems by enabling objects build in isolation or re-used from other systems to be composed via interaction constraints. We use the Actor model to describe objects and the concept of real-time synchronizers to describe interaction constraints. Our model is accompanied by a formal semantics that precisely defines what real-time constraints means, and what constitutes a program's correct real-time behaviors. The semantics defines how the system may evolve in the real-time domain, and what progress guarantees the language makes. We briefly discuss implementation problems and potential solutions.

Current middleware solutions such as CORBA and Java's RMI emphasize compositional design by separating functional aspects of a system (e.g. objects) from the mechanisms used for interaction (e.g. remote procedure call through stubs and skeletons). While this is an effective solution for handling distributed interactions, higher-level requirements such as heterogeneity, availability, and adaptability require policies for resource management as well as interaction. We describe the Distributed Connection Language (dcl): an architecture description language based on the Actor model of distributed objects. System components and the policies which govern an architecture are specified as encapsulated groups of actors. Composition operators are used to build connections between components as well as customize their behavior. This customization is realized using a meta-architecture. We describe the syntax and semantics of dcl, and illustrate the language by way of several examples.

No abstract available.

We present an actor language which is an extension of a simple functional language, and provide an operational semantics for this extension. Actor configurations represent open distributed systems, by which we mean that the specification of an actor system explicitly takes into account the interface with external components. We study the composability of such systems. We define and study various notions of testing equivalence on actor expressions and configurations. The model we develop provides fairness. An important result is that the three forms of equivalence, namely, convex, must, and may equivalences, collapse to two in the presence of fairness. We further develop methods for proving laws of equivalence and provide example proofs to illustrate our methodology.

Concurrent call/return communication (CCRC) allows programmers to conveniently express a communication pattern where a sender invokes a remote operation and uses the result to continue its computation. The blocking semantics requires context switching for efficient utilization of computation resource. We present a compilation technique which allows programmers to use CCRC with the cost of non-blocking asynchronous communication plus minimum context switch cost. The technique transforms CCRCs into non-blocking asynchronous sends and encapsulates continuations into separate objects. A data flow analysis is used to guarantee that only necessary context is cached in continuation objects.

We describe the design of a runtime system for a fine-grained concurrent object-oriented (actor) language and its performance. The runtime system provides considerable flexibility to users; specifically, it supports location transparency, actor creation and dynamic placement, and migration. The runtime system includes an efficient distributed name server, a latency hiding scheme for remote actor creation, and a compiler-controlled intra-node scheduling mechanism for local messages and dynamic load balancing. Our preliminary evaluation results suggest that the efficiency that is lost by the greater flexibility of actors can be restored by an efficient runtime system which provides an open interface that can be used by a compiler to allow optimizations. On several standard algorithms, the performance results for our system are comparable to efficient C implementations.

To optimize performance in a fault-tolerant distributed system, it is often necessary to enforce different failure semantics for different components. By choosing a custom set of failure semantics for each component and then by enforcing the semantics with a minimal set of protocols for a particular architecture, performance may be maximized while ensuring the desired system behavior. We have developed DIL, a language for specifying, on a per-component basis, protocols that transparently enforce failure semantics. These protocols may be reused with arbitrary components, allowing the development of a library of protocols.>

We present a new programming paradigm called ActorSpace. ActorSpace provides a new communication model based on destination patterns. An actorSpace is a computationally passive container of actors which acts as a context for matching patterns. Patterns are matched against listed attributes of actors and actorSpaces that are visible in the actorSpace. Both visibility and attributes are dynamic. Messages may be sent to one or all members of a group defined by a pattern. The paradigm provides powerful support for component-based construction of massively parallel and distributed applications. In particular, it supports open interfaces to servers and pattern-directed access to software repositories.