Coordination services and protocols are critical components of distributed systems and are essential for providing consistency, fault tolerance, and scalability. However, due to the lack of standard benchmarking and evaluation tools for distributed coordination services, coordination service developers/researchers either use a NoSQL standard benchmark and omit evaluating consistency, distribution, and fault tolerance; or create their own ad-hoc microbenchmarks and skip comparability with other services. In this study, we analyze and compare the evaluation mechanisms for known and widely used consensus algorithms, distributed coordination services, and distributed applications built on top of these services. We identify the most important requirements of distributed coordination service benchmarking, such as the metrics and parameters for the evaluation of the performance, scalability, availability, and consistency of these systems. Finally, we discuss why the existing benchmarks fail to address the complex requirements of distributed coordination system evaluation.

MongoDB's distributed multi-document transactions protocol was designed and developed incrementally, building on WiredTiger, an existing single node multi-version storage engine that provided snapshot isolated key-value storage. This layered approach required meticulous management of concurrency control and timestamping mechanisms across system layers, complicated by intricate component interactions and a large evolving codebase. In this paper, we describe our experience using modular formal specification techniques to address this challenge. Our approach formally specifies the distributed transactions protocol and its interface with the underlying storage layer, allowing us to verify high level protocol properties while also formalizing the contract between these two components. This modular approach also enables an automated, model-based verification technique for testing conformance of the WiredTiger storage implementation to this interface. We use an explicit state model checker to automatically generate test cases from our storage model, which are then executed against the storage implementation, ensuring the implementation matches the interface relied upon by the transactions protocol. Our work highlights the value of formal modeling not only for verifying high-level protocol correctness but also for precisely defining and validating interactions with lower-level system components in an automated way. Beyond verifying key isolation properties, our specification also enabled us to formally analyze permissiveness- -how well the protocol maximizes concurrency within a given isolation level-a property not previously examined.

This paper describes BigBFT, a multi-leader Byzantine fault tolerance protocol that achieves high throughput and scalable consensus in blockchain systems. BigBFT achieves this by (1) enabling every node to be a leader that can propose and order the blocks in parallel, (2) piggybacking votes within rounds, (3) pipelining blocks across rounds, and (4) using only two communication steps to order blocks in the common case.BigBFT has an amortized communication cost of O(n) over n requests. We evaluate BigBFT’s performance both analytically, using back-of-the-envelope load formulas to construct a cost analysis, and also empirically by implementing it in our Pax-iBFT framework. Our evaluation compares BigBFT with PBFT, Tendermint, Streamlet, and Hotstuff under various workloads using deployments of 4 to 20 nodes. Our results show that BigBFT outperforms PBFT, Tendermint, Streamlet, and Hotstuff protocols either in terms of latency (by up to 40%) or in terms of throughput (by up to 190%).

Strongly consistent replication helps keep application logic simple and provides significant benefits for correctness and manageability. Unfortunately, the adoption of strongly-consistent replication protocols has been curbed due to their limited scalability and performance. To alleviate the leader bottleneck in strongly-consistent replication protocols, we introduce Pig, an in-protocol communication aggregation and piggybacking technique. Pig employs randomly selected nodes from follower subgroups to relay the leader's message to the rest of the followers in the subgroup, and to perform in-network aggregation of acknowledgments back from these followers. By randomly alternating the relay nodes across replication operations, Pig shields the relay nodes as well as the leader from becoming hotspots and improves throughput scalability. We showcase Pig in the context of classical Paxos protocols employed for strongly consistent replication by many cloud computing services and databases. We implement and evaluate PigPaxos, in comparison to Paxos and EPaxos protocols under various workloads over clusters of size 5 to 25 nodes. We show that the aggregation at the relay has little latency overhead, and PigPaxos can provide more than 3 folds improved throughput over Paxos and EPaxos with little latency deterioration. We support our experimental observations with the analytical modeling of the bottlenecks and show that the communication bottlenecks are minimized when employing only one randomly rotating relay node.

Summary Question answering is a fundamental problem for artificial intelligence research. State‐of‐the‐art question answering systems, such as search engines, can answer well‐formed factual questions. However, they fail on nonfactual and natural language queries. On the other hand, crowdsourcing leverages human intelligence to present solutions for problems, which are hard for computers. In the process of crowdsourcing, aggregating the responses from the crowd is a big challenge of itself. This work presents a model that integrates artificial intelligence with crowdsourcing to answer difficult natural language multiple choice questions. We build a crowdsourced mobile gaming experience for “Who wants to be a millionaire?” TV quiz show to test our methods. We use lightweight artificial intelligence models in aggregating the crowd responses. Our methods are able to answer even the hardest questions with very high accuracy. The experiment results suggest that building a super player for “Who wants to be a millionaire?” is feasible using our models. This study shows that facilitating crowdsourcing with artificial intelligence is an important tool for answering questions, which trouble state‐of‐the‐art question answering systems.

State machine replication protocols, like MultiPaxos and Raft, are a critical component of many distributed systems and databases. However, these protocols offer relatively low throughput due to several bottlenecked components. Numerous existing protocols fix different bottlenecks in isolation but fall short of a complete solution. When you fix one bottleneck, another arises. In this paper, we introduce compartmentalization, the first comprehensive technique to eliminate state machine replication bottlenecks. Compartmentalization involves decoupling individual bottlenecks into distinct components and scaling these components independently. Compartmentalization has two key strengths. First, compartmentalization leads to strong performance. In this paper, we demonstrate how to compartmentalize MultiPaxos to increase its throughput by 6× on a write-only workload and 16× on a mixed read-write workload. Unlike other approaches, we achieve this performance without the need for specialized hardware. Second, compartmentalization is a technique, not a protocol. Industry practitioners can apply compartmentalization to their protocols incrementally without having to adopt a completely new protocol.

