We evaluated whether a vibrotactile breathing pacer would influence two measures of affect during a cognitive stressor. In particular, we examined whether changes in breathing would be evident, and if so, whether these would mediate the effects of breathing pacer on self-report anxiety and skin conductance. Our results were surprising: although we observed the expected effects on breathing, we were unable to demonstrate that changes in breathing parameters were responsible for the observed changes in self-report anxiety. In addition, we failed to show that the pacer had an impact on skin conductance. In this paper, we investigate why we did not observe the expected effects. We believe our negative results have implications for evaluating technological interventions for affect regulation.

To address difficulties with affect dysregulation in youth diagnosed with autism spectrum disorder (ASD), we designed and developed an end-to-end vibrotactile breathing pacer system and evaluated its usability. In this paper we describe the system architecture and the features we deployed for this system based on expert advice and reviews. Through piloting this system with one child diagnosed with ASD, we learned that our system was used in ways we did and did not anticipate. For example, the paced-breathing personalization procedure did not meet the attention span of the pilot participant but two instead of one pacer devices encouraged caregiver’s involvement. This paper details our learnings and concludes with a list of system design guidelines at the system architecture level. To the best of our knowledge, this is the first fully functional vibrotactile system designed for ASD children that withstood usability testing in vitro for two weeks.

Given the prevalence and adverse impact of anxiety, there is considerable interest in using technology to regulate anxiety. Evaluating the efficacy of such technology in terms of both the average effect (the intervention efficacy) and the heterogeneous effect (for whom and in what context the intervention was effective) is of paramount importance. In this paper, we demonstrate the efficacy of PIV, a personalized breathing pacer, in reducing anxiety in the presence of a cognitive stressor. We also quantify the relation between our specific stressor and PIV-user engagement. To our knowledge, this is the first mixed-design study of a vibrotactile affect regulation technology which accounts for a specific stressor and for individual differences in relation to the technology's efficacy. Guidelines in this paper can be applied for designing and evaluating other affect regulation technologies.

We describe the design and evaluation of PIV, a personalizable and inconspicuous vibrotactile breathing pacer. Given the prevalence and adverse impact of anxiety and anxiety disorders, our goal is to develop a technology that helps people regulate their anxiety through paced breathing. We examined two previously unstudied questions: What is an effective vibrotactile pattern for paced breathing, and where should the tactors be placed on the body to make the pacer most effective? We designed a series of personalized vibrotactile pacing patterns, and evaluated them on three body sites, in terms of self-reported and psychophysiological measures including skin conductance and breath wave parameters. The results show that personalization plays an important role in PIV’s pattern and placement design choices. We concluded that the choice of frequency based, strong-exhale-phased patterns and abdomen placement are appropriate for future studies.

Emerging cloud-based network services must deliver both good performance and high availability. Achieving both of these goals requires content replication across multiple sites. Many cloud-based services either require or would benefit from the semantics and simplicity of strong consistency. However, replication techniques for strong consistency can severely limit the availability of replicated services when recovering large data objects over wide-area links. To address this problem, we present the design and implementation of ZORFU, a hierarchical system architecture for replication across data centers. The primary contribution of ZORFU is a local recovery technique that significantly increases availability of replicated strongly consistent services. Local recovery achieves this by reducing the recovery time by an order of magnitude, while imposing only a negligible latency overhead. Experimental results show that ZORFU can recover a 100 MB object in 4 ms.

Fault recovery is a key issue in modern data centers. In a fat tree topology, a single link failure can disconnect a set of end hosts from the rest of the network until updated routing information is disseminated to every switch in the topology. The time for re-convergence can be substantial, leaving hosts disconnected for long periods of time and significantly reducing the overall availability of the data center. Moreover, the message overhead of sending updated routing information to the entire topology may be unacceptable at scale. We present techniques to modify hierarchical data center topologies to enable switches to react to failures locally, thus reducing both the convergence time and control overhead of failure recovery. We find that for a given network size, decreasing a topology's convergence time results in a proportional decrease to its scalability (e.g. the number of hosts supported). On the other hand, reducing convergence time without affecting scalability necessitates the introduction of additional switches and links. We explore the tradeoffs between fault tolerance, scalability and network size, and propose a range of modified multi-rooted tree topologies that provide significantly reduced convergence time while retaining most of the traditional fat tree's desirable properties.

