This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or due to jamming). We consider a wireless network consisting of a set of n honest and reliable nodes within transmission (and interference) range of each other, and we model the external disruptions with a powerful adaptive adversary. This adversary may know the protocol and its entire history and can use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-ϵ)-fraction of the timesteps, for an arbitrary constant ϵ > 0 unknown to the nodes. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant (asymptotically optimal) throughput for the nonjammed time periods under any of the aforementioned adversarial strategies. The derived principles are also useful to build robust applications on top of the MAC layer, and we present an exemplary study for leader election, one of the most fundamental tasks in distributed computing.

Generalized matching problems arise in a number of applications, including computational advertising, recommender systems, and trade markets. Consider, for example, the problem of recommending multimedia items (e.g., DVDs) to users such that (1) users are recommended items that they are likely to be interested in, (2) every user gets neither too few nor too many recommendations, and (3) only items available in stock are recommended to users. State-of-the-art matching algorithms fail at coping with large real-world instances, which may involve millions of users and items. We propose the first distributed algorithm for computing near-optimal solutions to large-scale generalized matching problems like the one above. Our algorithm is designed to run on a small cluster of commodity nodes (or in a MapReduce environment), has strong approximation guarantees, and requires only a poly-logarithmic number of passes over the input. In particular, we propose a novel distributed algorithm to approximately solve mixed packing-covering linear programs, which include but are not limited to generalized matching problems. Experiments on real-world and synthetic data suggest that a practical variant of our algorithm scales to very large problem sizes and can be orders of magnitude faster than alternative approaches.

In this paper we study the “price of anarchy" for the general class of (weighted and unweighted) atomic “congestion games" with the sum of players' costs as the objective function. We show that for linear resource cost functions the price of anarchy is exactly $\frac{3 + \sqrt{5}}{2} \approx 2.618$ for weighted congestion games and exactly $2.5$ for unweighted congestion games. We show that for resource cost functions that are polynomials of degree $d$ the price of anarchy is $d^{\Theta(d)}$. Our results also hold for mixed strategies. In particular, these results apply to atomic routing games where the traffic demand from a source to a destination must be satisfied by choosing a single path between source and destination.

We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that allow (1 + ϵ) approximation and whose convergence time is essentially linear in the maximal path length, and is independent of the number of commodities and the size of the graph. Our algorithms use a very natural approximate steepest descent framework, combined with a blocking flow technique to speed up the convergence in distributed and parallel environment. Previously known solutions that achieved comparable convergence time and approximation ratio required exponential computational and space overhead per agent.

We develop a framework of distributed and stateless solutions for implicitly given packing linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. This is motivated by multi-commodity flow problems where flows can be split along possibly exponentially many paths.

Let $X=\{1,2,\ldots,n\}$ be a ground set of n elements, and let ${\cal S}$ be a family of subsets of X, $|{\cal S}|=m$, with a positive cost $c_S$ associated with each $S\in{\cal S}$. Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one by one. Once a new element is given, the algorithm has to cover it by some set of ${\cal S}$ containing it. We assume that the elements of X and the members of ${\cal S}$ are known in advance to the algorithm; however, the set $X'\subseteq X$ of elements given by the adversary is not known in advance to the algorithm. (In general, $X'$ may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let ${\cal C}$ denote the family of sets in ${\cal S}$ that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets ${\cal C}_{OPT}$ that covers $X'$. The performance of the algorithm is the ratio between the cost of ${\cal C}$ and the cost of ${\cal C}_{OPT}$. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an $O(\log m\log n)$ competitive deterministic algorithm for the problem and establish a nearly matching $\Omega\bigl(\frac{\log n\log m}{\log\log m+\log\log n}\bigr)$ lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm.

We develop a framework of distributed and stateless solutions for packing and covering linear programs (LPs), which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a separate “agent” controlling each variable, and an agent is allowed to read off the current values only of those constraints in which it has nonzero coefficients. This is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets. The most appealing features of our algorithms are their simplicity and polylogarithmic convergence. For the packing LP $\max\{c\cdot x\mid Ax\leq b,$ $x\geq0\}$, the algorithm associates a dual variable $y_i=\exp[\frac{1}{\epsilon}(\frac{A_ix}{b_i}-1)]$ for each constraint i, and each agent j iteratively increases (resp., decreases) $x_j$ multiplicatively if $A_j^\top y$ is too small (resp., large) as compared to $c_j$. Our algorithm, starting from a feasible solution, always maintains feasibility and computes a $(1+\epsilon)$ approximation in $\mathrm{poly}(\frac{\ln(mn\cdot A_{\max})}{\epsilon})$ rounds. Here m and n are number of rows and columns of A, and $A_{\max}$, also known as the “width” of the LP, is the ratio of the maximum and the minimum nonzero values taken by the expression $A_{ij}/(b_ic_j)$ as the pair $i,j$ varies over the matrix. A similar algorithm works for the covering LP $\min\{b\cdot y\mid A^\top y\geq c,$ $y\geq0\}$ as well. While exponential dual variables have been used in several packing/covering linear programming (LP) algorithms before [S. Plotkin, D. Shmoys, and E. Tardos, Math. Oper. Res., 20 (1995), pp. 257–301; Y. Bartal, J. W. Byers, and D. Raz, Proceedings of the IEEE Symposium on Foundations of Computer Science, 1997; N. Garg and J. Könemann, SIAM J. Comput., 37 (2007), pp. 630–652; L. K. Fleischer, SIAM J. Discrete Math., 13 (2000), pp. 505–520; N. E. Young, Proceedings of the IEEE Symposium on Foundations of Computer Science, 2001; C. Koufogiannakis and N. E. Young, Proceedings of the IEEE Symposium on Foundations of Computer Science, 2007], this is the first algorithm which is both stateless and has polylogarithmic convergence. Our algorithms can be thought of as applying distributed gradient descent/ascent on a carefully chosen potential. Our analysis differs from those of previous multiplicative update based algorithms and argues that while the current solution is far away from optimality, the potential function decreases/increases by a significant factor.

We consider solutions for distributed unsplittable multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. A requirement here is that each commodity routes its entire demand along a single path at any point in time. Assuming that the minimum capacity of any edge is at least polylogarithmic factor larger than the maximum demand of any commodity, we present a greedy distributed randomized algorithm, which with high probability, achieves 1+ε approximation, in O(H · logO(1)) m · (1/ε)0(1)) iterations where H ≤ n is an upper bound on the number edges allowed on any flow-path. No prior results exist for our distributed model.

We design a stateless and distributed solution to the problem of maximum multicommodity flows--route the maximum amount of flow between given source-sink pairs, possibly split along several paths, subject to edge-capacity constraints. Our main contribution is in extending the work of [1,2] to the case where the flow can be routed along possibly exponentially many different paths. Our algorithm, starting from an arbitrary feasible flow, always maintains a feasible flow, and reaches a 1 + ε approximation of maximum benefit value in Õ(n2) rounds.

In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is an adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon>0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it can be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel.

We study the speed of convergence of decentralized dynamics to approximately optimal solutions in potential games. We consider α-Nash dynamics in which a player makes a move if the improvement in his payoff is more than an α factor of his own payoff. Despite the known polynomial convergence of α-Nash dynamics to approximate Nash equilibria in symmetric congestion games [7], it has been shown that the convergence time to approximate Nash equilibria in asymmetric congestion games is exponential [25]. In contrast to this negative result, and as the main result of this paper, we show that for asymmetric congestion games with linear and polynomial delay functions, the convergence time of α-Nash dynamics to an approximate optimal solution is polynomial in the number of players, with approximation ratio that is arbitrarily close to the price of anarchy of the game. In particular, we show this polynomial convergence under the minimal liveness assumption that each player gets at least one chance to move in every T steps. We also prove that the same polynomial convergence result does not hold for (exact) best-response dynamics, showing the α-Nash dynamics is required. We extend these results for congestion games to other potential games including weighted congestion games with linear delay functions, cut games (also called party affiliation games) and market sharing games.

A fundamental network design problem is the one of Traffic Aggregation or Network Design. The goal is to design a network which is able to support a unit flow for each commodity, at a time, between its source-sink pair, e.g., to support buffered multicast traffic. When the flows are unsplittable, this corresponds to the Steiner forest problem and to the problem of sharing cost of multicast by different users.