WPaxos is a multileader Paxos protocol that provides low-latency and high-throughput consensus across wide-area network (WAN) deployments. WPaxos uses multileaders, and partitions the object-space among these multileaders. Unlike statically partitioned multiple Paxos deployments, WPaxos is able to adapt to the changing access locality through object stealing. Multiple concurrent leaders coinciding in different zones steal ownership of objects from each other using phase-1 of Paxos, and then use phase-2 to commit update-requests on these objects locally until they are stolen by other leaders. To achieve fast phase-2 commits, WPaxos adopts the flexible quorums idea in a novel manner, and appoints phase-2 acceptors to be close to their respective leaders. We implemented WPaxos and evaluated it over WAN deployments across 5 AWS regions. The dynamic partitioning of the objectspace and emphasis on zone-local commits allow WPaxos to significantly outperform both partitioned Paxos deployments and leaderless Paxos approaches.

Many distributed databases employ consensus protocols to ensure that data is replicated in a strongly-consistent manner on multiple machines despite failures and concurrency. Unfortunately, these protocols show widely varying performance under different network, workload, and deployment conditions, and no previous study offers a comprehensive dissection and comparison of their performance. To fill this gap, we study single-leader, multi-leader, hierarchical multi-leader, and leaderless (opportunistic leader) consensus protocols, and present a comprehensive evaluation of their performance in local area networks (LANs) and wide area networks (WANs). We take a two-pronged systematic approach. We present an analytic modeling of the protocols using queuing theory and show simulations under varying controlled parameters. To cross-validate the analytic model, we also present empirical results from our prototyping and evaluation framework, Paxi. We distill our findings to simple throughput and latency formulas over the most significant parameters. These formulas enable the developers to decide which category of protocols would be most suitable under given deployment conditions.

Retroscope is a comprehensive lightweight distributed monitoring tool that enables users to query and reconstruct past consistent global states of the system. Retroscope achieves this by augmenting the system with Hybrid Logical Clocks (HLC) and by streaming HLC-stamped event logs for storage and processing; these HLC timestamps are then used for constructing global (or nonlocal) snapshots upon request. Retroscope provides a rich querying language (RQL) to facilitate searching for global predicates across past consistent states. The search is performed by advancing through global states in small incremental steps, greatly reducing the amount of computation needed to construct consistent states. The Retroscope search algorithm is embarrassingly-parallel and can employ many worker processes (each processing up to 150,000 consistent snapshots per second) to handle a single query. We evaluate Retroscope's monitoring capabilities in two case studies: Chord and Apache ZooKeeper.

Storing data close to where it is used improves the performance of cloud applications. However, data access patterns change dynamically over time. Many datastores statically shard data making locality-adaptation difficult, and some provide limited capability for controlling the data-placement or migration. This leads to increased latency, reduced throughput, and expensive operations. To address this problem, we investigate the requirements for live data-migration and design four data-migration polices. Our policies use heuristics to determine the optimal data placement based on the access locality in the workload and load-balancing constraints. We show that even simple heuristics can be effective, and the topology-aware policies demonstrate overall better results with up to 70% latency improvement in medium locality workloads and nearly 95% improvement in workloads exhibiting very strong single-region access locality.

Hybrid vector clock(s) (HVC) provide a mechanism to combine the theory and practice of distributed systems. Improving on traditional vector clock(s) (VC), HVC utilizes synchronized physical clocks to reduce the size by focusing only on causality where the physical time associated with two events is within a given uncertainty window ε and letting physical clock alone determine the order of events that are outside the uncertainty window. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, ε: uncertainty window, 8: message delay, a: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a delay differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases. We show that for many practical applications and deployment environments in Amazon EC2, the size of HVC remains only as a couple entries and substantially less than n. Finally, although the analytical results rely on a specific communication pattern they are useful in evaluating size of HVC in different communication scenarios.

The proliferation of big data and big computing boosted the adoption of machine learning across many application domains. Several distributed machine learning platforms emerged recently. We investigate the architectural design of these distributed machine learning platforms, as the design decisions inevitably affect the performance, scalability, and availability of those platforms. We study Spark as a representative dataflow system, PMLS as a parameter- server system, and TensorFlow and MXNet as examples of more advanced dataflow systems. We take a distributed systems perspective, and analyze the communication and control bottlenecks for these approaches. We also consider fault-tolerance and ease-of-development in these platforms. In order to provide a quantitative evaluation, we evaluate the performance of these three systems with basic machine learning tasks: logistic regression, and an image classification example on the MNIST dataset.

Traditional coordination services for distributed applications do not scale well over wide-area networks (WAN): centralized coordination fails to scale with respect to the increasing distances in the WAN, and distributed coordination fails to scale with respect to the number of nodes involved. We argue that it is possible to achieve scalability over WAN using a hierarchical coordination architecture and a smart token migration mechanism, and lay down the foundation of a novel design for a flexible-consistent coordination framework, called WanKeeper. We implemented WanKeeper based on the ZooKeeper API and deployed it over WAN as a proof of concept. Our experimental results based on the Yahoo! Cloud Serving Benchmark (YCSB), Apache BookKeeper replicated log service, and the Shared Cloud-backed File System (SCFS) show that WanKeeper provides multiple folds improvement in write/update performance in WAN compared to ZooKeeper, while keeping the same read performance.

In order to take a consistent snapshot of a distributed system, it is necessary to collate and align local logs from each node to construct a pairwise concurrent cut. By leveraging NTP synchronized clocks, and augmenting them with logical clock causality information, Retroscope provides a lightweight solution for taking unplanned retrospective snapshots of past distributed system states. Instead of storing a multiversion copy of the entire system data, this is achieved efficiently by maintaining a configurable-size sliding window-log at each node to capture recent operations. In addition to retrospective snapshots, Retroscope also provides incremental and rolling snapshots that utilize an existing snapshot to reduce the cost of constructing a new snapshot in proximity. This capability is useful for performing stepwise debugging and root-cause analysis, and supporting data integrity monitoring and checkpoint-recovery. We implement Retroscope for the Voldemort distributed datastore and evaluate its performance under varying workloads.