We derive a consensus protocol for a hybrid failure model. In this model, clients are Byzantine faulty and servers are crash faulty. We argue that this model is well suited to environments where the servers run within one administrative domain, and the clients run outside of this domain. Our consensus protocol, which is derived from crash Paxos, provides low latency for client requests, tolerates any number of (Byzantine) faulty clients, up to 1/3 (crash) faulty servers, and does not rely on computing costly signatures in the common case. It can be used to build state machine replication that provides a highly available service.

Modern data centers can consist of hundreds of thousands of servers and millions of virtualized end hosts. Managing address assignment while simultaneously enabling scalable communication is a challenge in such an environment. We present ALIAS, an addressing and communication protocol that automates topology discovery and address assignment for the hierarchical topologies that underlie many data center network fabrics. Addresses assigned by ALIAS interoperate with a variety of scalable communication techniques. ALIAS is fully decentralized, scales to large network sizes, and dynamically recovers from arbitrary failures, without requiring modifications to hosts or to commodity switch hardware. We demonstrate through simulation that ALIAS quickly and correctly configures networks that support up to hundreds of thousands of hosts, even in the face of failures and erroneous cabling, and we show that ALIAS is a practical solution for auto-configuration with our NetFPGA testbed implementation.

This article describes an architecture that allows a replicated service to survive crashes without breaking its TCP connections. Our approach does not require modifications to the TCP protocol, to the operating system on the server, or to any of the software running on the clients. Furthermore, it runs on commodity hardware. We compare two implementations of this architecture (one based on primary/backup replication and another based on message logging) focusing on scalability, failover time, and application transparency. We evaluate three types of services: a file server, a Web server, and a multimedia streaming server. Our experiments suggest that the approach incurs low overhead on throughput, scales well as the number of clients increases, and allows recovery of the service in near-optimal time.

In this paper, we consider the problem of detecting whether a compromised router is maliciously manipulating its stream of packets. In particular, we are concerned with a simple yet effective attack in which a router selectively drops packets destined for some victim. Unfortunately, it is quite challenging to attribute a missing packet to a malicious action because normal network congestion can produce the same effect. Modern networks routinely drop packets when the load temporarily exceeds their buffering capacities. Previous detection protocols have tried to address this problem with a user-defined threshold: too many dropped packets imply malicious intent. However, this heuristic is fundamentally unsound; setting this threshold is, at best, an art and will certainly create unnecessary false positives or mask highly focused attacks. We have designed, developed, and implemented a compromised router detection protocol that dynamically infers, based on measured traffic rates and buffer sizes, the number of congestive packet losses that will occur. Once the ambiguity from congestion is removed, subsequent packet losses can be attributed to malicious actions. We have tested our protocol in Emulab and have studied its effectiveness in differentiating attacks from legitimate network behavior.

Abstract Dependent failures constitute a real problem in distributed systems. In this paper, we present a framework for the design of distributed algorithms for systems in which failures of processes are not necessarily independent or identically distributed. To derive this framework, we revisit the traditional way of designing distributed algorithms: assuming a threshold t on the number of process failures and determining constraints on process replication of the form All mathematics should have $n > k\cdot t$ . Under this model, there are several important results in the literature, and we use observations from these results to derive a framework that enables more expressive characterizations of failures, but still captures the essence of previous results. Our framework then has two parts: a characterization of the subsets of processes that can fail in an execution and properties that express constraints on process replication, called replication predicates. After presenting our model to characterize failures, we first consider a class of replication predicates that represent most well‐known problems in distributed computing. Second, we extend this set to also include some predicates for problems that have unusual bounds. We argue that, although being unusual, they have important practical implications, such as using fewer replicas. Copyright © 2007 John Wiley & Sons, Ltd.

This paper demonstrates the value of analyzing sequences of function calls for forensic analysis. Although this approach has been used for intrusion detection (that is, determining that a system has been attacked), its value in isolating the cause and effects of the attack has not previously been shown. We also look for not only the presence of unexpected events but also the absence of expected events. We tested these techniques using reconstructed exploits in su, ssh, and lpr, as well as proof-of-concept code, and, in all cases, were able to detect the anomaly and the nature of the vulnerability.