We develop a framework of distributed and stateless solutions for packing and covering linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a separate "agent" controlling each variable and an agent is allowed to read-off the current values only of those constraints in which it has non-zero coefficients. This is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets.

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is O ( V ), where V is the number of nodes in the network. The message size used by the algorithm is O (log |ID|) where |ID| is the size of the name space of the nodes. Typically, log |ID| = O (log V ). Previous algorithms that adapt to dynamic networks involved Ω ( E ) messages per topological change—inherently paying for re-computation of the tree from scratch. Spanning trees are essential components in many distributed algorithms. Some examples include broadcast (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection , and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions.

Ah hoc networks offer increased coverage by using multihop communication. This architecture makes services more vulnerable to internal attacks coming from compromised nodes that behave arbitrarily to disrupt the network, also referred to as Byzantine attacks. In this work, we examine the impact of several Byzantine attacks performed by individual or colluding attackers. We propose ODSBR, the first on-demand routing protocol for ad hoc wireless networks that provides resilience to Byzantine attacks caused by individual or colluding nodes. The protocol uses an adaptive probing technique that detects a malicious link after log n faults have occurred, where n is the length of the path. Problematic links are avoided by using a route discovery mechanism that relies on a new metric that captures adversarial behavior. Our protocol never partitions the network and bounds the amount of damage caused by attackers. We demonstrate through simulations ODSBR's effectiveness in mitigating Byzantine attacks. Our analysis of the impact of these attacks versus the adversary's effort gives insights into their relative strengths, their interaction, and their importance when designing multihop wireless routing protocols.

The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures.

A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the following covering and packing problems, which are the dual of each other:

We consider the Active Min-Cost Measurement problem to minimize the cost incurred by measuring network link delays. Although the problem has a polynomial representation, its covering LP formulation, for which most of the previous distributed algorithms apply, has an exponential number of variables, one for each path.

A fundamental network design problem is the one of SteinerNetwork Design. The goal is to design a network which is able to support a unit flow for each commodity, at a time, between its source-sink pair. When the flows are unsplittable, this corresponds to the Steiner forest problem and to the problem of sharing cost of the multicast by different users. As a result of greedy selfish behavior of users in the network design game, the overall quality of the resulting solution is often not as good as the globally optimum solution of the underlying problem. We are therefore interested in the problem of designing distributed cost sharing mechanisms that induce the selfish agents to converge to the near-optimum solutions.

No abstract available.

We consider the problem of designing scalable and robust information systems based on multiple servers that can survive even massive denial-of-service (DoS) attacks. More precisely, we are focusing on designing a scalable distributed hash table (DHT) that is robust against so-called past insider attacks. In a past insider attack, an adversary knows everything about the system up to some time point t0 not known to the system. After t0, the adversary can attack the system with a massive DoS attack in which it can block a constant fraction of the servers of its choice. Yet, the system should be able to survive such an attack in a sense that for any set of lookup requests, one per non-blocked (i.e., non-DoS attacked) server, every lookup request to a data item that was last updated after t0 can be served by the system, and processing all the requests just needs polylogarithmic time and work at every server. We show that such a system can be designed.

We consider a model for sequential online decision-making by many diverse agents. On each day, each agent makes a decision, and pays a penalty if it is a mistake. Obviously, it would be good for agents to avoid repeating the same mistakes made by other agents; however, difficulty may arise when some agents disagree over what constitutes a mistake, perhaps maliciously.

We consider distributed algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. We seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. Our problem is analogous to recent work on oblivious routing [M. Bienkowski, M. Korzeniowski, and H. Räcke, Proceedings of the $15$th Annual ACM Symposium on Parallel Algorithms and Architectures, 2003, pp. 24–33, C. Harrelson, K. Hildrum, and S. Rao, Proceedings of the $15$th Annual ACM Symposium on Parallel Algorithms and Architectures, 2003, pp. 34–43, H. Räcke, Proceedings of the $43$rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 43–52] but with the objective of maximizing throughput rather than minimizing congestion. In contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm. This is accompanied by simple algorithms achieving upper bounds which are tight in terms of $\OPT$, the maximum throughput achievable by an omniscient algorithm, and are also tight in terms of m, the number of servers. Finally, we investigate an online version of the problem, in a restricted model which requires that clients, upon becoming active, must remain so for at least $log(n)$ time steps. In contrast to our primarily negative results in the oblivious case, here we present an algorithm which is constant-competitive. Our lower bounds justify the intuition, implicit in earlier work on the subject [B. Awerbuch and Y. Azar, Proceedings of the $35$th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 240–249], that some such restriction (i.e., requiring some stability in the demand pattern over time) is necessary in order to achieve a constant—or even polylogarithmic—competitive ratio.

A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local "pulse counter" that simulates the global clock in a synchronous network. In this paper, we present a time-optimal self-stabilizing scheme for such a synchronizer, assuming unbounded counters. We give a simple rule by which each node can compute its pulse number as a function of its neighbors' pulse numbers. We also show that some of the popular correction functions for phase clock synchronization are not self-stabilizing in asynchronous networks. Using our rule, the counters stabilize in time bounded by the diameter of the network, without invoking global operations. We argue that the use of unbounded counters can be justified by the availability of memory for counters that are large enough to be practically unbounded and by the existence of reset protocols that can be used to restart the counters in some rare cases where faults will make this necessary.

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar "taste" may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player's real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead.

The problem of scalable and robust distributed data storage has recently attracted a lot of attention. A common approach in the area of peer-to-peer systems has been to use a distributed hash table (or DHT). DHTs are based on the concept of virtual space. Peers and data items are mapped to points in that space, and local-control rules are used to decide, based on these virtual locations, how to interconnect the peers and how to map the data to the peers.DHTs are known to be highly scalable and easy to update as peers enter and leave the system. It is relatively easy to extend the DHT concept so that a constant fraction of faulty peers can be handled without any problems, but handling adversarial peers is very challenging. The biggest threats appear to be join-leave attacks (i.e., adaptive join-leave behavior by the adversarial peers) and attacks on the data management level (i.e., adaptive insert and lookup attacks by the adversarial peers) against which no provably robust mechanisms are known so far. Join-leave attacks, for example, may be used to isolate honest peers in the system, and attacks on the data management level may be used to create a high load-imbalance, seriously degrading the correctness and scalability of the system.We show, on a high level, that both of these threats can be handled in a scalable manner, even if a constant fraction of the peers in the system is adversarial, demonstrating that open systems for scalable distributed data storage that are robust against even massive adversarial behavior are feasible.

We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem, we have a communication network known to the algorithm in advance. What is not known in advance are the connectivity (bandwidth) or cut demands between vertices in the network which arrive online.We develop a unified framework for designing online algorithms for problems involving connectivity and cuts. We first present a general O (log m )-competitive deterministic algorithm for generating a fractional solution that satisfies the online connectivity or cut demands, where m is the number of edges in the graph. This may be of independent interest for solving fractional online bandwidth allocation problems, and is applicable to both directed and undirected graphs. We then show how to obtain integral solutions via an online rounding of the fractional solution. This part of the framework is problem dependent, and applies various tools including results on approximate max-flow min-cut for multicommodity flow, the Hierarchically Separated Trees (HST) method and its extensions, certain rounding techniques for dependent variables, and Räcke's new hierarchical decomposition of graphs.Specifically, our results for the integral case include an O (log m log n )-competitive randomized algorithm for the online nonmetric facility location problem and for a generalization of the problem called the multicast problem. In the nonmetric facility location problem, m is the number of facilities and n is the number of clients. The competitive ratio is nearly tight. We also present an O (log 2 n log k )-competitive randomized algorithm for the online group Steiner problem in trees and an O (log 3 n log k )-competitive randomized algorithm for the problem in general graphs, where n is the number of vertices in the graph and k is the number of groups. Finally, we design a deterministic O (log 3 n log log n )-competitive algorithm for the online multi-cut problem.

We consider a simple model for reputation systems such as the one used by eBay. In the model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m objects, some of which are bad. The goal of the honest players is to find a good object. To facilitate collaboration, the system maintains a shared billboard. A basic step of a player consists of consulting the billboard, probing an object to learn its true value, and posting the result on the billboard for the benefit of others. Probing an object incurs a unit cost to the player, and consulting the billboard is free. The dilemma of an honest player is how to balance between the desire to reduce its cost by taking advantage of the reports posted by honest peers, and the fear of being exploited by adopting reports posted by malicious players. In prior work, the authors presented an algorithm solving this problem in an asynchronous model, and the total cost of the probes made by honest players during the algorithm was analyzed. In this paper, the focus is on the individual cost, and a synchronous model in which each player takes a step in each round was considered. The prior algorithm has individual cost O(1/alphalog n) in this model, assuming that an alpha fraction of players are honest. In this paper, it is proven that no algorithm could guarantee individual cost of less than Omega(1/alpha), which is essentially constant if there are enough honest players. The main result is a new algorithm that achieves O(1) individual cost when there are many honest players, and achieves individual cost O((1/alpha)(log n/ log log n)) even when there are not. It is also shown that this algorithm generalizes to other interesting scenarios

An ad hoc wireless network is an autonomous self-organizing system of mobile nodes connected by wireless links where nodes not in direct range communicate via intermediary nodes. Routing in ad hoc networks is a challenging problem as a result of highly dynamic topology as well as bandwidth and energy constraints. In addition, security is critical in these networks due to the accessibility of the shared wireless medium and the cooperative nature of ad hoc networks. However, none of the existing routing algorithms can withstand a dynamic proactive adversarial attack. The routing protocol presented in this work attempts to provide throughput-competitive route selection against an adaptive adversary. A proof of the convergence time of our algorithm is presented as well as preliminary simulation results.

Survivable routing protocols are able to provide service in the presence of attacks and failures. The strongest attacks that protocols can experience are attacks where adversaries have full control of a number of authenticated nodes that behave arbitrarily to disrupt the network, also referred to as Byzantine attacks. This work examines the survivability of ad hoc wireless routing protocols in the presence of several Byzantine attacks: black holes, flood rushing, wormholes and overlay network wormholes. Traditional secure routing protocols that assume authenticated nodes can always be trusted, fail to defend against such attacks. Our protocol, ODSBR, is an on-demand wireless routing protocol able to provide correct service in the presence of failures and Byzantine attacks. We demonstrate through simulation its effectiveness in mitigating such attacks. Our analysis of the impact of these attacks versus the adversary’s effort gives insights into their relative strengths, their interaction and their importance when designing wireless routing protocols.

We consider a model with n players and m objects. Each player has a "preference vector" of length m that models his grade for each object. The grades are unknown to the players. A player can learn his grade for an object by probing that object, but performing a probe incurs cost. The goal of a player is to learn his preference vector with minimal cost, by adopting the results of probes performed by other players. To facilitate communication, we assume that players collaborate by posting their grades for objects on a shared billboard: reading from the billboard is free. We consider players whose preference vectors are popular, i.e., players whose preferences are common to many other players. We present distributed and sequential algorithms to solve the problem with logarithmic cost overhead.

The essence of the routing problem in real networks is that the traffic demand from a source to destination must be satisfied by choosing a single path between source and destination. The splittable version of this problem is when demand can be satisfied by many paths, namely a flow from source to destination. The unsplittable, or discrete version of the problem is more realistic yet is more complex from the algorithmic point of view; in some settings optimizing such unsplittable traffic flow is computationally intractable.In this paper, we assume this more realistic unsplittable model, and investigate the "price of anarchy", or deterioration of network performance measured in total traffic latency under the selfish user behavior. We show that for linear edge latency functions the price of anarchy is exactly $2.618 for weighted demand and exactly $2.5 for unweighted demand. These results are easily extended to (weighted or unweighted) atomic "congestion games", where paths are replaced by general subsets. We also show that for polynomials of degree d edge latency functions the price of anarchy is dδ(d). Our results hold also for mixed strategies.Previous results of Roughgarden and Tardos showed that for linear edge latency functions the price of anarchy is exactly 4/3 under the assumption that each user controls only a negligible fraction of the overall traffic (this result also holds for the splittable case). Note that under the assumption of negligible traffic pure and mixed strategies are equivalent and also splittable and unsplittable models are equivalent.

When many parties share network resources on an overlay network, mechanisms must exist to allocate the resources and protect the network from overload. Compared to large physical networks such as the Internet, in overlay networks the dimensions of the task are smaller, so new and possibly more effective techniques can be used. In this work we take a fresh look at the problem of flow control in multisender multigroup reliable multicast and unicast and explore a cost-benefit approach that works in conjunction with Internet standard protocols such as TCP. In contrast to existing window-based flow control schemes, we avoid end-to-end per sender or per group feedback by looking only at the state of the virtual links between participating nodes. This produces control traffic proportional only to the number of overlay network links and independent of the number of groups, senders, or receivers. We show the effectiveness of the resulting protocol through simulations and validate the simulations with live Internet experiments. We demonstrate near-optimal utilization of network resources, fair sharing of individual congested links, and quick adaptation to network changes.

We present the pulse protocol which is designed for multi-hop wireless infrastructure access. While similar to the more traditional access point model, it is extended to operate across multiple hops. This is particularly useful for conference, airport, or large corporate deployments. In these types of environments where users are highly mobile, energy efficiency becomes of great importance. The pulse protocol utilizes a periodic flood initiated at the network gateways which provides both routing and synchronization to the network. This synchronization is used to allow idle nodes to power off their radios for a large percentage of the time when they are not needed for packet forwarding. This results in substantial energy savings. Through simulation we validate the performance of the routing protocol with respect to both packet delivery and energy savings.

Electronic commerce engines like eBay depend heavily on reputation systems to improve customer confidence that electronic transactions will be successful, and to limit the economic damage done by disreputable peers defrauding others. In a reputation system, participant spost information about every transaction,and routinely check the posted information before taking any action to avoid other participants with a bad history.In this paper, we introduce a framework for optimizing reputation systems for objects.We study reputation systems in an asynchronous setting, and in the context of restricted access to the objects. Specifically, we study the cases where access may be restricted in time (objects arrive and depart from system) and inspace (each peer has access to only a subset of the objects).

In this paper we consider the problem of maintaining a consistent mapping of a virtual object space to a set of memory modules, i.e. the object space can be decomposed into a set of ranges where every module is responsible for exactly one range. A module owning some range R is responsible for storing all objects in R. Besides consistency, we require the mapping to be compact, i.e. any object or consecutive range of objects should be spread out over as few memory modules as possible. A compact mapping is important for many applications such as efficiently executing programs using a large amount of space or complex search queries such as semi-group range queries. Our main result assumes a static set of memory modules of uniform capacity, but we also show how to extend this to a dynamic set of memory modules of non-uniform capacity in a decentralized environment.In both settings, new objects may be added, old objects may be deleted, or objects may be modified over time. Each object consists of a set of data blocks of uniform size. So insert, delete, or modify operations on objects can be seen as insert or delete operations of data blocks. Each module can send or receive at most one data block in each unit of time and the injection of insert or delete requests for data blocks is under adversarial control. We prove asymptotically tight upper and lower bounds on the maximum rate at which the adversary can inject requests into the system so that a consistent and compact placement can be preserved without exceeding the capacity of a module at any time. Specifically, we show that in a (1-ε)-utilized system (i.e. the available space is used up to an ε fraction) the maximum injection rate that can be sustained is Θ(ε).

Minimal delay routing is a fundamental task in networks. Since delays depend on the (potentially unpredictable) traffic distribution, online delay optimization can be quite challenging. While uncertainty about the current network delays may make the current routing choices sub-optimal, the algorithm can nevertheless try to learn the traffic patterns and keep adapting its choice of routing paths so as to perform nearly as well as the best static path. This online shortest path problem is a special case of online linear optimization, a problem in which an online algorithm must choose, in each round, a strategy from some compact set S ⊆ Rd so as to try to minimize a linear cost function which is only revealed at the end of the round. Kalai and Vempala[4] gave an algorithm for such problems in the transparent feedback model, where the entire cost function is revealed at the end of the round. Here we present an algorithm for online linear optimization in the more challenging opaque feedback model, in which only the cost of the chosen strategy is revealed at the end of the round. In the special case of shortest paths, opaque feedback corresponds to the notion that in each round the algorithm learns only the end-to-end cost of the chosen path, not the cost of every edge in the network.We also present a second algorithm for online shortest paths, which solves the shortest-path problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs better than the first, as measured by their additive regret.

We consider the model of unreliable network links, where at each time unit a link might be either up or down. We consider two related problems. The first, establishing end to end communication between two given nodes, where the performance measure is the average number of times the chosen path was disconnected. The second, is to build a spanning tree rooted at a given source node, where the performance measure is the average number of nodes that are the disconnected from the source. For both problems we design competitive algorithms.

This paper presents a general methodology for building messagepassing peer-to-peer systems capable of performing prefix search for arbitrary user-defined names. Our methodology allows to achieve even load distribution, high fault-tolerance, and low-congestion concurrent query execution. This is the first known peer-to-peer system for prefix search with such properties. The essence of this methodology is a plug and play paradigm for designing a peer-to-peer system as a modular composition of arbitrary concurrent data structures.

Let X=[1,2,•••,n] be a ground set of n elements, and let S be a family of subsets of X, |S|=m, with a positive cost cS associated with each S ∈ S.Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one-by-one. Once a new element is given, the algorithm has to cover it by some set of S containing it. We assume that the elements of X and the members of S are known in advance to the algorithm, however, the set X' ⊆ X of elements given by the adversary is not known in advance to the algorithm. (In general, X' may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let C denote the family of sets in S that the algorithm chooses. At the end of the game the adversary also produces (off-line) a family of sets COPT that covers X'. The performance of the algorithm is the ratio between the cost of C and the cost of COPT. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm.We present an O(log m log n) competitive deterministic algorithm for the problem, and establish a nearly matching Ω(log n log m/log log m + log log n) lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting the fractional solution they supply into a deterministic online algorithm.

We describe a general technique for converting an online algorithm Β to a truthtelling mechanism. We require that the original online competitive algorithm has certain "niceness" properties in that actions on future requests are independent of the actual value of requests which were accepted (though these actions will of course depend upon the set of accepted requests). Under these conditions, we are able to give an online truthtelling mechanism (where the values of requests are given by bids which may not accurately represent the valuation of the requesters) such that our total profit is within O(ρ + log μ) of the optimum offline profit obtained by an omniscient algorithm (one which knows the true valuations of the users). Here ρ is the competitive ratio of Β for the optimization version of the problem, and μ is the ratio of the maximum to minimum valuation for a request. In general there is an Ω(log μ) lower bound on the ratio of worst-case profit for a truthtelling mechanism when compared to the profit obtained by an omniscient algorithm, so this result is in some sense best possible. In addition, we prove that our construction is resilient against many forms of "cheating" attempts, such as forming coalitions.We demonstrate applications of this result to several problems. We develop online truthtelling mechanisms for online routing and admission control of path or multicast requests, assuming large network capacities. Assuming the existance of an algorithm Β for the optimization version of the problem, our techniques provide truthtelling mechanisms for general combinatorial auctions. However, designing optimization algorithms may be difficult in general because of online or approximation lower bounds. For the cases described above, we are able to design optimization algorithms Β by amortizing the lost benefit from online computation (and from approximation hardness in the case of multicast) against the benefit obtained from accepted requests.We comment that our upper bounds on profit competitiveness imply, as an obvious corollary, similar bound on global efficiency, namely overall well-being of all the users. This contrasts with most other work on truthtelling mechanisms for general online resource allocation, where only efficiency is maximized, and competitiveness can be arbitrarily poor.

We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and online settings, can be significantly improved if we allow preemption, i.e., interrupt a job and later continue its execution, perhaps migrating it to a different machine. Preemption is inherent to make a scheduling algorithm efficient. While in the case of a single processor most operating systems can easily handle preemptions, migrating a job to a different machine results in a huge overhead. Thus, it is not commonly used in most multiprocessor operating systems. The natural question is whether migration is an inherent component for an efficient scheduling algorithm in either the online or offline setting. Leonardi and Raz [Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 110--119] showed that the well-known algorithm, shortest remaining processing time (SRPT), performs within a logarithmic factor of the optimal offline algorithm. Note that SRPT must use both preemption and migration to schedule the jobs. It is not known if better approximation factors can be reached and thus SRPT, although it is an online algorithm, becomes the best known algorithm in the offline setting. In fact, in the online setting, Leonardi and Raz showed that no algorithm can achieve a better bound. Without migration, no (offline or online) approximations are known. This paper introduces a new algorithm that does not use migration, works online, and is just as effective (in terms of approximation ratio) as the best known offline algorithm that uses migration.

In this paper we consider the problem of delivering dynamically changing input streams in dynamically changing networks where both the topology and the input streams can change in an unpredictable way. In particular, we present two simple distributed balancing algorithms (one for packet injections and one for flow injections) and show that for the case of a single receiver these algorithms will always ensure that the number of packets or flow in the system is bounded at any time step, even for an injection process that completely saturates the capacities of the available edges and even if the network topology changes in a completely unpredictable way. We also show that the maximum number of packets or flow that can be in the system at any time is essentially best possible by providing a lower bound that holds for any online algorithm, whether distributed or not. Interestingly, our balancing algorithms do not behave well in a completely adversarial setting. We show that also in the other extreme of a static network and a static injection pattern the algorithms will converge to a point in which they achieve an average routing time that is close to the best possible average routing time that can be achieved by any strategy. This demonstrates that there are simple algorithms that can be efficient for very different scenarios.

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of stability —will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n -node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n ). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay. Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