Causal consistency is an intermediate consistency model that can be achieved together with high availability and high-performance requirements even in presence of network partitions. In the context of partitioned data stores, it has been shown that implicit dependency tracking using clocks is more efficient than explicit dependency tracking by sending dependency check messages. Existing clock-based solutions depend on monotonic psychical clocks that are closely synchronized. These requirements make current protocols vulnerable to clock anomalies. In this paper, we propose a new clock-based algorithm, CausalSpartan, that instead of physical clocks, utilizes Hybrid Logical Clocks (HLCs). We show that using HLCs, without any overhead, we make the system robust on physical clock anomalies. This improvement is more significant in the context of query amplification, where a single query results in multiple GET/PUT operations. We also show that CausalSpartan decreases the visibility latency for a given data item comparing to existing clock-based approaches. In turn, this reduces the completion time of collaborative applications where two clients accessing two different replicas edit same items of the data store. Like previous protocols, CausalSpartan assumes that a given client does not access more than one replica. We show that in presence of network partitions, this assumption (made in several other works) is essential if one were to provide causal consistency as well as immediate availability to local updates.

Coordination and consensus play an important role in datacenter and cloud computing, particularly in leader election, group membership, cluster management, service discovery, resource/access management, and consistent replication of the master nodes in services. Paxos protocols and systems provide a fault-tolerant solution to the distributed consensus problem and have attracted significant attention as well as generating substantial confusion. In order to elucidate the correct use of distributed coordination systems, we compare and contrast popular Paxos protocols and Paxos systems and present advantages and disadvantages for each. We also categorize the coordination use-patterns in cloud, and examine Google and Facebook infrastructures, as well as Apache top-level projects to investigate how they use Paxos protocols and systems. Finally, we analyze tradeoffs in the distributed coordination domain and identify promising future directions for achieving more scalable distributed coordination systems.

Research in system stabilization has traditionally relied on the availability of a complete system implementation. As such, it would appear that the scalability and reusability of stabilization is limited in practice. To redress this perception, in this paper, we show for the first time that system stabilization may be designed knowing only the system specification but not the system implementation. We refer to stabilization designed thus as specification-based design of stabilization and identify “local everywhere specifications” and “convergence refinements” as being amenable to the specification-based design of stabilization. Using our approach, we present the design of Dijkstra's four-state stabilizing token-ring system starting from an abstract fault-intolerant token-ring system. We also present an illustration of automated design of specification-based stabilization on a three-state token-ring system.

For datacenter applications that require tight synchronization, transactions are commonly employed for achieving concurrency while preserving correctness. Unfortunately, distributed transactions are hard to scale due to the decentralized lock acquisition and coordination protocols they employ. We investigate the use of a centralized lock broker architecture to improve the efficiency/scalability for distributed transactions, and present the design and development of such a framework, called Panopticon. Panopticon achieves efficiency/scalability by divorcing locks from the data items and migrating locks to improve lock access locality. More specifically, the lock broker mediates the access to data shared across servers by migrating the associated locks like tokens, and in the process learns and improves the access locality of transactions. Our experiments show that Panopticon performs better than distributed transactions as the number of data items and number of servers involved in transactions increase. Moreover, as the history locality (the probability of using the same objects in consecutive transactions) increase, Panopticon's lock migration strategies improve lock-access locality and result in significantly better performance. Finally, we also show that, by employing simple learning techniques, the broker can further improve the lock access locality and, hence, the performance of distributed transactions.

In-memory data grid (IMDG) is a new technology that enables scalable and low-latency processing of big data by sharding it over the RAMs of multiple servers. In this paper, we explore the design space of IMDGs to identify their advantages and avoid their drawbacks. We present the performance tradeoffs of IMDGs using unit tests on core distributed operations and data structures. For evaluation, we use large-scale graph processing, a challenging task that requires a high degree of communication and coordination between vertices. We find that while IMDGs cannot compete with specialized distributed frameworks (such as Giraph and GraphLab) for batch-mode graph processing, they excel for online graph processing and offer exciting opportunities for social networks and web services applications.

We develop the Periodic Listening Medium Access Control protocol (PLMAC) to improve energy-efficiency for smartphone-based data collection applications. PLMAC decreases the idle listening period of network nodes with a duty cycling schedule based on neighbor node visits. In a smartphone-based data collection application, network nodes run mostly in the idle listening operation for detecting a smartphone visit. The duty cycling mechanism of PLMAC allows nodes to sleep most of the time with a sleep/listen schedule. When a node is visited by a smartphone user, its neighbor nodes adjust their listening period to be long enough to communicate with an approaching smartphone. By analyzing a mobility dataset, we validate the need for a duty cycling schedule based on neighbor node visits. PLMAC runs in collaboration with the B-MAC protocol. We found that PLMAC's duty cycling mechanism results in better energy-efficiency than B-MAC.

Hybrid vector clocks (HVC) implement vector clocks (VC) in a space-efficient manner by exploiting the availability of loosely-synchronized physical clocks at each node. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, epsilon: uncertainty window, delta: minimum message delay, alpha: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases. Our model and simulations show the HVC size is a sigmoid function with respect to increasing epsilon; it has a slow start but it grows exponentially after a phase transition. We present equations to identify the phase transition point and show that for many practical applications and deployment environments, the size of HVC remains only as a couple entries and substantially less than n. We also find that, in a model with random unicast message transmissions, increasing n actually helps for reducing HVC size.

This article describes LineKing, a crowdsensing system for monitoring and forecasting coffee shop line wait times. LineKing consists of a smartphone component that provides automatic and accurate wait-time detection, and a cloud backend that uses the collected data to provide accurate wait-time estimation. LineKing is used on a daily basis by hundreds of users to monitor the wait-times of a coffee shop in the University at Buffalo, SUNY. The novel wait-time estimation algorithms of LineKing deployed at the cloud backend provide median absolute errors of less than 3 minutes.