Replication is a technique commonly used to increase the availability of services in distributed systems, including grid and Web services. While replication is relatively easy for services with fully deterministic behavior, grid and Web services often include nondeterministic operations. The traditional way to replicate such nondeterministic services is to use the primary-backup approach. While this is straightforward in synchronous systems with perfect failure detection, typical grid environments are not usually considered to be synchronous systems. This paper addresses the problem of replicating nondeterministic services by designing a protocol based on Paxos and proposing two performance optimizations suitable for replicated grid services. The first improves the performance in the case where some service operations do not change the service state, while the second optimizes grid service requests that use transactions. Evaluations done both on a local cluster and on Planet-Lab demonstrate that these optimizations significantly reduce the service response time and increase the throughput of replicated services

Network routers occupy a unique role in modern distributed systems. They are responsible for cooperatively shuttling packets amongst themselves in order to provide the illusion of a network with universal point-to-point connectivity. However, this illusion is shattered—as are implicit assumptions of availability, confidentiality, or integrity—when network routers are subverted to act in a malicious fashion. By manipulating, diverting, or dropping packets arriving at a compromised router, an attacker can trivially mount denial-of-service, surveillance, or man-in-the-middle attacks on end host systems. Consequently, Internet routers have become a choice target for would-be attackers and thousands have been subverted to these ends. In this paper, we specify this problem of detecting routers with incorrect packet forwarding behavior and we explore the design space of protocols that implement such a detector. We further present a concrete protocol that is likely inexpensive enough for practical implementation at scale. Finally, we present a prototype system, called Fatih, that implements this approach on a PC router and describe our experiences with it. We show that Fatih is able to detect and isolate a range of malicious router actions with acceptable overhead and complexity. We believe our work is an important step in being able to tolerate attacks on key network infrastructure components.

We present a hybrid approach to the scheduling of jobs in a distributed system where the critical response is the bandwidth to access stored data. Our approach supports the master-worker scheme, but could be applied to other cases of parallel computation over stored data. We tested our new approach under various circumstances and measured it performance by means of several metrics. We made comparisons of our approach with respect to other scheduling policies; it performed significantly better than the majority of cases, and in worst cases, it was as good as the best of the others.

Network routers occupy a key role in modern data transport and consequently are attractive targets for attackers. By manipulating, diverting or dropping packets arriving at a compromised router, an attacker can trivially mount denial-of-service, surveillance or man-in-the-middle attacks on end host systems. In this paper, we specify the problem of detecting routers with incorrect packet forwarding behavior and we explore the design space of protocols that implement such a detector. We further present a concrete protocol that is inexpensive enough for practical implementation at scale.

It is possible to enhance our understanding of what has happened on a computer system by using forensic techniques that do not require prediction of the nature of the attack, the skill of the attacker, or the details of the system resources or objects affected. These techniques address five fundamental principles of computer forensics. These principles include recording data about the entire operating system, particularly user space events and environments, and interpreting events at different layers of abstraction, aided by the context in which they occurred. They also deal with modeling the recorded data as a multi-resolution, finite state machine so that results can be established to a high degree of certainty rather than merely inferred.

The combination of grid technology and Web services has produced an attractive platform for deploying distributed applications: grid services, as represented by the Open Grid Services Infrastructure (OGSI) and its Globus toolkit implementation. As the use of grid services grows in popularity, tolerating failures becomes increasingly important. This work addresses the problem of building a reliable and highly-available grid service by replicating the service on two or more hosts using the primary-backup approach. The primary goal is to evaluate the ease and efficiency with which this can be done, by first designing a primary-backup protocol using OGSI, and then implementing it using Globus to evaluate performance implications and tradeoffs. We compared three implementations: one that makes heavy use of the notification interface defined in OGSI, one that uses standard grid service requests instead of notification, and one that uses low-level socket primitives. The overall conclusion is that, while the performance penalty of using Globus primitives - especially notification - for replica coordination can be significant, the OGSI model is suitable for building highly-available services and it makes the task of engineering such services easier.