This paper addresses the problem of aggregating the topology of a sub-network in a compact way with minimum distortion. The problem arises from networks that have a hierarchical structure, where each sub-network must advertise the cost of routing between each pair of its border nodes. The straight-forward solution of advertising the exact cost for each pair has a quadratic cost which is not practical. We look at the realistic scenario of networks where all links are bidirectional, but their cost (or distance) in the opposite directions might differ significantly. The paper presents a solution with distortion that is bounded by the logarithm of the number of border nodes and the square-root of the asymmetry in the cost of a link. This is the first time that a theoretical bound is given to an undirected graph. We show how to apply our solution to PNNI, and suggest some other heuristics that are tested to perform better than the provenly bounded solution.

Managing a large collection of networked machines, with a series of incoming jobs, requires that the jobs be assigned to machines wisely. A new approach to this problem is presented, inspired by economic principles: the Cost–Benefit framework. This framework simplifies complex assignment and admission control decisions, and performs well in practice. We demonstrate this framework in the context of an Internet-wide market for computational services and verify its utility for a classic network of workstations.

A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and shown to be useful in practice. This "opportunity cost" method converts the usage of several heterogeneous resources in a machine to a single homogeneous "cost." Assignment and reassignment are then performed based on that cost. This is in contrast to traditional, ad hoc methods for job assignment and reassignment. These treated each resource as an independent entity with its own constraints, as there was no clean way to balance one resource against another. Our method has been tested by simulations, as well as real executions, and was found to perform well.