We leverage crowd wisdom for multiple-choice question answering, and employ lightweight machine learning techniques to improve the aggregation accuracy of crowdsourced answers to these questions. In order to develop more effective aggregation methods and evaluate them empirically, we developed and deployed a crowdsourced system for playing the “Who wants to be a millionaire?” quiz show. Analyzing our data (which consist of more than 200,000 answers), we find that by just going with the most selected answer in the aggregation, we can answer over 90% of the questions correctly, but the success rate of this technique plunges to 60% for the later/harder questions in the quiz show. To improve the success rates of these later/harder questions, we investigate novel weighted aggregation schemes for aggregating the answers obtained from the crowd. By using weights optimized for reliability of participants (derived from the participants’ confidence), we show that we can pull up the accuracy rate for the harder questions by 15%, and to overall 95% average accuracy. Our results provide a good case for the benefits of applying machine learning techniques for building more accurate crowdsourced question answering systems.

This paper presents a survey on the timing performance of Google Cloud Messaging (GCM). We evaluate GCM in real world experiments, and at a reasonable scale involving thousands of real users. Our findings reveal that the GCM message delivery is unpredictable, namely having a reliable connection to Google's GCM servers on the client device does not guarantee a timely message arrival. Therefore, GCM is not suitable for time sensitive and/or "must-deliver-to-all" app scenarios. On the other hand, GCM delivers the push messages to a big portion of the subscribers (more than 40% in any experiment scenario) in a reasonable timeframe (in 10 seconds). Therefore, GCM may be a good fit for the application scenarios where random multicasting is sufficient, such as crowdsourcing systems. Our results provide a through evaluation of the GCM performance, and will guide developers and researchers to decide whether GCM is suitable for their intended use cases.

In many real world applications, the same item may be described by multiple sources. As a consequence, conflicts among these sources are inevitable, which leads to an important task: how to identify which piece of information is trustworthy, i.e., the truth discovery task. Intuitively, if the piece of information is from a reliable source, then it is more trustworthy, and the source that provides trustworthy information is more reliable. Based on this principle, truth discovery approaches have been proposed to infer source reliability degrees and the most trustworthy information (i.e., the truth) simultaneously. However, existing approaches overlook the ubiquitous long-tail phenomenon in the tasks, i.e., most sources only provide a few claims and only a few sources make plenty of claims, which causes the source reliability estimation for small sources to be unreasonable. To tackle this challenge, we propose a confidence-aware truth discovery (CATD) method to automatically detect truths from conflicting data with long-tail phenomenon. The proposed method not only estimates source reliability, but also considers the confidence interval of the estimation, so that it can effectively reflect real source reliability for sources with various levels of participation. Experiments on four real world tasks as well as simulated multi-source long-tail datasets demonstrate that the proposed method outperforms existing state-of-the-art truth discovery approaches by successful discounting the effect of small sources.

The proximity alert service on Android is important as an enabler of smart cities, however, it is also limited in this role due to its excessive energy expenditure. In this paper, we present the design and implementation of an energy-efficient proximity alert service for both high-precision and low-precision applications. Our methods utilize the distance to the point of interest and the user's transportation mode in order to dynamically determine the location-sensing interval and the location providers (GPS or Network) to be used. We implement our methods as a middleware service in the Android open source project. Our service for realistic scenarios, on average, increases the battery life time of baseline proximity alert in Android by 62% for high-precision and 71% for low-precision applications.

Concurrent execution is a big challenge for distributed systems programming and cloud computing. Using locks is the most common technique for developing distributed applications that require tight synchronization. Unfortunately, locking is manual, error-prone, and unscalable. To address this issue, we propose a scalable automated locking framework called Maestro. Maestro consists of a master and several workers, which can be dynamically instantiated on demand. Maestro examines the program actions of the workers before deployment and automatically decides which worker actions can be executed locally (without contacting the master) and which actions require synchronization through the master. Maestro has applications in graph processing, real-time enterprise analysis, and web-services domains. By enabling the developers to write code at a higher-level of abstraction (shared-memory), Maestro improves productivity and lowers the cost of entry to cloud computing backend development.

In wireless sensor network (WSN) deployments, Receiver-side Collision Detection (RCD) has been proposed for speeding up collaborative feedback collection from a single hop neighborhood. Using RCD, an initiator node can query the existence of a predicate P in its neighborhood in constant time by making all P-positive nodes answer simultaneously. Despite the collisions, the initiator is still able to infer useful information from a broadcast using RCD: an activity in the network means the predicate P holds for at least one node while silence indicates that P does not hold at any queried node in the network. In this study we investigate the threshold querying problem, where the initiator has to learn whether P holds in the network for at least threshold t number of nodes in single hop of the initiator. To answer the threshold queries in an efficient fashion, we present a number of adaptive RCD-based querying mechanisms that dynamically re-groups the queried nodes in the network. We evaluate our algorithms on a real sensor network implementation and also carry out several simulations to contrast our approach with the traditional techniques. The experiments reveal that our algorithms achieve significant time improvements in threshold queries over traditional techniques.

Federated sensor networks (FSNs) connect and combine several partitioned wireless sensor networks (WSNs) to extend the scope of WSNs to larger scale geographical areas. The federated and sparsely/intermittently connected nature of FSNs introduce several challenges for deploying middleware services such as routing, querying, tracking, time synchronization. In this paper, we investigate the challenges for deploying a querying service on FSNs. We review several querying protocols proposed in the WSNs literature and identify the applicability and shortcomings of these protocols for FSNs. Based on our investigation, we suggest open research directions for building an efficient querying service for FSNs.

In this study, we provide a lightweight singlehop primitive, Read-All-Write-Self (RAWS), that achieves optimistic concurrency control. RAWS guarantees serializability, which simplifies implementation and verification of distributed algorithms, compared to the low level message passing model. We also present a self-stabilizing multihop extension of RAWS, called Multihop Optimistic Concurrency Control Algorithm (MOCCA), to address the challenges of multihop networks. We implement RAWS on motes and investigate the effects of message loss over this novel primitive.