No abstract available.

In a recent paper we have proposed FT-TCP: an architecture that allows a replicated service to survive crashes without breaking its TCP connections. FT-TCP is attractive in principle because it does not require modifications to the TCP protocol and does not affect any of the software running on the clients; however, its practicality for real-world applications remains to be proven. In this paper, we report on our experience in engineering FT-TCP for two such applications---the Samba file server and a multimedia streaming server from Apple. We compare two implementations of FT-TCP, one based on primary-backup and another based on message logging, focusing on scalability, failover time, and application transparency. Our experiments suggest that FT-TCP is a practicable approach for replicating TCP/IP-based services that incurs low overhead on throughput, scales well as the number of clients increases, and allows recovery of the service in near-optimal time.

Group communications systems have been designed to provide an infrastructure for fault-tolerance in distributed systems, including wide-area systems. In our work on master-worker computation for GriPhyN, which is a large project in the area of the computational grid, we asked the question should we build our wide-area master-worker computation using wide-area group communications? This paper explains why we decided doing so was not a good idea.

We present a new abstraction to replace the t of n assumption used in designing fault-tolerant algorithms. This abstraction models dependent process failures yet it is as simple to use as the t of n assumption. To illustrate this abstraction, we consider Consensus for synchronous systems with both crash and arbitrary process failures. By considering failure correlations, we are able to reduce latency and enable the solution of Consensus for system configurations in which it is not possible when forced to use algorithms designed under the t of n assumption. We show that, in general, the number of rounds required in the worst case when assuming crash failures is different from the number of rounds required when assuming arbitrary failures. This is in contrast with the traditional result under the t of n assumption.

Internet Service Providers (ISPs) can exploit path diversity to balance load and improve robustness. Unfortunately, it is difficult to evaluate the potential impact of these approaches without routing and topological data, which are confidential. In this paper, we characterize path diversity in the real Sprint network. We then characterize path diversity in ISP topologies inferred using the Rocketfuel tool. Comparing the real Sprint topology to the one inferred by Rocketfuel, we find that the Rocketfuel topology has significantly higher apparent path diversity.(As a metric, path diversity is particularly sensitive to the presence of false or missing links, both of which are artifacts of active measurement techniques.) We evaluate heuristics that improve the accuracy of the inferred Rocketfuel topologies. Finally, we discuss limitations of active measurements techniques to capture topological properties such as path diversity.

No abstract available.

Abstract Wide‐area systems are gaining in popularity as an infrastructure for running scientific applications. From a fault tolerance perspective, these environments are challenging because of their scale and their variability. Causal message logging protocols have attractive properties that make them suitable for these environments. They spread fault tolerance information around in the system providing high availability. This information can also be used to replicate objects that are otherwise inaccessible because of network partitions. However, current causal message logging protocols do not scale to thousands or millions of processes. We describe the Hierarchical Causal Message Logging Protocol (HCML) that uses a hierarchy of shared logging sites, or proxies, to significantly reduce the space requirements as compared with existing protocols. These proxies also act as caches for fault tolerance information and reduce the overall message overhead by as much as 50%. HCML also leverages differences in bandwidth between processes that reduces overall message latency by as much as 97%. Copyright © 2003 John Wiley & Sons, Ltd.

We present Moshe, a novel scalable group membership algorithm built specifically for use in wide area networks (WANs), which can suffer partitions. Moshe is designed with three new significant features that are important in this setting: it avoids delivering views that reflect out-of-date memberships; it requires a single round of messages in the common case; and it employs a client-server design for scalability. Furthermore, Moshe's interface supplies the hooks needed to provide clients with full virtual synchrony semantics. We have implemented Moshe on top of a network event mechanism also designed specifically for use in a WAN. In addition to specifying the properties of the algorithm and proving that this specification is met, we provide empirical results of an implementation of Moshe running over the Internet. The empirical results justify the assumptions made by our design and exhibit good performance. In particular, Moshe terminates within a single communication round over 98% of the time. The experimental results also lead to interesting observations regarding the performance of membership algorithms over the Internet.