We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (tota time in the system).The performance of the algorithm, both in offline and online settings, can be significantly improved if we allow preemption: i.e., intermpt a job and later continue its execution, perhaps migrating it to a different machine.Preemption is inherent to make a scheduling algorithm efficient.While in case of a single processor, most operating systems can easily handle preemptions, migrating a job to a different machine results in a huge overhead.Thus, it is not commonly used in most multiprocessor operating systems.The natural question is whether migration is an inherent component for an efficient scheduling algorithm, in either online or offline setting.Leonardi and Raz (STOC'97) showed that the well known algorithm, shortest remaining processing time (SRF'I'), performs within a logarithmic factor of the optimal algorithm.Note that SRPT must use both preemption and migration to schedule the jobs.It is not known if better approximation factors can be reached.In fact, in the on-line setting, Leonardi and Raz showed that no algorithm

We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph G=(V, E) in which the robot explores every vertex and edge in the graph by traversing at most O(E+V1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E+V2) edges. We also give an application of piecemeal learning to the problem of searching a graph for a “treasure.”

We introduce a new traversal technique in the context of piecemeal exploration of unknown graphs. The problem of learning a graph via piecemeal exploration requires a robot to create a complete map of its environment, subject to two constraints. First, it cannot jump between non-adjacent vertices in one time step and second, it must return to a fixed starting point every so often. This paper presents the recursive piecemeal search (RPS) strategy together with an algorithm for the above problem. We are able to achieve O(log 2 n) overhead (where n is the number of vertices), improving on previous results of Awerbuch, Betke, Rivest, and Singh which require O(n ffl ) overhead. The graph is discovered via the recursive piecemeal search, which can be viewed as a combination of breadth-first and depth-first passes. The construction of RPS trees relies on the concept of sparse neighborhood covers and captures nicely the nature of the graph exploration problem. This paper is eligible for ...

Networks deploying hierarchical routing are recursively partitioned into sub-networks that do not reveal the full details of their internal structure outside their domains. Instead, an aggregated view of certain parameters that are associated with traversal within such sub-networks between their border nodes is advertised. The ATM PNNI standard and the Internet Nimrod architecture both adopt this approach for routing. This paper studies the effectiveness of ATM hierarchical routing protocols on networks with different hierarchical structures by simulation. Our study shows that in general, the hierarchical source routing performs well compared to the global routing strategy which imposes no hierarchy, while utilizing less storage and communication overhead. For certain networks and topologies, the hierarchical routing performs better than the global routing. Different hierarchies imposed on the same topologies have significantly different performance on the throughput and routing delay. This suggests the necessity of studying the hierarchy design for communication networks using hierarchical routing.

Max-min is a frequently praised criterion for flow control despite its limitations. In practice, the fast rate of changes in the connection layout in modern networks makes it hard for any flow control algorithm to converge to an optimal point. In such an environment, it might be better to trade accuracy with speed. We present algorithms that relax the optimality criterion of the max-min flow fairness but achieve a fast convergence time that is logarithmic in the link bandwidth and not a function of the number of active connections (or sessions). The relaxation we use requires rates to be increased or decreased by a certain factor, 1+/spl epsiv/, or in other words, assigned rates can only be a natural power of some basic bandwidth 1+/spl epsiv/. Under this criterion, the quiescent time of our flow control algorithms is log/sub 1+/spl epsiv//B, where B is the maximum link bandwidth in minimum allocation units. This is a great improvement over the super-linear quiescent time of known algorithms both exact and approximated.

In the future, global networks will consist of a hierarchy of subnetworks called domains. For reasons of both scalability and security, domains will not reveal details of their internal structure to outside nodes. Instead, these domains will advertise only a summary, or aggregated view, of their internal structure, e.g., as proposed by the ATM PNNI standard. This work compares, by simulation, the performance of several different aggregation schemes in terms of network throughput (the fraction of attempted connections that are realized), and network control load (the average number of crankbacks per realized connection.) Our main results are: the minimum spanning tree is a good aggregation scheme; exponential link cost functions perform better than min-hop routing; our suggested logarithmic update scheme that determines when re-aggregation should be computed can significantly reduce the computational overhead due to re-aggregation with a negligible decrease in performance.

This paper addresses the problem of aggregating the topology of a sub-network in a compact way with minimum distortion. The problem arises from networks that have a hierarchical structure, where each sub-network must advertise the cost of routing between each pair of its border nodes. The straightforward solution of advertising the exact cost for each pair has a quadratic cost which is not practical. We look at the realistic scenario of networks where all links are bidirectional, but their cost (or distance) in the opposite directions might differ significantly. The paper presents a solution with distortion that is bounded by the logarithm of the number of border nodes and the square-root of the asymmetry in the cost of a link. This is the first time that a theoretical bound is given to an undirected graph. We show how to apply our solution to the ATM PNNI standard.

We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the number of brushes that can be sold in that city. What is the best route to take to sell the quota while traveling the least distance possible? Notice that unlike the standard traveling salesman problem, not only do we need to figure out the order in which to visit the cities, but we must decide the more fundamental question: which cities do we want to visit? In this paper we give the first approximation algorithm having a polylogarithmic performance guarantee for this problem, as well as for the slightly more general "prize-collecting traveling salesman problem" (PCTSP) of Balas, and a variation we call the "bank robber problem" (also called the "orienteering problem" by Golden, Levi, and Vohra). We do this by providing an O(log 2 k) approximation to the somewhat cleaner k-MST problem which is defined as follows. Given an undirected graph on n nodes with nonnegative edge weights and an integer $k \leq n$, find the tree of least weight that spans k vertices. (If desired, one may specify in the problem a "root vertex" that must be in the tree as well.) Our result improves on the previous best bound of $O(\sqrt{k})$ of Ravi et al.

This paper introduces a near-linear time sequential algorithm for constructing a sparse neighborhood cover. This implies analogous improvements (from quadratic to near-linear time) for any problem whose solution relies on network decompositions, including small edge cuts in planar graphs, approximate shortest paths, and weight- and distance-preserving graph spanners. In particular, an O(log n) approximation to the k-shortest paths problem on an n-vertex, E-edge graph is obtained that runs in $\soh{n + E + k}$ time.

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.

The essence of the simplest buy-at-bulk network design problem is buying network capacity "wholesale" to guarantee connectivity from all network nodes to a certain central network switch. Capacity is sold with "volume discount": the more capacity is bought, the cheaper is the price per unit of bandwidth. We provide O(log/sup 2/n) randomized approximation algorithm for the problem. This solves the open problem in Salman et al. (1997). The only previously known solutions were restricted to special cases (Euclidean graphs). We solve additional natural variations of the problem, such as multi-sink network design, as well as selective network design. These problems can be viewed as generalizations of the the Generalized Steiner Connectivity and Prize-collecting salesman (K-MST) problems. In the selective network design problem, some subset of /spl kappa/ wells must be connected to the (single) refinery, so that the total cost is minimized.

Multicast routing and admission control can be defined as follows. Various network users issue online requests for a connection to certain multicast sources. The network either connects this request or rejects it (admission control decision). If request is connected, a path with sufficient bandwidth is established starting at the requesting user and ending either at the source or at one of the users previously connected to the same source (route selection decision). The goal of these admission control and route selection decisions is to maximize total number of users connected (i.e. total thruput) subject to the network capacity constraints. This problem can be reduced to the online maximal dense tree problem: Upon a service request from a node in a weighted graph with a distinguished source, the node is either rejected or connected to the tree of previously connected nodes. The goal is to maximize the total number of requests while keeping the density (ratio of accepted re...

A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. A primary example is the maintenance, for routing and other purposes, of a record of the current topology of the system. Such a database must be updated in the wake of locally generated changes to its contents. Due to previous disconnections of parts of the network, a maintenance protocol may need to update processors holding widely varying versions of the database. We provide a deterministic protocol for this problem, with only polylogarithmic overhead in both time and communication complexities. Previous deterministic solutions required polynomial overhead in at least one of these measures.

In this paper we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic adversarial model of packet generation and path determination for which the time-averaged injection rate of packets requiring the use of any edge is limited to be less than 1. A crucial issue that arises in such a setting is that of stability-will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly-used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size. Our results resolve several questions posed by Borodin et al. and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

Article Free Access Share on Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract) Authors: Baruch Awerbuch Johns Hopkins University and Lab. for Computer Science, MIT Johns Hopkins University and Lab. for Computer Science, MITView Profile , Yossi Azar Department of Computer Science, Tel-Aviv University, Israel Department of Computer Science, Tel-Aviv University, IsraelView Profile , Amos Fiat Department of Computer Science, Tel-Aviv University, Israel Department of Computer Science, Tel-Aviv University, IsraelView Profile , Tom Leighton Mathematics Department and Lab for Computer Science, MIT Mathematics Department and Lab for Computer Science, MITView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 519–530https://doi.org/10.1145/237814.238000Published:01 July 1996Publication History 54citation583DownloadsMetricsTotal Citations54Total Downloads583Last 12 Months24Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper introduces a new distributed data object called Resource Controller that provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of resources that may be managed by such an object include; number of messages sent, number of nodes participating in the protocol, and total CPU time consumed. The Resource Controller object is accessed through a procedure that can be invoked at any node in the network. Before consuming a unit of resource at some node, the controlled algorithm should invoke the procedure at this node, requesting a permit or a rejection. The key characteristics of the Resource Controller object are the constraints that it imposes on the global resource consumption. An (M, W)-Controller guarantees that the total number of permits granted is at mostM; it also ensures that, if a request is rejected, then at leastM—Wpermits are eventually granted, even if no more requests are made after the rejected one. In this paper, we describe several message and space-efficient implementations of the Resource Controller object. In particular, we present an (M, W)-Controller whose message complexity isO(nlog2nlog(M/(W+ 1)) wherenis the total number of nodes. This is in contrast to theO(nM)message complexity of a fully centralized controller which maintains a global counter of the number of granted permits at some distinguished node and relays all the requests to the node.

This paper presents deterministic sublinear-time distributed algorithms for network decomposition and for constructing a sparse neighborhood cover of a network. The latter construction leads to improved distributed preprocessing time for a number of distributed algorithms, including all-pairs shortest paths computation, load balancing, broadcast, and bandwidth management.

) Baruch Awerbuch y Margrit Betke Ronald L. Rivest Mona Singh Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 Abstract We study the problem of learning a graph by piecemeal exploration, in which a mobile robot must return every so often to its starting point (for refueling, say). We assume that the robot can distinguish vertices and edges which it has already explored. We present an algorithm for piecemeal learning an unknown undirected graph G = (V; E) in which the robot explores every vertex and edge in G by traversing at most O(E + V 1+o(1) ) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E + V 2 ) edges. We also address the related problem of searching a graph for a particular distinguished location or treasure. If this location or treasure is known to be near the starting point, then the robot should search in a breadth-first manner from the starting point. We gi...

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion. Traditionally, the assignment of jobs to servers is measured by the L/sub /spl infin// norm; in other words, an assignment of jobs to servers is quantified by the maximum load assigned to any server. In this measure the performance of the greedy load balancing algorithm may be a logarithmic factor higher than the offline optimal. In many applications, the L/sub /spl infin// norm is not a suitable way to measure how well the jobs are balanced, If each job sees a delay that is proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the squares of the numbers of jobs assigned to the servers. Minimizing the average delay is equivalent to minimizing the Euclidean (or L/sub 2/) norm. For any fixed p, 1/spl les/p</spl infin/, we show that the greedy algorithm performs within a constant factor of the offline optimal with respect to the L/sub p/ norm. The constant grows linearly with p, which is best possible, but does not depend on the number of servers and jobs.