Idle-listening is the biggest challenge for energy-efficiency and longevity of multihop wireless sensor network (WSN) deployments. While existing coordinated sleep/wakeup scheduling protocols eliminate idle-listening for simple traffic patterns, they are unsuitable to handle the complex traffic patterns of the random routing protocols. We present a novel coordinated sleep/wakeup protocol PowerNap, which avoids the overhead of distributing complex, large sleep/wakeup scheduling information to the nodes. PowerNap piggybacks onto the relayed data packets the seed of the pseudo-random generator that encodes the scheduling information, and enables any recipient/snooper to calculate its sleep/wakeup schedule from this seed. In essence, PowerNap trades off doing extra computation in order to avoid expensive control packet transmissions. We show through simulations and real implementation on TelosB motes that PowerNap eliminates the idle-listening problem efficiently and achieves self-stabilizing, low-latency, and low-cost relaying of data packets for random routing protocols.

Nowadays, most of the basic web services use instant location information for providing suitable content to smartphone users. However, more intelligent smartphone applications such as context-based search and advertising, early warning systems and city-wide sensing applications may require additional information about smartphone users such as their mobility profiles. To meet more personalized demand of these applications we propose TRACK ME: A new web-based framework for smartphone applications with personalized lightweight mobility service as well as location tracking and mobility profile construction. We showed that our personalized mobility service supports different smartphone applications and it is lightweight enough to provide fast access to the mobility profiles of smartphone users. We illustrate the benefits of our mobility service on two smartphone applications: location prediction and air pollution exposure risk estimation.

Stationary wireless sensor networks (WSNs) fail to scale when the area to be monitored is unbounded and the physical phenomenon to be monitored may migrate through a large region. Deploying mobile sensor networks (MSNs) alleviates this problem, as the self-configuring MSN can relocate to follow the phenomenon of interest. However, a major challenge here is to maximize the sensing coverage in an unknown, noisy, and dynamically changing environment with nodes having limited sensing range and energy, and moving under distributed control. To address these challenges, we propose a new distributed algorithm, Causataxis, which enables the MSN to relocate toward the interesting regions and adjust its shape and position as the sensing environment changes. (In Latin, causa means motive/interest. A taxis (plural taxes) is an innate behavioral response by an organism to a directional stimulus. We use Causataxis to refer to an interest driven relocation behavior.) Unlike conventional cluster-based systems with backbone networks, a unique feature of our proposed approach is its biosystem inspired growing and rotting behaviors with coordinated locomotion. We compare Causataxis with a swarm-based algorithm, which uses the concept of virtual spring forces to relocate mobile nodes based on local neighborhood information. Our simulation results show that Causataxis outperforms the swarm-based algorithm in terms of the sensing coverage, the energy consumption, and the noise tolerance with a slightly high communication overhead.

In this paper, we propose a novel routing protocol, PRO, for profile-based routing in pocket switched networks. Differing from previous routing protocols, PRO treats node encounters as periodic patterns and uses them to predict the times of future encounters. Exploiting the regularity of human mobility profiles, PRO achieves fast (low-delivery-latency) and efficient (low-message-overhead) routing in intermittently connected pocket switched networks. PRO is self-learning, completely decentralized, and local to the nodes. Despite being simple, PRO forms a general framework, that can be easily instantiated to solve searching and querying problems in adhoc smartphone networks. We validate the performance of PRO with the “'Reality Mining” dataset containing 350K hours of celltower connectivity and Bluetooth connection data, and compare its performance with that of previous approaches.

In microblogging services such as Twitter, the users may become overwhelmed by the raw data. One solution to this problem is the classification of short text messages. As short texts do not provide sufficient word occurrences, traditional classification methods such as "Bag-Of-Words" have limitations. To address this problem, we propose to use a small set of domain-specific features extracted from the author's profile and text. The proposed approach effectively classifies the text to a predefined set of generic classes such as News, Events, Opinions, Deals, and Private Messages.

Despite the availability of the sensor and smart-phone devices to fulfill the ubiquitous computing vision, the-state-of-the-art falls short of this vision. We argue that the reason for this gap is the lack of an infrastructure to task/utilize these devices for collaboration. We propose that microblogging services like Twitter can provide an "open" publish-subscribe infrastructure for sensors and smartphones, and pave the way for ubiquitous crowd-sourced sensing and collaboration applications. We design and implement a crowd-sourced sensing and collaboration system over Twitter, and showcase our system in the context of two applications: a crowd-sourced weather radar, and a participatory noise-mapping application. Our results from real-world Twitter experiments give insights into the feasibility of this approach and outline the research challenges in sensor/smartphone integration to Twitter.

Improving throughput and delay is an important challenge in multi-hop wireless sensor networks. In this work, we propose ABC-MC, a simple multi-channel geographic forwarding scheme. ABC-MC is based on ABC which is a lightweight and reliable routing protocol where nodes do not need to set up or maintain routing/neighbor tables. A unique feature of ABC-MC is that it uses a channel prenegotiation mechanism to reduce delay. Another unique feature of ABC-MC is that it takes account of the channel usage information within three hops in channel selection to reduce interference. Experimental results show that ABC-MC outperforms other protocols in terms of the average delay and throughput performance.

In this paper we devise a holistic solution to the pursuer-evader tracking problem taking into account the limitations of the wireless sensor networks (WSNs) as well as the dynamics of both the pursuer and evader. More specifically, we present an optimal strategy for the pursuer to capture the evader despite the delayed and imprecise information available at the pursuer-side. In order to minimize the communication overhead while ensuring capture, we provide an optimal evader sampling scheme that adjusts the sampling frequency based on the strategies of the pursuer and evader, as well as the distance between the pursuer and evader. We support our adaptive sampling scheme with a just-in-time delivery protocol that publishes the evader's location updates directly to the pursuer, reducing the communication overhead of tracking even further. To further enhance the tracking reliability, we use a two-level design of fault tolerance: 1) a double position advertisement scheme to mask single message losses, and 2) a breadcrumbs-based backup scheme for stabilizing from desynchronization.Our simulation results show that the adaptive sampling scheme guides the pursuer to capture the evader effectively, and reduces the communication overhead significantly compared to fixed rate sampling. Our simulation results also show that our two-level fault-tolerance strategy ensures high capture rates even under consecutive message losses.

