Search

The dynamic content distribution problem addresses the trade-off between storage and delivery costs in modern virtual content delivery networks (CDNs). That is, a video file can be stored in multip...

We initiate the study of error confinement in distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior, and only temporarily. The external behavior of all other nodes must remain impeccable, even though their internal state may be affected. Error confinement is impossible if an adversary is allowed to inflict arbitrary transient faults on the system, since the faults might completely wipe out input values. We introduce a new fault tolerance measure we call agility, which quantifies the strength of an algorithm that disseminate information, against state corrupting faults.We study the basic problem of broadcast, and propose algorithms that guarantee error confinement with optimal agility to within a constant factor, even in asynchronous networks when the topology is unknown. These algorithms can serve as building blocks in more general reactive systems. Previous results in exploring locality in reactive systems were not error confined, and relied on the assumption (not used in current paper) that the errors hitting each node are probabilistic, such that a faulty node itself, or its neighbor, can detect the node faulty.The main algorithm uses the novel core bootstrapping technique, that seems inherent for voting in reactive networks; its analysis leads to an interesting combinatorial problem. The technique and the analysis may be of independent interest

Multicast services, assisted by special hardware, are being considered as a part of high-speed wide-area networks (WANs) in order to support new generations of multiuser applications. This paper describes an application multicast service for high-speed WANs which is capable of exploiting multicast hardware. Indeed, this research was conducted in context of the spanning tree hardware structure of PARIS and of plaNET, the pioneering broadband experimental networks that predated ATM. The results of this research were also included in IBM's ATM, called Networking BroadBand Services (NBBS).We achieve modularity and low cost by assigning to distinct components the separate problems of: 1) naming groups; 2) finding group members in a network; 3) configuring multicast hardware; and 4) delivering multicast messages in sequence. This modularity enables, for example, both the multicast to a group to which the user initiates the joining (formed by using 1 and 2 above), on one hand, and to groups computed by the source on the other hand. We give the overall organization of our service and then describe in detail the methods used to solve the first two of the subproblems.

Traditional broadcast protocols are inappropriate for the high-speed networks of the future. Such protocols are limited by the speed of software processing, which becomes a bottleneck as network speeds increase. This paper presents broadcast protocols that are appropriate for high-speed networks, and are tolerant of failures involving the loss of messages. The protocols are based primarily on the simple hardware functions present in a high-speed network node. This leads to message delivery at hardware speeds. In the unlikely event of a failure, software intervention is required to guarantee the timely termination of the protocol; however, this software processing does not interfere with message delivery.