Hochbaum(which has since been improved to a constant factor at this conference) for the special case of points in 2-dimensional Euclidean space.

This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic concept ofregional matching, and demonstrates how finding a regional matching with certain parameters enables efficient tracking. The communication overhead of our tracking mechanism is within a polylogarithmic factor of the lower bound.

The work is motivated by deadlock resolution and resource allocation problems, occurring in distributed server-client architectures. We consider a very general setting which includes, as special cases, distributed bandwidth management in communication networks, as well as variations of classical problems in distributed computing and communication networking such as deadlock: resolution and "dining philosophers". In the current paper, we exhibit first local solutions with globally-optimum performance guarantees. An application of our method is distributed bandwidth management in communication networks. In this setting, deadlock resolution (and maximum fractional independent set) corresponds to admission control maximizing network throughput. Job scheduling (and minimum fractional coloring) corresponds to route selection that minimizes load.>

This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems arise in numerous applications, including video-servers, real-lime database servers, and the provision of permanent virtual channel in large-scale communications networks. The paper describes both upper and lower bounds on the competitive ratio of algorithms for admission control and virtual circuit routing in trees, arrays, and hypercubes (the networks most commonly used in conjunction with nigh performance computing and communication). Our results include optimal algorithms for admission control and virtual circuit routing in trees, as well as the first competitive algorithms for these problems on non-tree networks. A key result of our research is the development of on-line algorithms that substantially outperform the greedy-based approaches that are used in practice.>