Mobility path information of cellphone users play a crucial role in a wide range of cellphone applications, including context-based search and advertising, early warning systems, city-wide sensing applications such as air pollution exposure estimation and traffic planning. However, there is a disconnect between the low level location data logs available from the cellphones and the high level mobility path information required to support these cellphone applications. In this paper, we present formal definitions to capture the cellphone users' mobility patterns and profiles, and provide a complete framework, Mobility Profiler, for discovering mobile user profiles starting from cell based location log data. We use real-world cellphone log data (of over 350 K hours of coverage) to demonstrate our framework and perform experiments for discovering frequent mobility patterns and profiles. Our analysis of mobility profiles of cellphone users expose a significant long tail in a user's location-time distribution: A total of 15% of a user's time is spent on average in locations that each appear with less than 1% of time.

We present a practical plant-and-play wireless sensor network system for entry-exit monitoring. Our system is easily configurable and robust, making it feasible to be deployed in a wide range of entry-exit monitoring applications. At the core of our system lies a novel MAC protocol that is self-synchronizing. Notably, our MAC protocol allows the nodes to maintain a very low duty cycle (the radios are in sleep mode 100% of the time in the absence of detections), while also enabling quick synchronization of the nodes (when needed) for a consistent classification of entry or exit events. We have deployed this system for monitoring a faculty parking lot at our university and integrated it with an SMS notification system to provide information on the availability of parking spots on demand. We present the parking lot occupancy trends obtained through this deployment and discuss some of the reliability issues encountered.

Distributed observation and control of mobile objects via static wireless sensors demands timely information in a distance-sensitive manner: Information about closer objects is required more often and more quickly than that of farther objects. In this article, we present a wireless sensor network protocol, Trail, that supports distance-sensitive tracking of mobile objects for in-network subscribers upon demand. Trail achieves a find time that is linear in the distance from a subscriber to an object, via a distributed data structure that is updated only locally when the object moves. Notably, Trail does not partition the network into a hierarchy of clusters and clusterheads, and as a result Trail has lower maintenance costs, is more locally fault tolerant, and it better utilizes the network in terms of load balancing and minimizing the size of the data structure needed for tracking. Moreover, Trail is reliable and energy efficient, despite the network dynamics that are typical of wireless sensor networks. Trail can be refined by tuning certain parameters, thereby yielding a family of protocols that are suited for different application settings such as rate of queries, rate of updates, and network size. We evaluate the performance of Trail by analysis, simulations in a 90 × 90 sensor network, and experiments on 105 Mica2 nodes in the context of a pursuer-evader control application.

In contrast to traditional wireless sensor network (WSN) applications that perform only data collection and aggregation, the new generation of information processing applications such as pursuit-evasion games, tracking, evacuation, and disaster relief applications require in-network information storage and querying. Due to the resource limitations of WSNs, it is challenging to implement in-network querying in a distributed, lightweight, resilient, and energy-efficient manner. We address these challenges by exploiting location information and the geometry of the network and propose an in-network querying framework, namely, the Distributed Quad-Tree (DQT). DQT is distance sensitive for querying of an event: the cost of answering a query for an event is at most a constant factor (2radic(2) in our case) of the distance *d* to the event. DQT construction is local and does not require any communication. Moreover, due to its minimalist infrastructure and stateless nature, DQT shows graceful resilience to node failures and topology changes. Since event-based querying is inherently limited to the anticipated types of inquiries, we further extend our framework to achieve complex range-based querying. To this end, we use a multiresolution algorithm, which is optimal with respect to least square errors that models the data in a decentralized way. Our model-based scheme answers queries with approximate values accompanied by certainty levels with increased resolution at lower layers of the DQT hierarchy. Our analysis and experiments show that our framework achieves distance sensitivity and resiliency for event-based querying, as well as greatly reduces the cost of complex range querying.

Fast and energy-efficient message delivery is an ultimate goal in multi-hop wireless sensor networks. To help achieve this goal, we propose ABC, a simple geographic forwarding scheme capable of bypassing routing holes. ABC is a lightweight and reliable routing protocol in that nodes do not need to set up or maintain routing or neighbor tables; instead, ABC achieves lightweight routing via its "Angled relaying" mechanism and uses the "Backoff time and relay Cancellation" mechanism to reduce contention and the number of retransmissions. One unique feature of ABC is that a relayed message is used as an implicit ACK to a previous sender. Another unique feature of ABC is its routing hole bypassing mechanism based on reactive boundary recognition. In this paper we provide an extensive analysis of ABC in terms of average hop count and average delay per hop. Simulation results also show that ABC outperforms other protocols in terms of average delay and number of transmissions per message delivery.

To achieve scalability, energy-efficiency, and timeliness, wireless sensor network deployments increasingly employ in-network processing. In this paper, we identify singlehop feedback collection as a key building block for in-network processing applications, and introduce a basic singlehop primitive, pollcast. The key idea behind this primitive is to exploit the receiver-side collision detection information at the MAC-layer to speed-up collaborative feedback collection. Using pollcast, a node can get an affirmation about the existence of a node-level predicate P in its neighborhood in constant time by asking all nodes where P hold to reply simultaneously. We have implemented pollcast on Tmotes using Chipcon 2420 radio. Our results show that this primitive is indeed lightweight, resilient, and effective. Our paper is also the first time receiver-side collision detection is achieved in a practical manner for Chipcon 2420 radio.

Effectively managing concurrent execution is one of the biggest challenges for future wireless sensor/actor networks (WSANs): for safety reasons concurrency needs to be tamed to prevent unintentional nondeterministic executions, on the other hand, for real-time guarantees concurrency needs to be boosted to achieve timeliness. We propose a transactional, optimistic concurrency control framework for WSANs that enables understanding of a system execution as a single thread of control, while permitting the deployment of actual execution over multiple threads distributed on several nodes. By exploiting the atomicity and broadcast properties of singlehop wireless communication, we provide a lightweight implementation of our transactional framework on the motes platform.

