We present a distributed self-adjusting algorithm for skip graphs that minimizes the average routing costs between arbitrary communication pairs by performing topological adaptation to the communication pattern. Our algorithm is fully decentralized, conforms to the CONGEST model (i.e. uses O(logn) bit messages), and requires O(logn) bits of memory for each node, where n is the total number of nodes. Upon each communication request, our algorithm first establishes communication by using the standard skip graph routing, and then locally and partially reconstructs the skip graph topology to perform topological adaptation. We propose a computational model for such algorithms, as well as a yardstick (working set property) to evaluate them. Our working set property can also be used to evaluate self-adjusting algorithms for other graph classes where multiple tree-like subgraphs overlap (e.g. hypercube networks). We derive a lower bound of the amortized routing cost for any algorithm that follows our model and serves an unknown sequence of communication requests. We show that the routing cost of our algorithm is at most a constant factor more than the amortized routing cost of any algorithm conforming to our computational model. We also show that the expected transformation cost for our algorithm is at most a logarithmic factor more than the amortized routing cost of any algorithm conforming to our computational model.

Modern web services rely on a network of distributed cache servers to efficiently deliver content to users. Load imbalance among cache servers can substantially degrade content delivery performance. Due to the skewed and dynamic nature of real-world workloads, cache servers that serve viral content experience higher load as compared to other cache servers. We propose a novel distributed load balancing protocol called Meezan to address the load imbalance among cache servers. Meezan replicates popular objects to mitigate skewness and adjusts hash space boundaries in response to load dynamics in a novel way. Our theoretical analysis shows that Meezan achieves near perfect load balancing for a wide range of operating parameters. Our trace driven simulations shows that Meezan reduces load imbalance by up to 52% as compared to prior solutions.

In this paper, we study a compositional approach to designing a class of stabilizing distributed systems. We show that the linear pipelined composition of a number of stabilizing modules is inherently stabilizing, and is a useful method of constructing scalable stabilizing solutions for streaming applications that are on the rise in peer-to-peer and sensor networks. We present the correctness proof and complexity analysis of the composition for a linear pipeline. Subsequently, we generalize the pipelined composition to alternative, concurrent, and repetitive versions, investigate the stabilization properties of these versions, and present a set of conditions under which these extended constructions retain their stabilization properties.

We describe a simple framework, called the transitive closure framework (TCF), for the self-stabilizing construction of any overlay network. The TCF is easy to reason about and algorithms derived from it stabilize within O(log n) more rounds than the optimal. As evidence of the power of this framework, we derive from the TCF a simple, self-stabilizing protocol for constructing Skip + graphs in O(log n) rounds.

The token ring is a seminal topic in self-stabilization research. It has been expanded to include multiple tokens, and improved upon using randomization to lower the state space requirements. In this brief announcement, we discuss how the two ideas can be brought together for an optimal solution to the multi-token ring problem.

Stabilizing distributed systems expect all the component processes to run predefined programs that are externally mandated. In Internet scale systems, this is unrealistic, since each process may have selfish interests and motives related to maximizing its own payoff. This article formulates the problem of selfish stabilization to show how competition blends with cooperation in a stabilizing environment.

Locating a center or a median in a graph is a fundamental graph-theoretic problem. Centers and medians are especially important in distributed systems because they are ideal locations for placing resources that need to be shared among different processes in a network. This paper presents simple self-stabilizing algorithms for locating centers and medians of trees. Since these algorithms are self-stabilizing, they can tolerate transient failures. In addition, they can automatically adjust to a dynamically changing tree topology. After the algorithms are presented, their correctness is proven and upper bounds on their time complexity are established. Finally, extensions of our algorithms to trees with arbitrary, positive edge costs are sketched.

No abstract available.

. Self-stabilization provides a non-masking approach to fault tolerance. Given this fact, one would hope that in a self-stabilizing system, the amount of disruption caused by a fault is proportional to the severity of the fault. However, this is not true for many self-stabilizing systems. Our paper addresses this weakness of distributed self-stabilizing systems by introducing the notion of fault containment. Informally, a fault-containing self-stabilizing algorithm is one that contains the effects of limited transient faults while retaining the property of self-stabilization. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. Then, it is shown that self-stabilization and fault containment are goals that can conflict. For example, it is shown that imposing a O(1) bound on the worst case recovery time from a 1-faulty state necessitates added overhead for stabilization: for some tasks, the O(1) recovery time implies stabiliz...

No abstract available.

No abstract available.

This paper is an exercise to construct a stabilizing mutual-exclusion protocol that withstands a single crash-failure. We begin with a collection of distributed processes arranged in a ring. The resulting protocol is stabilized by construction. Stabilizing protocols converge to a correct behavior regardless of their initial state. A faulty process is automatically removed from the system and, after repair, automatically integrated into the system. Our technique can be generalized to different systems by substituting appropriate protocols for various components.>

Dijkstra [4, 5] introduced the problem of self-stabilization in distributed systems as an interesting exercise for achieving global convergence through local actions. In [4] he presented three solutions to a specific version of the self-stabilization problem, one of which was proved in [6]. This paper presents an alternative solution of his self-stabilization problem with four-state machines.

A new class of Petri nets called regular nets is described.The structure of these nets guarantees liveness once the invanants are marked with tokens.Some graphical properties ofmvariants and variants are discussed.The concept of net labeling is introduced and a systematic method of synthesizing regular nets ts presented.It is shown how the safety of such nets can be trivially assured, thus producing live and safe control structures.

A simple algorithm for testing the 2-summability of Boolean functions is presented in this note. The concept of asummobility has been extended and the idea of "mutual 2-asummability" has been introduced. The authors show how mutual 2-asummobility can be utilized for the testing of isobaricity of threshold functions containing no more than seven variables.

Any switching function can always be realized by a single multithreshold threshold element possessing a suitable number of thresholds. However, the practical realization of such elements often presents serious difficulties; as such it becomes more convenient to realize the given function in the form of a network of multi-threshold threshold elements, each possessing fewer thresholds. In this paper, a thorough study of these networks with different modes of interconnection has been made. These discussions have been limited to constant weight (CW) networks only. Finally, a technique for obtaining the three-threshold network configuration for an arbitrary k-threshold function has also been suggested. It has been assumed that feedback loops are absent.

A decomposition and reconstruction approach for synthesizing an arbitrary Boolean function with a minimum number of threshold logic elements connected by feedforward paths only is presented. Attention is mainly focused on cascade-type realizations. The approach has the advantage that near-minimal solutions are readily derived. An estimate of how closely the minimality has been approached is obtainable in this method. The method has been successfully applied by the authors to Boolean functions of 5 and 6 variables.