Many important protocols in distributed computing have simple and elegant solutions if one allows the assumption of unbounded size registers. This assumption can be simulated in practice using sufficiently large but bounded registers; however the resulting protocols are extremely vulnerable to transient faults. The authors present a general methodology for the transformation of unbounded register protocols so that they can work with bounded registers in a self-stabilizing fashion. The applicability of this method is demonstrated with two examples: spanning tree computation and topology update.>

) Baruch Awerbuch Rafail Ostrovsky y August 15, 1994 Abstract In this paper we consider the question of fault-tolerant distributed network protocols with extremely small memory requirements per processor. In particular, we show that even in the case of worst-case transient faults (i.e., in a self-stabilizing setting), many fundamental network protocols can be achieved using only O(log n) bits of memory per incident network edge. In the heart of our construction is a self-stabilizing asynchronous network reset protocol with the same small memory requirements. Johns Hopkins University, Baltimore, MD 21218, and MIT Lab. for Computer Science. E-mail: [email protected]. Supported by Air Force Contract TNDGAFOSR-86-0078, ARPA/Army contract DABT63-93-C-0038, ARO contract DAAL03-86-K-0171, NSF contract 9114440-CCR, DARPA contract N00014-J-92-1799. y U.C. Berkeley and ICSI. Supported by NSF postdoctoral fellowship and ICSI. E-mail: [email protected]. 1 1 Introduction...

Thw paper considers symmetry-breakhg in an aaynchronoue d~tributed network.We present and analyze a randomized protocol that constructs a maximal independent set in O(log n) expected time, and also a protocol for the dining philosophers problem that schedules a job that competes with 6 other jobs in expected 0(6) time, which is optimal.The beat previous algorithms for dining philosophers achieved only 0(62).In addition, the new protocols are 2-wait-/iwe which means that delays at a process are only dependent on processors or links at most distance two in the communication graph.1. Design a round-based protocol that performs well in a synchronous distributed network.