In a mobile ad hoc network, tracking protocols need to deal with-in addition to the mobility of the target- the mobility of the intermediate nodes that maintain a track toward the target. To address this problem, we propose the MDQT (Mobility-enhanced Distributed QuadTree) tracking framework. MDQT employs a static cell abstraction to mask the mobility of the nodes and provide the illusion of a logical static network overlaid on the mobile network. MDQT implements this virtual static network layer in a lightweight/communication-free manner by exploiting the soft-state principle and the snooping feature of wireless communication. Using simulations, we study the effects of the mobility speed and the percentage of mobile nodes on the performance of our MDQT framework. We find that even at very high mobility speeds (50 meters per second), low update rates (1 update per second), and 100% node mobility, the success rate of MDQT tracking is above 85% and the latency is comparable with that of static networks.

Stationary wireless sensor networks (WSNs) fail to scale when the area to be monitored is open (i.e borderless) and the physical phenomena to be monitored may migrate through a large region. Deploying mobile sensor networks (MSNs) alleviates this problem, as the self-configuring MSN can relocate to follow the phenomena of interest. However, a major challenge here is to maximize the sensing coverage in an unknown, noisy, and dynamic sensing environment while minimizing energy consumption. Another major challenge is to maintain network connectivity for each MSN node during relocations. To address these challenges, we propose a new distributed algorithm, Causataxis1, that enables the MSN to relocate toward the interesting regions and adjust its shape and position as the sensing environment changes. Causataxis achieves scalable control of the MSN via a backbone-tree infrastructure maintained over clusterhead nodes, and achieves agility via localized cluster formation and dissolution. Unlike conventional cluster-based systems with backbone networks, a unique feature of our proposed approach is its bio-system inspired growing and rotting behaviors with coordinated locomotion. We compare Causataxis with a custom tuned swarm algorithm, which uses the concept of virtual spring forces to relocate mobile nodes based on local neighborhood information. Our simulation results show that Causataxis can outperform the swarm based algorithm in terms of the sensing coverage, the energy consumption, and the noise tolerance with a slightly high communication overhead.

Abstract With the increasing need for different energy saving mechanisms in Wireless Sensor Networks (WSNs), data aggregation techniques for reducing the number of data transmissions by eliminating redundant information have been studied as a significant research problem. These studies have shown that data aggregation in WSNs may produce various trade‐offs among some network related performance metrics such as energy, latency, accuracy, fault‐tolerance and security. In this paper, we investigate the impact of data aggregation on these networking metrics by surveying the existing data aggregation protocols in WSNs. Our aim is twofold: First, providing a comprehensive summary and comparison of the existing data aggregation techniques with respect to different networking metrics. Second, pointing out both the possible future research issues and the need for collaboration between data management and networking research communities working on data aggregation in WSNs. Copyright © 2006 John Wiley & Sons, Ltd.

In contrast to the traditional wireless sensor network (WSN) applications that perform only data collection and aggregation, new generation of information processing applications, such as pursuit-evasion games, tracking, evacuation, and disaster relief applications, require in-network information storage and querying. Due to the resource limitations of WSNs, it is challenging to implement in-network information storage and querying in a resilient, energy-efficient, and distributed manner. To address these challenges, we exploit location information and geometry of the network and present an in-network querying infrastructure, namely distributed quad-tree (DQT) structure. DQT satisfies efficient in-network information storage as well as distance-sensitive querying: the cost of answering a query for an event is at most a constant factor (in our case 2radic2 ) of the distance "d" to the nearest event in the network. DQT construction is local and does not require any communication. Moreover, due to its minimalist infrastructure and stateless nature, DQT shows graceful resilience to the face of failures.

RTS-CTS handshake based protocols achieve "reliable unicast" by eliminating the hidden node problem effectively, however, these solutions are not directly or efficiently gener- alizablefor solving the "reliable multicast"problem; multicast remains as a best-effort operation in wireless ad hoc networks. Here, we present a simple, light-weight, and self- stabilizing MAC protocol, namely busy elimination multiple access (BEMA) protocol, for solving the reliable multicast problem. BE MA grants on-demand access to the channel-rather than assigning fixed slots as in TDMA based approaches-and supports prioritization of traffic, thereby providing a useful building block for applications with reliability and quality-of service requirements.

We present our experience with designing, developing, and deploying of an Internet accessible wireless sensor network for monitoring temperature, humidity, and illumination of a controlled environment. The design goals for our system, INSIGHT: Internet-sensor integration for habitat monitoring, are extended deployment lifetime, remote querying and configuration, ease of deployment, and reliability. We present results from our deployment of INSIGHT in a greenhouse.

RTS-CTS handshake based protocols achieve "reliable unicast" by eliminating the hidden node problem effectively, however, these solutions are not directly or efficiently generalizable for solving the "reliable multicast" problem; multicast remains a best-effort operation in wireless ad hoc networks. Here we present a simple light-weight MAC protocol, namely busy elimination multiple access (BEMA) protocol, for solving the reliable multicast problem. BEMA grants on-demand access to the channel-rather than assigning fixed slots as in TDMA based approaches-and supports prioritization of traffic, thereby providing a useful building block for applications with reliability and quality-of-service requirements

A sybil node impersonates other nodes by broadcasting messages with multiple node identifiers (ID). In contrast to existing solutions which are based on sharing encryption keys, we present a robust and lightweight solution for sybil attack problem based on received signal strength indicator (RSSI) readings of messages. Our solution is robust since it detects all sybil attack cases with 100% completeness and less than a few percent false positives. Our solution is lightweight in the sense that alongside the receiver we need the collaboration of one other node (i.e., only one message communication) for our protocol. We show through experiments that even though RSSI is time-varying and unreliable in general and radio transmission is non-isotropic, using ratio of RSSIs from multiple receivers it is feasible to overcome these problems.