As communication networks grow, existing fault handling tools that involveglobalmeasures such as global time-outs or reset procedures become increasingly unaffordable, since their cost grows with the size of the network. Rather, for a fault handling mechanism to scale to large networks, its cost must depend only on the number of failed nodes (which, thanks to today's technology, grows much more slowly than the networks). Moreover, it should allow the nonfaulty regions of the networks to continue their operation even during the recovery of the faulty parts. This paper introduces the conceptsfault localityandfault-locally mendableproblems, which are problems for which there are correction algorithms (applied after faults) whose cost depends only on the (unknown) number of faults. We show thatanyinput-output problem is fault-locally mendable. The solution involves a novel technique combining data structures and “local votes” among nodes, which may be of interest in itself.

This work is concerned with the problem of broadcasting a large message efficiently when each processor has partial prior knowledge about the contents of the broadcast message. The partial information held by the processors might be out of date or otherwise erroneous, and consequently, different processors may hold conflicting information. Tight bounds are established for broadcast under such conditions, and applications of the broadcast protocol to other distributed computing problems are discussed.

A new paradigm for the design of self-stabilizing distributed algorithms, called local detection , is introduced. The essence of the paradigm is in defining a local condition based on the state of a processor and its immediate neighborhood such that the system is in a globally legal state if and only if the local condition is satisfied at all the nodes. In this work we also extend the model of self-stabilizing networks traditionally assuming memory failure to include the model of dynamic networks (assuming edge failures and recoveries). We apply the paradigm to the extended model which we call “dynamic self-stabilizing networks”. Without loss of generality, we present the results in the least restrictive shared memory model of read/write atomicity, to which end we construct basic information transfer primitives. Using local detection, we develop deterministic and randomized self-stabilizing algorithms that maintain a rooted spanning tree in a general network whose topology changes dynamically. The deterministic algorithm assumes unique identities while the randomized assumes an anonymous network. The algorithms use a constant number of memory words per edge in each node; and both the size of memory words and of messages is the number of bits necessary to represent a node identity (typically O (log n ) bits where n is the size of the network). These algorithms provide for the easy construction of self-stabilizing protocols for numerous tasks: reset, routing, topology-update and self-stabilization transformers that automatically self-stabilize existing protocols for which local detection conditions can be defined.

Afek, Awerbuch, Plotkin, and Saks identified an important fundamental problem inherent to distributed networks, which they called the Resource Controller problem. Consider, first, the problem in which one node (called the "root") is required to estimate the number of events that occurred all over the network. This counting problem can be viewed as a useful variant of the heavily studied and used task of topology update (that deals with collecting all remote information). The Resource Controller problem generalizes the counting problem: such remote events are considered as requests, and the counting node, i.e., the "root", also issues permits for the requests. That way, the number of request granted can be controlled (bounded).An efficient Resource Controller was constructed in the paper by Afek et al., which can operate on a dynamic network assuming that the network is spanned by a tree that may only grow, and only by allowing leaves to join the tree. In contrast, the Resource Controller presented here can operate under a more general dynamic model, allowing the spanning tree of the network to undergo both insertions and deletions of both leaves and internal nodes. Despite the more dynamic network model we allow, the message complexity of our controller is always at most the message complexity of the more restricted controller.All the applications for the controller of Afek et al. apply also for our controller. Moreover, with the same message complexity, our controller can handle these applications under the more general dynamic model mentioned above. In particular, under the more general dynamic model, the new controller can be transformed into an efficient size-estimation protocol, i.e., a protocol allowing the root to maintain a constant estimation of the number of nodes in the dynamically changing network. Informally, the resulted new size-estimation protocol uses O(log2n) amortized message complexity per topological change (assuming that the number of changes in the network size is "not too small"), where n is the current number of nodes in the network. In addition, with the same message complexity (as that of the size-estimation protocol), the new controller can be used to solve the name-assignment problem by assigning and maintaining unique log n+O(1)-bit identifiers for the nodes of the dynamic network.The new size-estimation protocol can be used for other applications, not mentioned in the paper by Afek et al.. Specifically, it can be used to extend many existing labeling schemes supporting different queries (e.g routing, ancestry, etc.) so that these schemes can now operate correctly also under more general models. These extensions maintain the same asymptotic sizes of the corresponding labels (or routing tables) of the original schemes and incur only a relatively low extra additive cost to the message complexity of the corresponding original schemes.

A control architecture for a high-speed packet-switched network is described. The architecture was designed and implemented as part of the PARIS (subsequently plaNET and BBNS) networking project at IBM. This high bandwidth network for integrated communication (data, voice, video) is currently operational as a laboratory prototype. It will also be deployed within the AURORA Testbed that is part of the NSF/DARPA gigabit networking program. The high bandwidth dictates the need for specialized hardware to support faster packet handling for both point-to-point and multicast connections. A faster and more efficient network control is also required in order to support the increased number of connections and their changing requirements with time. The new network control architecture presented exploits specialized hardware, thereby enabling tasks to be performed faster and with less computation overhead. In particular, since control information can be distributed quickly using hardware packet handling mechanisms, decisions can be made based upon more complete and accurate information. In some respects, this has the effect of having the benefits of centralized control (e.g., easier bandwidth resource allocation to connections), while retaining the fault tolerance and scalability of a distributed architecture. >

The Dynamic Content Distribution problem addresses the trade-off between storage and delivery costs in modern virtual Content Delivery Networks (CDNs). That is, a video file can be stored in multiple places so that the request of each user is served from a location that is near by to the user. This minimizes the delivery costs, but is associated with a storage cost. This problem is NP-hard even in grid networks. In this paper, we present a constant factor approximation algorithm for grid networks. We also present an O(logδ)-competitive algorithm, where δ is the normalized diameter of the network, for general networks with general metrics. We show a matching lower bound by using a reduction from online undirected Steiner tree. Our algorithms use a rather intuitive approach that has an elegant representation in geometric terms.

Network-on-Chip (NoC) is an evolving interconnection architecture addressing the rising complexity of system-on-chips (SoCs). We present a model for the cost of a NoC for a multiple use-case SoC, i.e., a system with distinct modes of operation, each having a unique traffic pattern. Specifically, we formulate an optimization problem capturing the fact that different use-cases can share capacity. We evaluate the proposed scheme using synthetic and real-life traffic, showing a substantial reduction of up to 27% in the required NoC resources, both when using a new algorithm we present and when using (a somewhat heavier) simulated-annealing procedure.

A traditional distributed system was, usually, designed by some centralized manufacturer and owned by some central owner. On the other hand, many modern distributed systems (e.g., many Peer to Peer (P2P) networks) are formed when people team up to pool their resources together to form such a system. We aim to initiate an investigation into the way people make a distributed decision on the composition of such a system, with the goal of realizing high values. Intuitively, we look at settings in which, by teaming up, a node increases its utility, however, it also pays a cost that often (as mentioned later) increases with the size of the system. The right balance is achieved by the right size system.

International audience; Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only. Hence, various extensions were suggested. We present a model that enhances the original model of population protocols by introducing a (weak) notion of speed of the agents. This enhancement allows us to design fast converging protocols with only weak requirements (for example, suppose that there are different types of agents, say agents attached to sick animals and to healthy animals, two meeting agents just need to be able to estimate which of them is faster, e.g., using their types, but not to actually know the speeds of their types). Then, using the new model, we study the gathering problem, in which there is an unknown number of anonymous agents that have values they should deliver to a base station (without replications). We develop efficient protocols step by step searching for an optimal solution and adapting to the size of the available memory. The protocols are simple, though their analysis is somewhat involved. We also present a more involved result - a lower bound on the length of the worst execution for any protocol. Our proofs introduce several techniques that may prove useful also in future studies of time in population protocols.

Most self-stabilizing protocols rely on checking every neighbor of a node continuously to detect failures. Such protocols have a high communication cost, especially in dense graphs. Conceivably, one can check neighbors less often, reducing the amount of communication per round. However, delaying the checking delays the fault detection and the stabilization, and therefore has the potential of increasing the total amount of communication overhead until stabilization. In this paper, we strive to reduce "after stabilization" overhead, without increasing the "before stabilization" overhead. For that, we investigate the potential effect of randomization on the communication efficiency of self-stabilizing protocols. We present randomized low communication self-stabilizing algorithms for several major tasks, namely, spanning tree construction, distributed reset, and unison. We study this approach in a complete graph, since there the communication overhead of checking seems the highest when one strives for protocols that are also fast.

We present a model for asynchronous mobile agent networks that takes into account the notion of speed of the agents. Then, we study the gathering problem (GP), in which an unknown number of anonymous agents have constant values they must deliver (only once) to a non mobile agent, the base station.

Developing self-stabilizing solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. This remark holds for a large variety of models. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an automatic transformer for algorithms in population protocols model . This model introduced recently for networks with a large number of resource-limited mobile agents. For our purposes, we use a variant of this model. Mainly, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication "speed" and considered through the notion of cover time . The automatic transformer takes as an input an algorithm solving a static problem and outputs a self-stabilizing algorithm for the same problem. We prove that our transformer is correct and we analyze its stabilization complexity.

The Edsger W. Dijkstra Prize in Distributed Computing is awarded for an outstanding paper on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade.

We study distributed algorithms for networks with undetectable fail-stop failures, assuming that all of them had occurred before the execution started. (It was proved that distributed agreement cannot be reached when a node may fail during execution.) Failures of this type are encountered, for example, during a recovery from a crash in the network. We study the problems of leader election and spanning tree construction, that have been characterized as fundamental for this environment. We point out that in presence of faults just duplicating messages in an existing algorithm does not suffice to make it resilient; actually, this redundancy gives rise to synchronization problems and also might increase the message complexity. In this paper we investigate the problem of making existing spanning tree algorithms fault-resilient, and still overcome these difficulties. Several lower bounds and optimal fault-resilient algorithms are presented for the first time.However, we believe that the main contribution of the paper is twofold: First, in designing the algorithms we use tools that thus argued to be rather general (for example, we extend the notion of token algorithms to multiple-token algorithms). In fact we are able to use them on several different algorithms, for several different families of networks. Second, following the amortized computational complexity, we introduce amortized message complexity as a tool for analyzing the message complexity.

The paper considers the design of energy-efficient online protocols for the basic problem of message transmission to hosts positioned at unknown distances in ad-hoc wireless networks. The paper formulates a number of variants of this problem and presents optimally competitive algorithms for those variants.

A self-stabilizing distributed protocol can recover from any state-corrupting fault. A self-stabilizing protocol is called adaptive if its recovery time is proportional to the number of processors hit by the fault. General adaptive protocols are known for the special case of function computations: these are tasks that map static distributed inputs to static distributed outputs. In reactive distributed systems, input values at each node change on-line, and dynamic distributed outputs are to be generated in response in an on-line fashion. To date, only some specific reactive tasks have had an adaptive implementation. In this paper we outline the first proof that all reactive tasks admit adaptive protocols. The key ingredient of the proof is an algorithm for distributing input values in an adaptive fashion. Our algorithm is optimal, up to a constant factor, in its fault resilience, response time, and recovery time.

An application for multicast service for high-speed WANs (wide area networks) which is capable of exploiting multicast hardware is described. Modularity and low cost area achieved by assigning to distinct components the separate problems of (1) naming groups, (2) finding group members in a network, (3) configuring multicast hardware, and (4) delivering multicast messages in sequence. The overall organization of the service is given, along with the methods used to solve the first two subproblems. >

The current trend in network technology is to implement as much of the switching function as possible directly in specialized high-speed hardware. A broadcast algorithm for such a network that is tolerant of failures in the form of message loss is presented. The model used is based on the one introduced by Cidon et al. (see Proc. of Seventh Annual ACM Symp. on Principles of Distributed Comput., Toronto, Canada. P.75-89, 1988); the hardware functions assumed are simple enough to be implemented in high-speed logic. The basic idea is to forward broadcast messages directly in hardware, thereby avoiding software-introduced delays. Software intervention (possible only after the broadcasted message has already been forwarded) is required only to ensure termination in case of failures. With high probability, the broadcast will terminate in time O(n tau /sub max/), where n is the number of nodes and tau /sub max/ is an upper bound on (variable) message delivery time across a link. >

The delivery of large files to single users, such as application programs for some versions of the envisioned network computer, or movies, is expected by many to be one of the main requirements of communication networks. This requires expensive high bandwidth capacity as well as fast and high storage servers. This motivates multimedia providers to optimize the delivery distances, as well as the electronic content allocation. A hierarchical architecture for providing the multimedia content was introduced by Nussbaumer, Patel, Schaffa, and Sternbenz (1994). They also introduced the trade-off between bandwidth and storage requirements for the placement of the content servers on the hierarchy tree. They found the best level of the hierarchy for the server location to minimize the total of the costs of communication and storage. Their algorithm is centralized. We solve the more general ease where servers can be located at different levels of the hierarchy. Our algorithm is distributed, and each node requires a limited memory capacity and computational power. Results for related approaches to caching design are of higher complexity. Results for related classic operations research problems are for centralized algorithms, mostly linear programming, that are not easy to convert into distributed algorithms. Instead, we observe that the use of dynamic programming is more natural for distributed implementations. For the specific problem at hand, we also managed to find a natural function (a generalization of the problem) that simplifies the combination operation used in dynamic programming. We also show how to map such contemporary problems to the area of classical plant location problems in operations research.

Many crucial network tasks such as database maintenance can be efficiently carried out given a tree that spans the network. By maintaining such a spanning tree, rather than constructing it "from-scratch" due to every topology change, one can improve the efficiency of the tree construction, as well as the efficiency of the protocols that use the tree. We present a protocol for this task which has communication complexity that is linear in the "actual" size of the biggest connected component. The time complexity of our protocol has only a polylogarithmic overhead in the "actual" size of the biggest connected component. The communication complexity of the previous solution, which was considered communication optimal, was linear in the network size, that is, unbounded as a function of the "actual" size of the biggest connected component. The overhead in the time measure of the previous solution was polynomial in the network size. In an asynchronous network it may not be clear what is the meaning of the "actual" size of the connected component at a given time. To capture this notion we define the virtual component and show that in asynchronous networks, in a sense, the notion of the virtual component is the closest one can get to the notion of the "actual" component.

As communication networks grow, existing fault handling tools become increasingly unaffordable. In many cases the reason is that they involve global measures such as global time-outs or reset procedures, and their cost grows with the size of the network. Rather, for a fault handling mechanism to scale to large networks, it should involve local measures, or, at worse, fault local measures, i.e. measures the cost of which depends only on the number of failed nodes (which, thanks to to-day's technology, grows much slower than the networks). This decreases the recovery time and, moreover, often allows the non-faulty regions of the networks to continue their operation even during the recovery of the faulty parts. We describe several research ideas that lead in this direction.

A self stabilizing protocol for constructing a rooted spanning tree in an arbitrary asynchronous network of processors that communicate through shared memory is presented. The processors have unique identifiers but are otherwise identical. The network topology is assumed to be dynamic, that is, edges can join or leave the computation before it eventually stabilizes.

This article deals with store-and-forward deadlock prevention in communication networks. The approach we adopt is that of establishing buffer classes in order to prevent cyclic waiting chains. This type of solutions usually tends to require many buffers. The main contribution is in showing that the number of required buffers can be reduced considerably by employing a hierarchical organization of the network. It proposes a new hierarchical scheme for arbitrary networks, that features a tradeoff between the communication overhead and the buffer requirements of the routing. This tradeoff can be shown to be close to optimal. >

The common practice in distributed algorithms research was to assume that the computation time is zero, and assign a cost only to the communication. This was justified at the times that the communication was the bottleneck of a network. However, lately there has been a dramatic increase in the capacity of communication links so that we can no longer make this assumption.

The problem of leader election in an asynchronous communication network with some faulty edges (and nodes) is studied. The election is needed in such cases in order to reorganize the network after failures have occurred. We present a fault-tolerant algorithm which guarantees commitment. The total number of messages is O(n2) and each message is O(log(MaxId)) bits (where n is the number of nodes and MaxId is the maximum identity). This improves a previous fault-tolerant algorithm. The algorithm can be used in networks in which message transmission is not restricted to the FIFO discipline. Thus the memory (or the time and messages) needed to simulate the FIFO discipline, is saved. The memory space needed in each node is only O(NodeDegree + log(MaxId)) (which is optimal when MaxID = nO(1)).

In this paper we develop a graph-oriented model for dealing with broadcasting in radio networks. Using this model, optimality in broadcasting protocols is defined, and it is shown that the problem of finding an optimal protocol is NP-hard. A polynomial time algorithm is proposed under which a channel is assigned to nodes from global, multiple-source broadcasting considerations. In particular, nodes participating in the broadcast do not interfere with each other's transmissions, but otherwise simultaneous channel reuse is permitted. Protocol implementations of this approach by frequency division and by time division are given. It is shown that, using these protocols, bounded delay for broadcasted messages can be guaranteed.

In future networks, transmission and switching capacity will dominate processing capacity. The authors investigate the way in which distributed algorithms should be changed in order to operate efficiently in this new environment. They introduce a class of new models for distributed algorithms which make explicit the difference between switching and processing. Based on these new models they define new message and time complexity measures which, they believe, capture the costs in many high-speed networks more accurately then traditional measures. In order to explore the consequences of the new models, they examine three problems in distributed computation. For the problem of maintaining network topology they devise a broadcast algorithm which takes O(n) messages and O(log n) time for a single broadcast in the new measure. For the problem of leader election they present a simple algorithm that uses O(n) messages and O(n) time. The third problem, distributed computation of a "globally sensitive" function, demonstrates some important features and tradeoffs in the new models and emphasizes and differences with the traditional network model. The results of the present paper influenced later research, as well as the design of IBM Networking Broadband Services (NBBS). >

The extensive use of open networks and distributed system poses serious threats to the security of end-to-end communications and network components themselves. A necessary foundation for securing a network is the ability to reliably authenticate communication partners and other network entities. One-way password-based authentication techniques are not sufficient to cope with the issues at hand. Modern designs rely on two-way cryptographic authentication protocols. However, most existing designs suffer from one or more limitations: they require synchronization of local clocks, they are subject to export restrictions because of the way they use cryptographic functions. they are not amenable to use in lower layers of network protocols because of the size and complexity of messages they use, etc. Designing suitable cryptographic protocols that cater to large and dynamic network communities but do not suffer from the above problems presents substantial challenges in terms of ease of use, efficiency, flexibility, and above all security. This paper discusses the above challenges; shows how a few simple protocols, including one proposed by ISO, can easily be broken; and derives a series of desirable properties that authentication protocols should exhibit to meet the requirements of future large and dynamic network communities. Then the paper describes a methodology that was developed to systematically build and test the security of a family of cryptographic two-way authentication protocols that are as simple as possible yet resistant to a wide class of attacks, efficient, easy to implement and use, and amenable to many different networking environments. It also discusses several concrete examples of protocols of that family that presents various advantages in specific distributed system scenarios.

International audience; The bandwidth demands on the World Wide Web continue to grow at an exponential rate. To address this problem, many research activities are focusing on the design of Web caches. Unfortunately, Web caches exhibit poor performance with a hit rate of about 30%. A solution to improve this rate, consists of groups of cooperating caches. In its most general form, a cooperative cache system includes protocols for hierarchical and transversal caching. Although such a system brings better performance, its drawback lies in the resulting network load due to the number of messages that need to be exchanged to locate an object. This paper introduces a new protocol for transversal cooperative caching, which significantly reduces the associated network load compared to that induced by existing systems