Search

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter $\Diam$. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sublinear in n, but linear in $\Diam$ (specifically, $O(\Diam + n^\varepsilon \cdot \log^* n)$ for $\varepsilon = \frac{\ln 3}{\ln 6} = 0.6131...$). Our result is achieved through the application of graph decomposition and edge-elimination-by-pipelining techniques that may be of independent interest.

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.

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.

This paper concerns {\em randomized} leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete $n$-node networks that runs in O(1) rounds and (with high probability) uses only $O(\sqrt{n}\log^{3/2} n)$ messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite $n$-node graph $G$ in $O(\tau(G))$ time and $O(\tau(G)\sqrt{n}\log^{3/2} n)$ messages, where $\tau(G)$ is the mixing time of a random walk on $G$. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient {\em deterministic} leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that $\Omega(\sqrt n)$ messages are needed for any leader election algorithm that succeeds with probability at least $1/e + \eps$, for any small constant $\eps > 0$. We view our results as a step towards understanding the randomized complexity ofleader election in distributed networks., Comment: Best Paper Award winner at ICDCN 2013, CDCN 2013 14th International Conference on Distributed Computing and Networking. Tata Institute of Fundamental Research, Mumbai, India

Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used is the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori information on the number of defective items, to the number of tests required by an optimal algorithm when the number of defective items is known in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvement over a previous algorithm due to Du and Hwang (1990) the competitive ratio of which is 2.75. It also proves a conjecture made by Du and Hwang. A new application of group testing techniques for high-speed network is discussed.

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.

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.

The resource discovery problem arises in the context of peer to peer (P2P) networks, where at any point of time a peer may be placed at or removed from any location over a general purpose network (e.g., an Internet site). A vertex (peer) can communicate with another vertex directly if and only if it knows a certain routing information to that other vertex. Hence, it is critical for peers to convey this routing information to each other. The problem was formalized by Harchol-Balter et al. (1999). The routing information needed for a vertex to reach another peer is that peer's identifier (e.g., IP address). A logical directed edge represents the fact that the peer at the tail of the edge knows the IP address of the one at its head. A number of algorithms were developed by Harchol-Balter et al. for this problem in the model of a synchronous network over a weakly connected directed graph. The best of these algorithms was randomized. Subsequently, a deterministic algorithm for the problem on synchronous networks with improved complexity was presented by Kutten et al. (2001). The current paper extends this deterministic algorithm to the environment of asynchronous networks, maintaining similar complexities (translated to the asynchronous model). These are lower than the complexities that would be needed to synchronize the system. The main technical difficulty in a directed, weakly connected system is to ensure that vertices take consistent steps, even if their knowledge about each other is not symmetric, and even if there is no timeout mechanism (which does exist in synchronous systems) to assist in that.

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter Diam. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sub-linear in n, but linear in Diam (specifically, O(Diam+n/sup 0.614/)). Our result is achieved through the application of graph decomposition and edge elimination techniques that may be of independent interest. >

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. >

It is shown that keeping track of history allows significant improvements in the realistic model of communication complexity of dynamic network protocols. The communication complexity for solving an arbitrary graph problem is improved from Theta (E) to Theta (V), thus achieving the lower bound. Moreover, O(V) is also the amortized complexity of solving an arbitrary function (not only graph functions) defined on the local inputs of the nodes. As a corollary, it is found that amortized communication complexity, i.e. incremental cost of adapting to a single topology change, can be smaller than the communication complexity of solving the problem from scratch. The first stage in the solution is a communication-optimal maintenance of a spanning tree in a dynamic network. The second stage is the optimal maintenance of replicas of databases. An important example of this task is the problem of updating the description of the network's topology at every node. For this problem the message complexity is improved from O(EV) to Theta (V). The improvement for a general database is even larger if the size of the database is larger than E. >

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. >

We focus on wavelength allocation schemes for all-optical WDM ring networks. For an N node network we characterize the traffic by its load L/sub max/ (the maximum number of lightpaths that share a link) and do not assume knowledge of the arrival/departure processes. We prove that shortest path routing produces a routing which has at most twice the load of the optimal solution. We show that at least 0.5 L/sub max/ log/sub 2/N+L/sub max/ wavelengths are required by any algorithm in the worst case, and develop an algorithm which requires up to 3 L/sub max/ log/sub 2/N wavelengths. For the case when the load is high and blocking is necessary we present an improved algorithm.

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.

This work concerns 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.

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 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.

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.

Greedy routing has been used in most of the proposed P2P networks because of several reasons. One of the main advantages is that greedy routing is very simple to implement and has some “implicit” fault-tolerance capabilities. It was however noticed that greedy routing usually produces paths of length larger than what would be required in a network of the given node degree. As an example some popular topologies like Chord have degree O(log n) and the greedy routing produces an average path length O(log n) whereas the lower bound is Ω(log n/log log n). The use of randomization allowed to show networks with optimal average path length. Recently a novel approach for routing in DHTs which improves on greedy routing has been proposed [4]. This approach, called NoN (Neighbors–of–Neighbors), substantially consists in making the greedy choice by looking not only at the neighbors of a node but at all the nodes at distance at most 2 from the node itself. The NoN approach together with the use of randomization in establishing the neighbors of the nodes which are present in the network, can optimally reduce the latency in several well known topologies. Hence the use of randomization, inspired by the Small-world idea introduced by Kleinberg [2], together with the NoN routing allows to maintain, to some extent, the advantages of greedy routing while optimizing the latency. Our goal is to retain the improvements given by the NoN routing over randomized networks, while eliminating the drawback in system overhead implied by this technique. In fact, randomization and NoN routing require the transmission to a node of its neighbors’s neighbors. While the authors in [4] argue that this can be done without extra cost by using keep-alive TCP messages, we eliminate the extracommunication at all and, similarly, eliminate the need of storing in each node its neighbors’s neighbors. To this aim we need to eliminate the random factor in establishing each neighbor of a node. In fact, determinism allows each node to calculate locally the neighbors of its neighbors. ∗ Work partially supported by EU RTN project ARACNE and by Italian FIRB WEBMINDS project

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