We present a fast, local clustering service, FLOC, that partitions a multihop wireless network into nonoverlapping and approximately equal-sized clusters. Each cluster has a clusterhead such that all nodes within unit distance and some nodes within distance m of the clusterhead belong to the cluster. We show that, by asserting a stretch factor m ges 2, FLOC achieves locality of clustering and fault-local self-stabilization: the effects of cluster formation and faults/changes at any part of the network are contained within at most m + 1 units. Through simulations and experiments with actual deployments, we analyze the trade-offs between clustering time and the quality of clustering and suggest suitable parameters for FLOC to achieve a fast completion time without compromising the quality of the resulting clustering

We consider the fault-tolerant consensus problem in wireless ad hoc networks with crash-prone nodes. We develop consensus algorithms for single-hop environments where the nodes are located within broadcast range of each other. Our algorithms tolerate highly unpredictable wireless communication, in which messages may be lost due to collisions, electromagnetic interference, or other anomalies. Accordingly, each node may receive a different set of messages in the same round. In order to minimize collisions, we design adaptive algorithms that attempt to minimize the broadcast contention. To cope with unreliable communication, we augment the nodes with collision detectors and present a new classification of collision detectors in terms of accuracy and completeness, based on practical realities. We show exactly in which cases consensus can be solved, and thus determine the requirements for a useful collision detector.We validate the feasibility of our algorithms, and the underlying wireless model, with simulations based on a realistic 802.11 MAC layer implementation and a detailed radio propagation model. We analyze the performance of our algorithms under varying sizes and densities of deployment and varying MAC layer parameters. We use our single-hop consensus algorithms as the basis for solving consensus in a multi-hop network, demonstrating the resilience of our algorithms to a challenging and noisy environment.

We present a fast local clustering service, FLOC, that partitions a multi-hop wireless network into nonoverlapping and approximately equal-sited clusters. Each cluster has a clusterhead such that all nodes within unit distance of the clusterhead belong to the cluster but no node beyond distance m from the clusterhead belongs to the cluster. By asserting m /spl ges/ 2, FLOC achieves locality: effects of cluster formation and faults/changes at any part of the network are contained within most m units. By taking unit distance to be the reliable communication radius and m to be the maximum communication radius, FLOC exploits the double-band nature of wireless radio-model and achieves clustering in constant time regardless of the network size. Through simulations and experiments with actual deployments, we analyze the tradeoffs between clustering time and the quality of clustering, and suggest suitable parameters for FLOC to achieve a fast completion time without compromising the quality of the resulting clustering.

No abstract available.

Sensor networks, that consist of potentially several thousands of nodes each with sensing (heat, sound, light, magnetism, etc.) and wireless communication capabilities, provide great opportunities for monitoring spatial information about a region of interest. Although spatial query execution has been studied extensively in the context of database systems (e.g., indexing technologies), these solutions are not directly applicable in the context of sensor networks due to the decentralized nature of the sensor networks and the limited computational power and energy scarcity of individual sensor nodes. We present a peer-to-peer indexing structure, namely peer-tree, in order to address the problem of energy- and time-efficient execution of spatial queries (such as nearest-neighbor queries) in sensor networks. Loosely speaking, our peer-tree structure can be interpreted as a peer-to-peer version of the centralized R-tree index structure. Using the peer-tree as a building block, we present a peer-to-peer query processing model where a query can be posed in any node of the network without the need of a central server. For achieving minimal energy consumption and minimal response time, our query processing model ensures that only the relevant nodes for the correct execution of a query are involved in the query execution.

During summer 2002, we ran a workshop module for a group of 28 eighth-grade girls. Our aim was ambitious: to introduce these students, ages 12 and 13, to computer science by focussing on the deep intellectual topic of self-stabilizing distributed algorithms and by imparting an intuitive appreciation for their use in fault tolerance. At the same time, we hoped to dispel some negative stereotypes of computer science. The module was a success according to evaluations and comments from the participants. This paper describes the sequence of exercises we developed as an elementary-level introduction to the graduate-level topics of fault tolerance and self-stabilization. We report them with the hope that others will try them in college classrooms, as we plan to do.

Refinement tools such as compilers do not necessarily preserve fault-tolerance. That is, given a fault-tolerant program in a high-level language as input, the output of a compiler in a lower-level language will not necessarily be fault-tolerant. We identify a type of refinement, namely "convergence refinement", that preserves the fault-tolerance property of stabilization. We illustrate the use of convergence refinement by presenting the first formal design of Dijkstra's little-understood 3-state stabilizing token-ring system. Our designs begin with simple, abstract token-ring systems that are not stabilizing, and then add an abstract "wrapper" to the systems so as to achieve stabilization. The system and the wrapper are then refined to obtain a concrete token-ring system, while preserving stabilization. In fact, the two are refined independently, which demonstrates that convergence refinement is amenable for "graybox" design of stabilizing implementations, i.e., design of system stabilization based solely on system specification and without knowledge of system implementation details.

Research in system stabilization has traditionally relied on the availability of a complete system implementation. As such, it would appear that the scalability and reusability of stabilization is limited in practice. Towards redressing this perception, the authors show for the first time that system stabilization may be designed knowing only the system specification but not the system implementation. We refer to stabilization designed thus as being "graybox" and identify "local everywhere-eventually specifications" as being amenable to design of graybox stabilization. We illustrate the design of graybox stabilization using timestamp-based distributed mutual exclusion as our example.

Vector clocks (VC) are an inherent component of a rich class of distributed applications. In this paper, we consider the problem of realistic —more specifically, bounded-space and fault-tolerant— implementation of these client applications. To this end, we generalize the notion of VC to resettable vector clocks (RVC), and provide a realistic implementation of RVC. Further, we identify an interface contract under which our RVC implementation can be substituted for VC in client applications, without affecting the client's correctness. Based on such substitution, we show how to transform the client so that it is itself realistically implemented; we demonstrate our method in the context of Ricart-Agrawala's mutual exclusion program.