The reasons for using mobile agents are well-known: moving computation to data to avoid transferring large amounts of data; supporting disconnected operation by, for example, moving a computation to a network that has better connectivity; supporting autonomous distributed computation by, for example, deploying a personalized filter near a real-time data source. Many mobile agent systems have been constructed and are in the public domain. But, despite these well-known advantages and widely available software, mobile agents are not yet being used as a common programming abstraction. We have been working since 1993, under the name of TACOMA, on operating system support and application of mobile agents. We have addressed issues including fault-tolerance, security, efficiency, and runtime structures and services. We have built a series of mobile agent middleware systems and evaluated them by building realistic and deployed applications. We have found that mobile agents are especially useful for large-scale systems configuration and deployment, system and service extensibility, and distributed application self-management. The programming model TACOMA supports has changed over these years to reflect our experience with writing real applications. Like other mobile agent systems, TACOMA started with a programming model that resembled the characterization given above of mobile agents being processes with explicit control over where they execute. We call this the traditional model of mobile agents.

We present an implementation of a fault-tolerant TCP (FT-TCP) that allows a faulty server to keep its TCP connections open until it either recovers or it is failed over to a backup. The failure and recovery of the server process are completely transparent to client processes connected with it via TCP. FT-TCP does not affect the software running on a client, does not require to change the server's TCP implementation, and does not use a proxy.

We describe a novel scalable group membership service designed explicitly for wide area networks. Our membership service is scalable in the number of groups supported, in the number of members in each group, and in the topology each group spans. Our service also supplies the hooks needed to provide clients with full virtual synchrony semantics. Our service attains, on average, a low message overhead by agreeing on membership within a single message round. Furthermore, our service avoids notifying the application of obsolete membership views when the network is unstable, yet it converges when the network has stabilized.

We present Optimistic Virtual Synchrony (OVS), a new form of group communication which provides the same capabilities as Virtual Synchrony with better performance. It does so by allowing applications to send messages during periods in which services implementing Virtual Synchrony block. OVS also allows applications to determine the policy as to when messages sent optimistically should be delivered and when they should be discarded. Thus, OVS gives applications fine grain control over the specific semantics they require, and does not impose costs for enforcing any semantics that they do not require. At the same time, OVS provides a single easy-to-use interface for all applications.

One use of mobile agents is support for itinerant computation (D. Chess et al., 1995). An itinerant computation is a program that moves from host to host in a network. Which hosts the program visits is determined by the program. The program can have a pre-defined itinerary or can dynamically compute the next host to visit as it visits each successive host; it can visit the same host repeatedly or it can even create multiple concurrent copies of itself on a single host. Itinerant computations are susceptible to processor failures, communications failures, and crashes due to program bugs. NAP is a protocol for supporting fault tolerance in itinerant computations. It employs a form of failure detection and recovery, and it generalizes the primary backup approach to a new computational model. The guarantees offered by NAP as well as an implementation for NAP in TACOMA are discussed.

The Nile system is a distributed environment for running very large, data-intensive applications across a network of commodity workstations. These applications process data from elementary particle collisions, generated by the Cornell Electron Storage Ring, and are used by physicists of the CLEO experiment. The applications have a simple data-parallel structure, and so Nile executes them using as much parallelism as is available. Nile currently runs at any single site. It is being used by alpha testers and is scheduled for beta release in March 1998. We describe how we are adapting this local-area Nile system to allow for wide-area, multiple site interactions. In particular, we consider the two problems of scaling and of fault tolerance.

Message logging protocols ensure that crashed processes make the same choices when re-executing nondeterministic events during recovery. Causal message logging protocols achieve this by piggybacking the results of these choices (called determinants) on the ambient message traffic. By doing so, these protocols do not create orphan processes nor introduce blocking in failure-free executions. To survive f failures, they ensure that determinants are stored by at least f+1 processes. Causal logging protocols differ in the kind of information they piggyback to other processes. The more information they send, the better each process is able to estimate global properties of the determinants, which in turn results in fewer needless piggybacking of determinants. This paper quantifies the tradeoff between the cost of sending more information and the benefit of doing so.

