Proceedings - International Conference on Distributed Computing Systems

Distributing video over the Internet is an increasingly important application. Nevertheless, the real-time and high bandwidth requirements of video make video distribution over today's Internet a challenge. Adaptive approaches can be used to respond to changes in bandwidth availability while limiting the effect of such changes on perceptual quality and resource consumption. Nevertheless, most existing adaptation mechanisms have limited scalability and do not effectively exploit the heterogeneity of the Internet. In this paper, we describe the design and implementation of a MPEG video broadcasting service based on active networks. In an active network, routers can be programmed to make routing decisions based on local conditions. Because decisions are made locally, adaptation reacts rapidly to changing conditions and is unaffected by conditions elsewhere in the network. Programmability allows the adaptation policy to be tuned to the structure of the transmitted data, and to the properties of local clients. We use the PLAN-P domain-specific language for programming active routers; this language provides high-level abstractions and safety guarantees that allow complex protocols to be developed rapidly and reliably. Our experiments show that our approach to video distribution permits the decoding of up to 9 times as many frames in a heavily loaded network as distribution using standard routers.

Recent peer-to-peer (P2P) systems are characterized by decentralized control, large scale and extreme dynamism of their operating environment. As such, they can be seen as instances of complex adaptive systems (CAS) typically found in biological and social sciences. We describe Anthill, a framework to support the design, implementation and evaluation of P2P applications based on ideas such as multi-agent and evolutionary programming borrowed from CAS. An Anthill system consists of a dynamic network of peer nodes; societies of adaptive agents travel through this network, interacting with nodes and cooperating with other agents in order to solve complex problems. Anthill can be used to construct different classes of P2P services that exhibit resilience, adaptation and self-organization properties. We also describe preliminary experiences with Anthill in implementing a file sharing application.

We present a method of timestamping messages and events in synchronous computations that capture the order relationship with vectors of size less than or equal to the size of the vertex cover of the communication topology of the system. Our method is fundamentally different from the techniques of Fidge (1989) and Mattern (1989). The timestamps in our method do not use one component per process but still guarantee that the order relationship is captured accurately. Our algorithm is online and only requires piggybacking of timestamps on program messages. It is applicable to all programs that either use programming languages based on synchronous communication such as CSP or use synchronous remote procedure calls.

Version vectors and their variants play a central role in update tracking in optimistic distributed systems. Existing mechanisms for a variable number of participants use a mapping from identities to integers, and rely on some form of global configuration or distributed naming protocol to assign unique identifiers to each participant. These approaches are incompatible with replica creation under arbitrary partitions, a typical mode of operation in mobile or poorly connected environments. We present an update tracking mechanism that overcomes this limitation; it departs from the traditional mapping and avoids the use of integer counters, while providing all the functionality of version vectors in what concerns version tracking.

In this paper, we focus our attention on the problem of automating the addition of failsafe fault-tolerance where fault-tolerance is added to an existing (fault-intolerant) program. A failsafe fault-tolerant program satisfies its specification (including safety and liveness) in the absence of faults. And, in the presence of faults, it satisfies its safety specification. We present a somewhat unexpected result that, in general, the problem of adding failsafe fault-tolerance in distributed programs is NP-hard. Towards this end, we reduce the 3-SAT problem to the problem of adding failsafe fault-tolerance. We also identify a class of specifications, monotonic specifications and a class of programs, monotonic programs. Given a (positive) monotonic specification and a (negative) monotonic program, we show that failsafe fault-tolerance can be added in polynomial time. We note that the monotonicity restrictions are met for commonly encountered problems such as Byzantine agreement, distributed consensus, and atomic commitment. Finally, we argue that the restrictions on the specifications and programs are necessary to add failsafe fault-tolerance in polynomial time; we prove that if only one of these conditions is satisfied, the addition of failsafe fault-tolerance is still NP-hard.

Recent technology advances have enabled mediated query processing with Internet accessible WebSources. A characteristic of WebSources is that their access costs exhibit transient behavior These costs depend on the network and server workloads, which are often affected by, the time of day,, day, etc. Given transient behavior, an appropriate performance target (PT) for a noisy, environment will correspond to "at least X percentage of queries will have a latency of less than T units of time". In this paper we propose an optimizer strategy that is sensitive to the objective of meeting such performance targets (PT). For each query plan, a PT sensitive optimizer uses both the expected value of the cost distribution of the plan, as well as the expected delay, of the plan. We validate our strategy using a simulation based study of the optimizers behavior. We also experimentally validate the optimizer using traces of access costs for real WebSources.

Internet streaming applications are affected by adverse network conditions such as high packet loss rates and long delays. This paper aims at mitigating such effects by leveraging the availability of client-side caching proxies. We present a novel caching architecture and associated cache management algorithms that turn edge caches into accelerators of streaming media delivery. A salient feature of our caching algorithms is that they allow partial caching of streaming media objects and joint delivery of content from caches and origin servers. The caching algorithms we propose are both network-aware and stream-aware; they take into account the popularity of streaming media objects, their bit-rate requirements, and the available bandwidth between clients and servers. Using realistic models of Internet bandwidth derived from proxy cache logs and measured over real Internet paths, we have conducted simulations to evaluate the performance of various cache management alternatives. Our experiments demonstrate that network-aware caching algorithms can significantly reduce service delay and improve overall stream quality. Our experiments also show that partial caching is particularly effective when bandwidth variability is not very high.

Self-stabilization is a promising paradigm for achieving fault-tolerance of distributed systems. A self-stabilizing protocol can converge to its intended behavior even when it starts from any system configuration, and, thus, can tolerate any type and any number of transient faults. The PIF (propagation of information with feedback) scheme in a tree network allows the root process to broadcast its information to all other processes and to collect their responses. Many distributed systems utilize the PIF scheme as a fundamental communication scheme. This paper first formalizes the pipelined PIF in tree networks, and proposes a self-stabilizing protocol for the pipelined PIF. The protocol applies the PIF to a sequence of information in a pipelined fashion. The protocol has stabilizing time of O(h) (where h is the height of the tree network). After stabilization, it completes each PIF in O(h) asynchronous rounds and has throughput of O(1). Moreover, the protocol achieves fault-containment: for a complete binary tree network, its expected stabilizing time from 1-faulty configurations is O(1).

We propose a fully distributed system (as compared to centralized and partially distributed systems) for cost-sensitive data mining. Experimental results have shown that this approach achieves higher accuracy than both the centralized and partially distributed learning methods, however, it incurs much less training time, neither communication nor computation overhead.

Finding information in a peer-to-peer system currently requires either a costly and vulnerable central index, or flooding the network with queries. We introduce the concept of routing indices (RIs), which allow nodes to forward queries to neighbors that are more likely to have answers. If a node cannot answer a query, it forwards the query to a subset of its neighbors, based on its local RI, rather than by selecting neighbors at random or by flooding the network by forwarding the query to all neighbors. We present three RI schemes: the compound, the hop-count, and the exponential routing indices. We evaluate their performance via simulations, and find that RIs can improve performance by one or two orders of magnitude vs. a flooding-based system, and by up to 100% vs. a random forwarding system. We also discuss the tradeoffs between the different RI schemes and highlight the effects of key design variables on system performance.