In this paper, we describe a very simple boundedqueuesize local-control algorithm for routing multicommodity flows in a dynamically-changing distributed network. The algorithm is based on the edge-balancing approach described in [AL93], but has the added benefits of: 1. a much improved running time, and 2. working even in networks where edge capacities can vary in an unpredictable and unknown fashion. In fact, the sequential running time of the algorithm is now comparable to (and, in some cases, better than) the time of the best previously known approximation algorithms for the multi-commodity flow problem in a fixed network [LMP + 91]. The fact that the new algorithm works well in dynamically changing networks means that problems such as end-to-end communication and load balancing [AMS89, AGR92, AAMR93] can now be solved in Johns Hopkins University, Baltimore, MD 21218-2694, and MIT Laboratory for Computer Science, Cambridge MA 02139. Email: [email protected]. Supported by...

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. We propose two modifications to the algorithm which result in a polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (>

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

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to completion and no reroutings are allowed. The "no rerouting" restriction appears in all the proposals for future high-speed networks and stems from current hardware limitations, in particular the fact that the bandwidth-delay product of the newly developed optical communication links far exceeds the buffer capacity of the network. In case the goal is to maximize the throughput, our framework yields an on-line O(log nT)-competitive strategy, where n is the number of nodes in the network and T is the maximum call duration. In other words, our strategy results in throughput that is within O(log nT) factor of the highest possible throughput achievable by an omniscient algorithm that knows all of the requests in advance. Moreover, we show that no on-line strategy can achieve a better competitive ratio. Our framework leads to competitive strategies applicable in several more general settings. Extensions include assigning each connection an associated "profit" that represents the importance of this connection, and addressing the issue of call-establishment costs.>

This paper introduces the first near-linear (specifically, O(Elog n+nlog/sup 2/ n)) time algorithm for constructing a sparse neighborhood cover in sequential and distributed environments. This automatically implies analogous improvements (from quadratic to near-linear) to all the results in the literature that rely on network decompositions, both in sequential and distributed domains, including adaptive routing schemes with O/spl tilde/(1) stretch and memory, small edge cuts in planar graphs, sequential algorithms for dynamic approximate shortest paths with O/spl tilde/(E) cost for edge insertion/deletion and O/spl tilde/(1) time to answer shortest-path queries, weight and distance-preserving graph spanners with O/spl tilde/(E) running time and space, and distributed asynchronous "from-scratch" breadth-first-search and network synchronizer constructions with O/spl tilde/(1) message and space overhead (down from O(n)).>

This paper gives a randomized competitive distributed paging algorithm called Heat and Dump, The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to within a constant factor. This is in contrast to the linear optimal deterministic competitive ratio.>

In this paper, we describe a very simple (1+/spl epsi/)-approximation algorithm for the multicommodity flow problem. The algorithm runs in time that is polynomial in N (the number of nodes in the network) and /spl epsiv//sup -1/ (the closeness of the approximation to optimal). The algorithm is remarkable in that it is much simpler than all known polynomial time flow algorithms (including algorithms for the special case of one-commodity flow). In particular, the algorithm does not rely on augmenting paths, shortest paths, min-cost paths, or similar techniques to push flow through a network. In fact, no explicit attempt is ever made to push flow towards a sink during the algorithm. Because the algorithm is so simple, it can be applied to a variety of problems for which centralized decision making and flow planning is not possible. For example, the algorithm can be easily implemented with local control in a distributed network and it can be made tolerant to link failures. In addition, the algorithm appears to perform well in practice. Initial experiments using the DIMACS generator of test problems indicate that the algorithm performs as well as or better than previously known algorithms, at least for certain test problems.>

This paper presents a simple local algorithm for load balancing in a distributed network.The algorithm makes no assumption about the structure of the network.It can be executed on a synchronous network with fixed topology, a synchronous network with dynamically changing topology, or an asynchronous network.It works quickly and balances well when the network has an expansion property.In particular, we show that in an n-node network with maximum degree d whose live edges, at every time step, forma p-expander, the algorithm will balance the load to within an additive O(d log n/p) term in O(A log(nA)/p) time, where A is the initial imbalance.The algorithm improves upon previous approaches that yield O(n) time bounds in dynamic and asynchronous networks.

Article Competitive distributed file allocation Share on Authors: Baruch Awerbuch View Profile , Yair Bartal View Profile , Amos Fiat View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 164–173https://doi.org/10.1145/167088.167142Online:01 June 1993Publication History 82citation483DownloadsMetricsTotal Citations82Total Downloads483Last 12 Months10Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In the network synchronization model, each node maintains a local pulse counter bounded-register algorithms.

This paper obtains the first deterministic sublinear-time algorithm ~1992

This paper examines the problem of balancing the job load in a network of processors, and introduces an online algorithm for scheduling a sequence of jobs in a competitive manner. The algorithm is shown to be polylog (n)-competitive according to a strict definition that forces the online algorithm to be competitive even when considering any bounded area of the network and bounded period of time.

The computational power of different communication models is a fundamental question in the theory of distributed computation. For example, in the synchronous model messages are assumed to be delivered within one time unit, whereas in the asynchronous model message delays may be arbitrary. Another important parameter of the model is the assumptions about the topology. In the dynamic topology model, links are assumed to crash and recover dynamically, but their status is known to the incident node processors. A meaningful computation can be carried out if the topology stabilizes for a sufficiently long period.

This paper presents a family of memory-balanced routing schemes that use relatively short paths while storing relatively little routing information. The quality of the routes provided by a scheme is measured in terms of their stretch, namely, the maximum ratio between the length of a route connecting some pair of processors and their distance. The hierarchical schemes$\mathcal{H}_k $ (for every integer $k\geqq 1$) presented in this paper guarantee a stretch factor of $O( k^2 )$ on the length of the routes and require storing at most $O( k \cdot n^{1/k} \cdot \log n\log D )$ bits of routing information per vertex in an n-processor network with diameter D. The schemes are name independent and applicable to general networks with arbitrary edge weights. This improves on previous designs whose stretch bound was exponential in k. The proposed schemes are based on a new efficient solution to a certain graph-theoretic problem concerning sparse graph covers. The new cover technique has already found several other applications in the area of distributed computing.

The first self-stabilizing end-to-end communication protocol and the most efficient known self-stabilizing network reset protocol are introduced. A simple method of local checking and correction, by which distributed protocols can be made self-stabilizing without the use of unbounded counters, is used. The self-stabilization model distinguishes between catastrophic faults that abstract arbitrary corruption of global state, and other restricted kinds of anticipated faults. It is assumed that after the execution starts there are no further catastrophic faults, but the anticipated faults may continue to occur.>

A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. Such a database must be updated in the wake of locally generated changes to its contents. Due to previous disconnections of parts of the network, a maintenance protocol may need to update processors holding widely varying versions of the database. A deterministic protocol, which has only polylogarithmic overhead in its time and communication complexities, is provided for this problem. Previous deterministic solutions required polynomial overhead in at least one of these measures.>

The notion of distributed program checking as a means of making a distributed algorithm self-stabilizing is explored. A compiler that converts a deterministic synchronous protocol pi for static networks into a self-stabilizing version of pi for dynamic networks is described. If T/sub pi / is the time complexity of pi and D is a bound on the diameter of the final network, the compiled version of pi stabilizes in time O(D+T/sub pi /) and has the same space complexity as pi . The general method achieves efficient results for many specific noninteractive tasks. For instance, solutions for the shortest paths and spanning tree problems take O(D) to stabilize, an improvement over the previous best time of O(D/sup 2/).>

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. Two modifications to the algorithm are proposed which result in polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (>

Store-and-forward deadlock prevention in communication networks is addressed. The approach adopted is that of establishing buffer classes in order to prevent cyclic waiting chains. This type of solution usually requires many buffers. The main contribution of the current study is in showing that the number of required buffers can be reduced considerably by using a hierarchical organization of the network. A novel hierarchical scheme for arbitrary networks is proposed, that features a trade-off between the communication overhead and the buffer requirements of the routing. This trade-off can be shown to be close to optimal.>

This work concerns the problem of broadcasting a large message efficiently when each processor has partial prior knowledge tocol to other distributed computing problems are discussed.

This paper deals with store-and-forward deadlocks in communication networks.The goal is to design deadlock-free routing schemes with small overhead in communication and space.Our main contribution is designing efficient protocols that are superior to existing ones in terms of their performance.

This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network in the presence of concurrent requests. The paper uses the graph-theoretic concept of regional matching for implementing efficient tracking mechanisms. The communication overhead of our tracking mechanism is within a polylogarithmic factor of the lower bound. 1 Introduction Since the primary function of a communication network is to provide communication facilities between users and processes in the system, one of the key problems such a network faces is the need to be able to Department of Mathematics and Lab. for Computer Science, M.I.T., Cambridge, MA 02139, USA. E-mail: [email protected]. Supported by Air Force Contract TNDGAFOSR-86-0078, ARO contract DAAL03-86-K0171, NSF contract CCR8611442, DARPA contract N00014-89J -1988, and a special grant from IBM. y Departmentof Applied Mathematicsand Computer Science, The Weizm...

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

A collection of clustering and decomposition techniques that make possible the construction of sparse and locality-preserving representations for arbitrary networks is presented. The representation method considered is based on breaking the network G(V,E) into connected regions, or clusters, thus obtaining a cover for the network, i.e. a collection of clusters that covers the entire set of vertices V. Several other graph-theoretic structures that are strongly related to covers are discussed. These include sparse spanners, tree covers of graphs and the concepts of regional matchings and diameter-based separators. All of these structures can be constructed by means of one of the clustering algorithms given, and each has proved a convenient representation for handling certain network applications.>

The synchronizer is a simulation methodology for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. Previously known synchronizers require each processor in the network to participate in each pulse of the synchronization process. The resulting communication overhead depends linearly on the number n of network nodes. A synchronizer with overhead only polylogarithmically dependent on n is introduced. This synchronizer can also be realized with polylog(n) space. The polylog-overhead synchronizer is based on involving only the relevant portions of the network in the synchronization process.>

Presents an efficient distributed online algorithm for scheduling jobs that are created dynamically, subject to resource constraints that require that certain pairs of jobs not run concurrently. The focus is on the response time of the system to each job, i.e. the length of the time interval that starts when the job is created or assigned to a processor and ends at the instant the execution of the job begins. The goal is to provide guarantees on the response time to each job j in terms of the density of arrivals of jobs that conflict with j. The model is completely asynchronous and includes various resource allocation problems that have been studied extensively, including the dining philosophers problem and its generalizations to arbitrary networks. In these versions of the problem, the resource requirements of each new job j determines an upper bound delta /sub j/ on the number of jobs that can exist concurrently in the system and conflict with j. Given such upper bounds, no scheduling algorithm can guarantee a response time better than delta /sub j/ times the maximum execution or message transmission time. A simple algorithm that guarantees response time that is essentially polynomial in delta /sub j/ is presented. It is based on the notion of a distribution queue and has a compact implementation.>

IntroductionWe describe the control protocols of the PARIS experimental network.This high bandwidth network for integrated communication (data, voice, video) ia 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 of specialized hardware to support faster packet handling and control protocols.A new network control architecture is presented which exploits the specialized hardware in order to support the expected real time needs of future traffic.In particular, since control information can be distributed quickly, 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.

This paper introduces the notion of cost-sensitive communication complexity and exemplifies it on the following basic communication problems: computing a global function, network synchronization, clock synchronization, controlling protocols' worst-case execution, connected components, spanning tree, etc., constructing a minimum spanning tree, constructing a shortest path tree. IntroductionTraEic load is one of the major factors affecting the behavior of a communication network.This fact is well recognized, and is the reason why most

We present a quantitative approach to dynamic networks.Dynamic networks, extensively studied in the last decade, are asynchronous networks with arbitrary topology, in which links and processors repeatedly fail and recover.Loosely speaking, we quantify the reliability of a link at a given moment as the time since the link last recovered.This quantitative definition allows us to iuvestigate protocols that either assume a certain amount of reliability, or provide service only to sufficiently reliable parts of the network.There are several tasks which cannot be solved efficiently when defined in the known (qualitative)approaches, but may be solved efliciently using the new quantitative definitions.We demonstrate this on the broodcast task.Broadcast is basically an order preserving transmission of a sequence of messages from a source processor to all other processors.Every processor which satisfies some fairness condition should accept the messages.This requires unbounded resources, if the fairness is defined using the known (qualitative) approaches.Hence, we give a new

In this paper, we survey the existing methods for designing shortest paths routing algorithms for dynamic networks. We compare them based on worst-case communication and message complexity, and suggest new approach that yields a protocol with linear time and polynomial communication.

This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks.Broadcastis a task initiated by asingleprocessor that wishes to convey a message to all processors in the network. The widely accepted model of communication networks, in which each processor initially knows the identity of its neighbors but does not know the entire network topology, is assumed. Although it seems obvious that the number of messages required for broadcast in this model equals the number of links, no proof of this basic fact has been given before. It is shown that the message complexity of broadcast depends on the exact complexity measure. If messages of unbounded length are counted at unit cost, then broadcast requires Θ(↿V↾) messages, whereVis the set of processors in the network. It is proved that, if one counts messages ofbounded length, then broadcast requires Θ(↿E↾) messages, whereEis the set of edges in the network. Assuming an intermediate model in which each vertex knows the topology of the network in radiusρ≥ 1 from itself, matching upper and lower bounds of Θ(min{↿E↾, ↿V↾1+Θ(l)/ρ}) is proved on the number of messages of bounded length required for broadcast. Both the upper and lower bounds hold for both synchronous and asynchronous network models. The same results hold for the construction of spanning trees, and various other global tasks.

The authors introduce a concept of network decomposition, a partitioning of an arbitrary graph into small-diameter connected components, such that the graph created by contracting each component into a single node has low chromatic number. They present an efficient distributed algorithm for constructing such a decomposition and demonstrate its use for design of efficient distributed algorithms. The method yields new deterministic distributed algorithms for finding a maximal independent set in an arbitrary graph and for ( Delta +1)-coloring of graphs with maximum degree Delta . These algorithms run in O(n/sup epsilon /) time for epsilon =O((log log n/log n)/sup 1/2/), whereas the best previously known deterministic algorithms required Omega (n) time. The techniques can also be used to remove randomness from the previously known most distributed breadth-first search algorithm.>

A dynamic communication network is one in which links may repeatedly fail and recover. In such a network, although it is impossible to establish a path of unfailed links, reliable communication is possible if there is no cut of permanently failed links between a sender and receiver. The authors consider for such a network the basic task of end-to-end communication, that is, delivery in finite time of data items generated online at the sender, to the receiver, in order and without duplication or omission. The best known previous solutions to this problem had exponential complexity. Moreover, it has been conjectured that a polynomial solution is impossible. The authors disprove this conjecture, presenting the first polynomial end-to-end protocol. The protocol uses methods adopted from shared-memory algorithms and introduces novel techniques for fast load balancing in communication networks.>

This paper is concerned with distributed algorithm for finding shortest paths in an asynchronous communication network. For the problem of Breadth First Search, the best previously known algorithms required either Θ(V) time, or Θ (E + V · D) communication. We present new algorithm, which requires O(D1+ε) time, and O(E1+ε) messages, for any ε > 0. (Here, V is number of nodes, E is number of edges and D is the diameter.) This constitutes a major step towards achieving the lower bounds, which are Ω(E) communication and Ω(D) time.

In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor - the maximum ratio between the cost of a route computed by the scheme and that of a cheapest path connecting the same pair of vertices.

A framework is introduced that provides a unified way for proving correctness as well as analyzing performance of a class of communication protocols called (asynchronous) reset protocols. They are logarithmic transformers, converting protocols working in a static asynchronous network into protocols working in a dynamic asynchronous network. The design of reset protocols is a classical problem in communication networking, renowned for its complexity. A paradigm is developed that gives fresh insight into this complicated problem. This additional insight leads to the development of reset protocols with complexities bounded by the communication complexity of the original protocol.>

An efficient simulation is given to show that dynamic networks are as fast as static ones up to a constant multiplicative factor. That is, any task can be performed in a dynamic asynchronous network essentially as fast as in a static synchronous network. The simulation protocol is based on an approach in which locality is perceived as the key to fast adaptation to changes in network topology. The heart of the simulation is a technique called a dynamic synchronizer, which achieves 'local' simulation of a global 'clock' in a dynamic asynchronous network. Using this result, improved solutions to a number of well-known problems on dynamic networks are obtained. It can also be used to improve the solution to certain static network problems.>

This paper addresses the problem of how to adapt an algorithm designed for fixed topology networks to produce the intended results, when run in a network whose topology changes dynamically, in spite of encountering topological changes during its execution. We present a simple and unified procedure, called a reset procedure, which, when combined with the static algorithm, achieves this adaptation. The communication and time complexities of the reset procedure, per topological change, are independent of the number of topological changes and are linearly bounded by the size of the subset of the network which participates in the algorithm.

We introduce a new primitive, the Resource Controller, which abstracts the problem of controlling the total amount of resources consumed by a distributed algorithm. We present an efficient distributed algorithm to implement this abstraction. The message complexity of our algorithm per participating node is polylogarithmic in the size of the network, compared to the linear cost per node of the naive algorithm. The implementation of our algorithm is simple and practical and the techniques used are interesting because a global quantity is managed in a distributed way. The Resource Controller can be used to construct efficient algorithms for a number of important problems, such as the problem of bounding the worst-case message complexity of a protocol and the problem of dynamically assigning unique names to nodes participating in a protocol.

The authors report that the paper by P.M.B. Vitanyi and B. Awerbuch, "Atomic shared register access by asynchronous hardware," Proc. 27th IEEE Symp. on Foundations of Computer Science (1986), 233-243, has an error in the 'Struldbrugg' algorithm (the main bounded tag algorithm) and a counterexample is presented. The "selection rule" of the reader is not sufficient to guarantee atomicity, but only the weaker regularity condition. Informally, regularity for multiwriter registers means that a reader does return a value written by a write, such that there is no complete other write strictly in between the durations of the read and the write it returns.

This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. Those problems include Minimum-Weight Spanning Tree (MST), Leader Election, counting the number of network nodes, and computing a sensitive decomposable function (e.g. majority, parity, maximum, OR, AND).

Parallel algorithms for finding the connected components (CC) and a minimum spanning FOREST (MSF) of an undirected graph are presented. The primary model of computation considered is that called "shuffle-exchange network" in which each processor has its own local memory, no memory is shared, and communication among processors is done via a fixed degree network. This model is very convenient for actual realization. Both algorithms have depth of O(log2 n) while using n2 processors. Here n is the number of vertices in the graph. The algorithms are first presented for the PRAM (parallel RAM) model, which is not realizable, but much more convenient for the design and presentation of algorithms. The CC and MSF algorithms are no exceptions. The CC PRAM algorithm is a simplification of the one appearing in [17]. A modification of this algorithm yields a simple and efficient MSF algorithm. Both have depth of O(log m) and they use m processors, where m is the number of edges in the graph.

A new distributed algorithm is presented for constructing breadth first search (BFS) trees. A BFS tree is a tree of shortest paths from a given root node to all other nodes of a network under the assumption of unit edge weights; such trees provide useful building blocks for a number of routing and control functions in communication networks. The order of communication complexity for the new algorithm isO(V^{1.6} + E)whereVis the number of nodes and E the number of edges. For dense networks withE \geq V^{1.6}this order of complexity is optimum.

The deadlock resolution problem can be informally stated as follows. There exists a set of actions, generated at different times, with some complex and contradictory precedence constraints between their executions. To resolve a deadlock, some of the actions need to be aborted; this enables to execute the remaining ones. This problem naturally arises in the context of distributed systems, e.g. communication networks, distributed operating systems and distributed databases, where actions are generated by many processors, and are not coordinated by a central controller. In this paper, we are concerned with efficient distributed algorithms (protocols) for resolution of dynamic deadlocks. Such resolution protocols must operate on-line without any knowledge of the future and using only local information. The main contribution of the paper is a reduction of the most general dynamic deadlock resolution problem to a conceptually simpler static problem, in which all actions are known a priori. The complexity of our reduction is O (m + n logn) in communication and O (n) in time, where n is the number of actions and m is total number of constraints. Since the static deadlock resolution requires at least Ω(m + n logn) in communication and Ω(n) in time, our reduction essentially shows that the resolution of dynamic deadlocks is not any harder than resolution of the static ones. We also show here a simple and optimal algorithm for the static problem, which, together with the above reduction, yields an optimal dynamic deadlock resolution protocol.

The contribution of this paper is two-fold. First, we describe two ways to construct multivalued atomic n-writer n-reader registers. The first solution uses atomic 1-writer 1-reader registers and unbounded tags. the other solution uses atomic 1-writer n-reader registers and bounded tags. The second part of the paper develops a general methodology to prove atomicity, by identifying a set of criteria which guaranty an effective construction for the required atomic mapping. We apply the method to prove atomicity of the two implementations for atomic multiwriter multireader registers.

Abstract Broadcast is the task of delivering copies of a packet to all nodes in a communication network. A broadcast is called reliable if all the packets are accepted by all the nodes in finite time and in the correct order. This paper presents a class of reliable broadcast protocols for unreliable networks. One of these protocols achieves reliable broadcast with minimum broadcast cost, assuming that the network allows reliable broadcast at all. In case that the network's topology is stable, the minimum broadcast delay is achieved. No existing broadcast protocol achieves this goal. As a by‐product, we achieve a new reliable routing protocol.

This paper develops a new distributed BFS algorithm for an asynchronous communication network. This paper presents two new BFS algorithms with improved communication complexity. The first algorithm has complexity O((E+V1.5)·logV) in communication and O(V1.5·logV) in time. The second algorithm uses the technique of the first recursively and achieves O(E·2 √logVloglogV) in communication and O(V·2√logVloglogV) in time.

Article Free Access Share on Communication-time trade-offs in network synchronization Author: Baruch Awerbuch M.I.T. M.I.T.View Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 272–276https://doi.org/10.1145/323596.323621Published:01 August 1985Publication History 19citation171DownloadsMetricsTotal Citations19Total Downloads171Last 12 Months15Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of simulating a synchronous network by an asynchronous network is investigated. A new simulation technique, referred to as a synchronizer, which is a new, simple methodology for designing efficient distributed algorithms in asynchronous networks, is proposed. The synchronizer exhibits a trade-off between its communication and time complexities, which is proved to be within a constant factor of the lower bound.

Abstract This article presents new simple distributed Maximum Flow and Breadth‐First Search algorithms for an asynchronous communication network. Our algorithms improve the best known algorithms both in the communication and time complexities. The basic idea is first to “synchronize” the network and then to apply synchronous algorithms which use efficiently the parallelism of the model.

We deal with communication networks whose topology changes arbitrarily subject to the restriction that no edge-cut in the network persists forever. Up to now, no formal-ground rules have been proposed for such networks, and no protocol has been proved to possess any desirable property. We introduce a new proof methodology, in the sense that link-behavior in such networks is axiomatized.

A parallel algorithm for finding Euler circuits in graphs is presented. Its depth is log |E| and it employs |E| processors. The computational model considered is the PRAM (the shared memory model).

Broadcast in a communication network is the delivery of copies of messages to all nodes. A broadcast protocol is reliable if all messages reach all nodes in finite time, in the correct order and with no duplicates. The present paper presents an efficient reliable broadcast protocol.