Message-logging protocols are an integral part of a popular technique for implementing processes that can recover from crash failures. All message-logging protocols require that, when recovery is complete, there be no orphan processes, which are surviving processes whose states are inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property "no orphan processes". From this specification, we describe how different existing classes of message-logging protocols (namely optimistic, pessimistic, and a class that we call causal) implement this property. We then propose a set of metrics to evaluate the performance of message-logging protocols, and characterize the protocols that are optimal with respect to these metrics. Finally, starting from a protocol that relies on causal delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f (1/spl les/f/spl les/n).

Processor group membership protocols implement a service that allow processors to agree on which processors are operational. Implementations of group membership for hard real-time systems have concentrated on either reducing failure detection latency or minimizing message complexity. Instead, we present a protocol that uses shared resources-processor time and network bandwidth-as a small, bounded tax imposed on existing broadcast message traffic. In doing so, the group membership protocol can easily be taken into account by any schedulability analysis.

Casual message logging protocols[3] have several attractive properties: they introduce no blocking, send no additional messages over those sent by the application, and can never cause orphans to be created by crashes.Causal message logging, however, does require additional data to be piggybacked on application messages.The amount of such piggybacked data can become large.In this paper, we present five different implementations of casual message logging.All of the corresponding protocols are parameterized by ~, the maximum number of processes that can fail concurrently.We also explore how the application's communication structure can be exploited to limit the amount of piggybacked data.ing recorded that state.When a process crashes, a new process is created in its place: the new process is given

No abstract available.

Message logging protocols are an integral part of a technique for implementing processes that can recover from crash failures. All message logging protocols require that, when recovery is complete, there be no orphan processes, which are surviving processes whose states are inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property "no orphan processes". From this specification, we describe how different existing classes of message logging protocols (namely optimistic, pessimistic, and a class that we call causal) implement this property. We then propose a set of metrics to evaluate the performance of message logging protocols, and characterize the protocols that are optimal with respect to these metrics. Finally, starting from a protocol that relies on causal delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f:1/spl les/f/spl les/n.

No abstract available.

No abstract available.

The fail-stop failure model appears frequently in the distributed systems literature. However, in an asynchronous distributed system, the fail-stop model cannot be implemented. In particular, it is impossible to reliably detect crash failures in an asynchronous system. In this paper, we show that it is possible to specify and implement a failure model that is indistinguishable from the fail-stop model from the point of view of any process within an asynchronous system. We give necessary conditions for a failure model to be indistinguishable from the fail-stop model, and derive lower bounds on the amount of process replication needed to implement such a failure model. We present a simple one-round protocol for implementing one such failure model, which we call simulated fail-stop.>

A methodology for transforming a process control program that cannot tolerate sensor failure into one that can is presented. In this methodology, a reliable abstract sensor is created by combining information from several real sensors that measure the same physical value. To be useful, an abstract sensor must deliver reasonably accurate information at reasonable computational cost. The authors consider sensors that deliver multidimensional values (e.g. location or velocity in three dimensions). Geometric techniques are used to derive upper bounds on abstract sensor accuracy and to develop efficient algorithms for implementing abstract sensors.>

One aspect of fault-tolerance in process control programs is the ability to tolerate sensor failure. This paper presents a methodology for transforming a process control program that cannot tolerate sensor failures into one that can. Issues addressed include modifying specifications in order to accommodate uncertainty in sensor values and averaging sensor values in a fault-tolerant manner. In addition, a hierarchy of sensor failure models is identified, and both the attainable accuracy and the run-time complexity of sensor averaging with respect to this hierarchy is discussed.

The design of a network file service that is tolerant to fail-stop failures and that can be run on top of a standard network file service is described. The fault-tolerance is completely transparent, so the resulting file system supports the same set of heterogeneous workstations and applications as the chosen standard, To demonstrate that the design can provide the benefit of highly available files at a reasonable cost to the user, a prototype has been implemented using the Sun NFS protocol. The approach is not limited to being used with NFS and should apply to any network file service built along the client-server model.>

To a client of a loosely-coupled distributed system, one of the simplest services is a time service. Usually the client simply requests the time from any subset of the time servers making up the service, and uses the first reply. Issues that need to be considered in other services, such as connection establishment or client authentication, need not be considered in a time service. The simplicity of this instruction, however, misrepresents the complexity of implementing such a service.