In vertex recoloring, we are given $n$ vertices with their initial coloring, and edges arrive in an online fashion. The algorithm must maintain a valid coloring by recoloring vertices, at a cost. The problem abstracts a scenario of job placement in machines (possibly in the cloud), where vertices represent jobs, colors represent machines, and edges represent ``anti affinity'' (disengagement) constraints. Online recoloring is a hard problem. One family of instances which is fairly well-understood is bipartite graphs, in which two colors are sufficient to satisfy all constraints. In this case it is known that the competitive ratio of vertex recoloring is $Θ(\log n)$. We propose a generalization of the problem, which allows using additional colors (possibly at a higher cost), to improve overall performance. We analyze the simple case of bipartite graphs of bounded largest \emph{bond} (a bond of a connected graph is an edge-cut that partitions the graph into two connected components). First, we propose two algorithms. One exhibits a trade-off for the uniform-cost case: given $Ω(\logβ)\le c\le O(\log n)$ colors, the algorithm guarantees that its cost is at most $O(\frac{\log n}{c})$ times the optimal offline cost for two colors, where $n$ is the number of vertices and $β$ is the size of the largest bond. The other algorithm is for the case where the additional colors come at a higher cost, $D>1$: given $Δ$ additional colors, where $Δ$ is the maximum degree in the graph, the algorithm guarantees $O(\log D)$ competitiveness. As to lower bounds, we show that if the cost of the extra colors is $D>1$, no (randomized) algorithm can achieve a competitive ratio of $o(\log D)$. We also show that for bipartite graphs of unbounded bond size, any deterministic online algorithm has competitive ratio $Ω(\min(D,\log n))$.

We consider a stochastic network model consisting of a set of n synchronous processes communicating by message passing. In each round, processes send messages directly to each other over a complete communication graph. The processes do not fail, but messages can be lost. Each message is delivered with probability p, for a given parameter p ∈ [0,1]. We study the following optimization version of approximate agreement in this model. We assume that processes start with binary input values, execute an algorithm for a fixed number of rounds, and decide values in [0,1] satisfying the usual validity requirement stating that if all processes start with the same input value, then they should all decide that value. We propose deterministic algorithms that minimize the expected discrepancy, namely, the expected maximum distance between the decided values. We also present lower bounds on the expected discrepancy, which demonstrate the optimality of our algorithms for two processes. Finally, we present applications of our algorithms to solve randomized consensus and randomized approximate agreement.

Abstract We investigate the effect of omnipresent cloud storage on distributed computing. To this end, we specify a network model with links of prescribed bandwidth that connect standard processing nodes, and, in addition, passive storage nodes. Each passive node represents a cloud storage system, such as Dropbox, Google Drive etc. We study a few tasks in this model, assuming a single cloud node connected to all other nodes, which are connected to each other arbitrarily. We give implementations for basic tasks of collaboratively writing to and reading from the cloud, and for more advanced applications such as matrix multiplication and federated learning. Our results show that utilizing node-cloud links as well as node-node links can considerably speed up computations, compared to the case where processors communicate either only through the cloud or only through the network links. We first show how to optimally read and write large files to and from the cloud in general graphs using flow techniques. We use these primitives to derive algorithms for combining , where every processor node has an input value and the task is to compute a combined value under some given associative operator. In the special but common case of “fat links,” where we assume that links between processors are bidirectional and have high bandwidth, we provide near-optimal algorithms for any commutative combining operator (such as vector addition). For the task of matrix multiplication (or other non-commutative combining operators), where the inputs are ordered, we present tight results in the simple “wheel” network, where procesing nodes are arranged in a ring, and are all connected to a single cloud node.

Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of a recoloring is the sum of weights of vertices whose color changed. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O(log n)-competitive deterministic algorithm and an Ω(log n) lower bound on the competitive ratio of randomized algorithms. For (Δ+1)-coloring, we present tight bounds of Θ(Δ) and Θ(logΔ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider a dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are weighted and the cost of recoloring a vertex is its weight. All our lower bounds hold even in the unweighted case.

We consider the following generalization of the classic ski rental problem. A task of unknown duration must be carried out using one of two alternatives called "buy" and "rent", each with a one-time startup cost and an ongoing cost which is a function of the duration. Switching from rent to buy also incurs a one-time cost. The goal is to minimize the competitive ratio, i.e., the worst-case ratio between the cost paid and the optimal cost, over all possible durations. For linear or exponential cost functions, the best deterministic and randomized on-line strategies are well known. In this work we analyze a much more general case, assuming only that the cost functions are continuous and satisfy certain mild monotonicity conditions. For this general case we provide (1) an algorithm that computes the deterministic strategy with the best competitive ratio, and (2) an approximation algorithm that, given ε>0$, computes a randomized strategy whose competitive ratio is within (1+ε) from the best possible, in time polynomial in ε-1. Our algorithm assumes access to a black box that can compute the functions and their inverses, as well as find their extreme points.

We consider packet forwarding on a tree with all packets destined for the root, assuming each link may forward at most c ≥ 1 packets each time step. We use the Adversarial Queuing Theory injection model, where a (ρ, σ)-adversary may inject at most σ + ρ · t packets into the network at arbitrary locations during any time interval of length t. The goal is to find a forwarding protocol that minimizes the maximal buffer space required to avoid overflows against a (ρ, σ)-adversary with ρ ≤ c. We consider protocols from the locality viewpoint. A protocol is called d-local if the actions of a node depend only on the current state of nodes at distance at most d. A D-local protocol, where D is the network diameter, is called centralized. It is known that buffers of size Θ(σ + ρ) are necessary and sufficient for centralized protocols. The buffer requirement of O(1)-local protocols was recently proved to be Θ(ρ log D+σ). In this paper, for any d ≥ 2, we describe a d-local algorithm whose buffer space requirement is O (⌈log D/d⌉ ρ + σ). This result is tight, up d to constant factors. In particular, it implies that O(log D) locality is sufficient to achieve the best worst-case performance possible even for centralized algorithms. We also give evidence suggesting that the buffer requirement of a local algorithm designed for trees is good also when the routes do not constitute a single-destination tree.

The winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Sepehr Assadi for his dissertation Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation, written under the supervision of Prof. Sanjeev Khanna at the University of Pennsylvania.

We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 ≤ ρ ≤ 1 and burstiness σ ≤ 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(ℓ d1/ℓ + σ) space suffice, where d is the number of distinct destinations and ℓ=⌋1/ρ⌊ and we show that Ω(1 over ℓ d1/ℓ + σ) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1 + d' + σ where d' is the maximum number of destinations on any root-leaf path.

We consider shortest paths computation and related tasks from the viewpoint of network algorithms, where the n-node input graph is also the computational system: nodes represent processors and edges represent communication links, which can in each time step carry an $$\mathcal {O}(\log n)$$ -bit message. We identify several basic distributed distance computation tasks that are highly useful in the design of more sophisticated algorithms and provide efficient solutions. We showcase the utility of these tools by means of several applications.

In the Local Computation Algorithms (LCA) model, the algorithm is asked to compute a part of the output by reading as little as possible from the input. For example, an LCA for coloring a graph is given a vertex name (as a "query"), and it should output the color assigned to that vertex after inquiring about some part of the graph topology using "probes"; all outputs must be consistent with the same coloring. LCAs are useful when the input is huge, and the output as a whole is not needed simultaneously. Most previous work on LCAs was limited to bounded-degree graphs, which seems inevitable because probes are of the form "what vertex is at the other end of edge i of vertex v?". In this work we study LCAs for unbounded-degree graphs. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. We show that there are problems that have very efficient LCAs on any graph - specifically, we show that there is an LCA for the weak coloring problem (where a coloring is legal if every vertex has a neighbor with a different color) that uses log^* n+O(1) probes to reply to any query. As another way of dealing with large degrees, we propose a more powerful type of probe which we call a strong probe: given a vertex name, it returns a list of its neighbors. Lower bounds for strong probes are stronger than ones in the edge probe model (which we call weak probes). Our main result in this model is that roughly Omega(sqrt{n}) strong probes are required to compute a maximal matching. Our findings include interesting separations between closely related problems. For weak probes, we show that while weak 3-coloring can be done with probe complexity log^* n+O(1), weak 2-coloring has probe complexity Omega(log n/log log n). For strong probes, our negative result for maximal matching is complemented by an LCA for (1-epsilon)-approximate maximum matching on regular graphs that uses O(1) strong probes, for any constant epsilon>0.

The Dijkstra Prize Committee has decided to grant the 2018 Edsger W. Dijkstra Prize in Distributed Computing to Bowen Alpern and Fred B. Schneider for their paper:

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+\sqrt{n})\cdot n^{o(1)}$ communication rounds in the CONGEST model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tilde{\Omega}(D+\sqrt{n})$-round complexity lower bound. The development of the algorithm entails two subresults of independent interest: (i) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of a spanning tree of average stretch $n^{o(1)}$. (ii) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of an $n^{o(1)}$-congestion approximator consisting of the cuts induced by $O(\log n)$ virtual trees. The distributed representation of the cut approximator allows for evaluation in $(D+\sqrt{n})\cdot n^{o(1)}$ rounds. All our algorithms make use of randomization and succeed with high probability.

We consider packet forwarding in acyclic networks with bounded adversarial packet injections. We focus on the model of adversarial queuing theory, where each packet is injected into the network with a prescribed path to its destination, and both the long-range average rate and the short-range burst size are bounded. Each edge has an associated buffer that stores packets while they wait to cross the edge. Our goal is to minimize the buffer space required to avoid overflows.

We define and study a new variant of the secretary problem. Whereas in the classic setting multiple secretaries compete for a single position, we study the case where the secretaries arrive one at a time and are assigned, in an on-line fashion, to one of multiple positions. Secretaries are ranked according to talent, as in the original formulation, and in addition positions are ranked according to attractiveness. To evaluate an online matching mechanism, we use the notion of blocking pairs from stable matching theory: our goal is to maximize the number of positions (or secretaries) that do not take part in a blocking pair. This is compared with a stable matching in which no blocking pair exists. We consider the case where secretaries arrive randomly, as well as that of an adversarial arrival order, and provide corresponding upper and lower bounds.

We present a near-optimal distributed algorithm for (1+o(1))-approximation of single-commodity maximum flow in undirected weighted networks that runs in (D+ √n)⋅ no(1) communication rounds in the Congest model. Here, n and D denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial O(m) time bound, and it nearly matches the Ω(D+√n) round complexity lower bound.

We study approximate distributed solutions to the weighted all-pairs shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. A deterministic (1+epsilon)-approximation to APSP with running time O(ε-2n log n) rounds. The best previously known algorithm was randomized and slower by a Theta(log n) factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and that are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of o(n log n). In the relabeling model, we obtain the following results. A randomized O(k)-approximation to APSP, for any integer k>1, running in ~O(n1/2+1/k+D) rounds, where D is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from O(k log k) to O(k). Also, the new algorithm uses O(log n)-bit labels, which is asymptotically optimal. A randomized O(k)-approximation to APSP, for any integer k>1, running in time ~O((nD)1/2 n1/k+D) and producing compact routing tables of size ~O(n1/k). The node labels consist of O(k log n) bits. This improves on the approximation ratio of Theta(k2) for tables of that size achieved by the best previously known algorithm, which terminates faster, in ~O(n1/2+1/k+D) rounds. In addition, we improve on the time complexity of the best known deterministic algorithm for distributed approximate Steiner forest.

Proof-labeling schemes, introduced by Korman, Kutten and Peleg [PODC 2005], are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of randomized proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces label size exponentially while guaranteeing probability of correctness arbitrarily close to one. In addition, we present a novel label-size lower bound technique that applies to both deterministic and randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.

We consider the following fundamental routing problem. An adversary inputs packets arbitrarily at sources, each packet with an arbitrary destination. Traffic is constrained by link capacities and buffer sizes, and packets may be dropped at any time. The goal of the routing algorithm is to maximize throughput, i.e., route as many packets as possible to their destination. Our main result is an O(log n)-competitive deterministic algorithm for an n-node uni-directional line network (i.e., 1-dimensional grid), requiring only that buffers can store at least 5 packets, and that links can deliver at least 5 packets per step. We note that O(log n) is the best ratio known, even for randomized algorithms, even when allowed large buffers and wide links. The best previous deterministic algorithm for this problem with constant-size buffers and constant-capacity links was O(log5 n)-competitive. Our algorithm works like admission-control algorithms in the sense that if a packet is not dropped immediately upon arrival, then it is "accepted" and guaranteed to be delivered. We also show how to extend our algorithm to a polylog-competitive algorithm for any constant-dimension uni-directional grid.

We consider the backup placement problem, defined as follows. Some nodes (processors) in a given network have objects (e.g., files, tasks) whose backups should be stored in additional nodes for increased fault resilience. To minimize the disturbance in case of a failure, it is required that a backup copy should be located at a neighbor of the primary node. The goal is to find an assignment of backup copies to nodes which minimizes the maximum load (number or total size of copies) over all nodes in the network. It is known that a natural selfish local improvement policy has approximation ratio Ω(log n / log log n); we show that it may take this policy Ω(√n) time to reach equilibrium in the distributed setting. Our main result in this paper is a distributed algorithm which finds a placement in polylogarithmic time and achieves approximation ratio O(log n/log log n). We obtain this result using a distributed approximation algorithm for f-matching in bipartite graphs that may be of independent interest.

We present distributed network algorithms to compute weighted and unweighted matchings with improved approximation ratios and running times. The computational model is a network of processors exchanging O (log n )-bit messages (the CONGEST model). For unweighted graphs, we give an algorithm providing (1-ϵ)-approximation in O (log n ) time for any constant ϵ>0, improving on the classical ½-approximation in O log n ) time of Israeli and Itai [1986]. The time complexity of the algorithm depends on 1⁃ϵ exponentially in the general case, and polynomially in bipartite graphs. For weighted graphs, we present another algorithm which provides (½-ϵ) approximation in general graphs in O (logϵ -1 log n ) time, improving on the previously known algorithms which attain (¼-ϵ)-approximation in O (log n ) time or ½-approximation in O ( n ) time. All our algorithms are randomized: the complexity bounds hold both with high probability and for the expected running time.

We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant ε>0, a (2+ε)-approximation in ~O(sk+√{min(st,n)}) rounds, where s is the shortest path diameter, t is the number of terminals, k is the number of terminal components in the input, and n is the number of nodes. Our randomized algorithm finds, with high probability, an O(log n)-approximation in time ~O(k+min(s,√ n)+D), where D is the unweighted diameter of the network. We also prove a matching lower bound of ~Ω(k+min(s,√n)+D) on the running time of any distributed approximation algorithm for the Steiner Forest problem. Previous algorithms were randomized, and obtained either an O(log n)-approximation in ~O(sk) time, or an O(1/ε)-approximation in O((√n+t)1+ε+D) time.

We describe a distributed randomized algorithm to construct routing tables. Given 0< ε <= 1/2, the algorithm runs in time ~O(n1/2+ε + HD), where n is the number of nodes and HD denotes the diameter of the network in hops (i.e., as if the network is unweighted). The weighted length of the produced routes is at most O(ε-1log ε-1) times the optimal weighted length. This is the first algorithm to break the Omega(n) complexity barrier for computing weighted shortest paths even for a single source. Moreover, the algorithm nearly meets the ~Omega(n1/2 + HD) lower bound for distributed computation of routing tables and approximate distances (with optimality, up to polylog factors, for ε=1/log n). The presented techniques have many applications, including improved distributed approximation algorithms for Generalized Steiner Forest, all-pairs distance estimation, and estimation of the weighted diameter.

In online set packing (OSP), elements arrive online, announcing which sets they belong to, and the algorithm needs to assign each element, upon arrival, to one of its sets. The goal is to maximize the number of sets that are assigned all their elements: a set that misses even a single element is deemed worthless. This is a natural online optimization problem that abstracts allocation of scarce compound resources, e.g., multipacket data frames in communication networks. We present a randomized competitive online algorithm for the weighted case with general capacity (namely, where sets may have different values, and elements arrive with different multiplicities). We prove a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximum set size and the maximum number of sets an element belongs to. We also present refined bounds that depend on the uniformity of these parameters.

In the multislope ski rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (“buying price”) and cost proportional to the duration of the usage (“rental rate”). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best alternative at any point in time. Multislope ski rental is a natural generalization of the classical ski rental problem (where there are only two available alternatives, namely pure rent and pure buy), which is one of the fundamental problems of online computation. The multislope ski rental problem is an abstraction of many problems, where online choices cannot be modeled by just two alternatives, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for multislope ski rental. Our results include an algorithm that produces the best possible online randomized strategy for any additive instance, where the cost of switching from one alternative to another is the difference in their buying prices, and an e-competitive randomized strategy for any (not necessarily additive) instance.

We study an abstract setting, where the basic information units (called “superpackets”) do not fit into a single packet, and are therefore spread over multiple packets. We assume that a superpacket is useful only if the number of its delivered packets is above a certain threshold. Our focus of attention is communication link ingresses, where large arrival bursts result in dropped packets. The algorithmic question we address is which packets to drop so as to maximize goodput. Specifically, suppose that each superpacket consists of k packets, and that a superpacket can be reconstructed if at most β · k of its packets are lost, for some given parameter 0 ≤ β; 0. Finally, we present some simulation results that demonstrate that the behavior of our algorithm in practice is far better than our worst-case analytical bounds.

We consider the model of fully connected networks, where in each round each node can send an O(log n)-bit message to each other node (this is the CONGEST model with diameter 1). It is known that in this model, min-weight spanning trees can be found in O(log log n) rounds. In this paper we show that distributed sorting, where each node has at most n items, can be done in time O(log log n) as well. It is also shown that selection can be done in O(1) time. (Using a concurrent result by Lenzen and Wattenhofer, the complexity of sorting is further reduced to constant.) Our algorithms are randomized, and the stated complexity bounds hold with high probability.

We consider the interactive model of recommender systems, in which users are asked about just a few of their preferences, and in return the system outputs an approximation of all their preferences. The measure of performance is the probe complexity of the algorithm, defined to be the maximal number of answers any user should provide (probe complexity typically depends inversely on the number of users with similar preferences and on the quality of the desired approximation). Previous interactive recommendation algorithms assume that user preferences are binary, meaning that each object is either "liked" or "disliked" by each user. In this paper we consider the general case in which users may have a more refined scale of preference, namely more than two possible grades. We show how to reduce the non-binary case to the binary one, proving the following results. For discrete grades with s possible values, we give a simple deterministic reduction that preserves the approximation properties of the binary algorithm at the cost of increasing probe complexity by factor s. Our main result is for the general case, where we assume that user grades are arbitrary real numbers. For this case we present an algorithm that preserves the approximation properties of the binary algorithm while incurring only polylogarithmic overhead.

In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.

We consider a scenario where large data frames are broken into a few packets and transmitted over the network. Our focus is on a bottleneck router: the model assumes that in each time step, a set of packets (a burst) arrives, from which only one packet can be served, and all other packets are lost. A data frame is considered useful only if none of its constituent packets is lost, and otherwise it is worthless. We abstract the problem as a new type of online set packing, present a randomized distributed algorithm and a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximal burst size and the maximal number of packets per frame. We also present refined bounds that depend on the uniformity of these parameters.

We study error confinement in distributed applications, which can be viewed as an extreme case of various fault locality notions studied in the past. Error confinement means that to the external observer, only nodes that were directly hit by a fault may deviate from their specified correct behavior, and only temporarily. The externally observable behavior of all other nodes must remain impeccable, even though their internal state may be affected. Error confinement is impossible if an adversary is allowed to inflict arbitrary transient faults on the system, since the faults might completely wipe out input values. We introduce a new fault-tolerance measure we call agility , which quantifies the fault tolerance of an algorithm that disseminates information against state corrupting faults. We then propose broadcast algorithms that guarantee error confinement with optimal agility to within a constant factor in synchronous networks. These algorithms can serve as building blocks in more general reactive systems. Previous results in exploring locality in reactive systems were not error confined, or allowed a wide range of behaviors to be considered correct. Our results also include a new technique that can be used to analyze the “cow path” problem.

We consider the distributed complexity of the stable marriage problem. In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable marriage problem requires Omega(sqrt(n/(B log n))) communication rounds in the worst case, even for graphs of diameter Theta (log n), where n is the number of nodes in the graph. Furthermore, the lower bound holds even if we allow the output to contain O(sqrt(n)) blocking pairs. We also consider epsilon-stability, where a pair is called epsilon-blocking if they can improve the quality of their match by more than an epsilon fraction, for some 0

We introduce the problem of managing a FIFO buffer of bounded space, where arriving packets have dependencies among them. Our model is motivated by the scenario where large data frames must be split into multiple packets, because maximum packet size is limited by data-link restrictions. A frame is considered useful only if sufficiently many of its constituent packets are delivered. The buffer management algorithm decides, in case of overflow, which packets to discard and which to keep in the buffer. The goal of the buffer management algorithm is to maximize throughput of useful frames. This problem has a variety of applications, e.g., Internet video streaming, where video frames are segmented and encapsulated in IP packets sent over the Internet. We study the complexity of the above problem in both the offline and online settings. We give upper and lower bounds on the performance of algorithms using competitive analysis.

Given an undirected graph and 0 ≤ ε ≤ 1, a set of nodes is called ε-near clique if all but an ε fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size ε-near clique if there exists an ε3-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n−Ω(1) in O(log n) time, and the algorithm also works if the graph contains a clique of size Ω(n/logα log n) for some α ∈ (0,1). Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.

In the stable marriage problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable marriage problem requires Ω(√n/Blog n) communication rounds in the worst case, even for graphs of diameter Θ(log n), where n is the number of nodes in the graph. The lower bound holds even if the output may contain O(√n) blocking pairs. We also consider ε-stability, where a pair is called ε-blocking if they can improve the quality of their match by more than an ε fraction, for some 0 ≤ ε ≤ 1. Our lower bound extends to ε-stability where ε is arbitrarily close to 1/2. We also present a simple distributed algorithm for ε-stability whose time complexity is O(n/ε).

We consider a system where users wish to find similar users. To model similarity, we assume the existence of a set of queries, and two users are deemed similar if their answers to these queries are (mostly) identical: each user has a vector of preferences, and two users are similar if their preference vectors differ in only a few coordinates. The preferences are unknown to the system initially, and the goal of the algorithm is to classify the users into classes of roughly the same preferences with the least possible number of queries presented to any user. We prove nearly matching lower and upper bounds on that problem. ecifically, we present an "anytime" algorithm that maintains a partition of the users, and the quality of the partition improves over time: let n be the number of users. At time T, groups of Õ(n/T) users with the same preferences will be separated (with high probability) if they differ in sufficiently many queries. We present a lower bound that matches the upper bound, up to a constant factor, for nearly all possible distances between user groups.

We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized $(4+\epsilon)$-approximation distributed algorithm for maximum weighted matching, whose running time is $O(\log n)$ for any constant $\epsilon>0$, where n is the number of nodes in the graph. This is, to the best of our knowledge, the first log-time distributed algorithm that achieves constant approximation for maximum weighted matching on general graphs. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give a distributed algorithm that maintains a $(1+\epsilon)$-approximation in $O(1/\epsilon)$ time for each node insertion or deletion for any constant $\epsilon>0$. For weighted dynamic graphs we give a constant-factor approximation distributed algorithm that runs in constant time for each insertion or deletion.

We consider the optimization problem of providing a set of video streams to a set of clients, where each stream has costs in m possible measures (such as communication bandwidth, processing bandwidth etc.), and each client has its own utility function for each stream. We assume that the server has a budget cap on each of the m cost measures; each client has an upper bound on the utility that can be derived from it, and potentially also upper bounds in each of the m cost measures. The task is to choose which streams the server will provide, and out of this set, which streams each client will receive. The goal is to maximize the overall utility subject to the budget constraints. We give an efficient approximation algorithm with approximation factor of O(m) with respect to the optimal possible utility for any input, assuming that clients have only a bound on their maximal utility. If, in addition, each client has at most mc capacity constraints, then the approximation factor increases by another factor of O(mclog n), where n is the input length. We also consider the special case of "small" streams, namely where each stream has cost of at most O(1/ log n) fraction of the budget cap, in each measure. For this case we present an algorithm whose approximation ratio is O(log n).

We consider an abstraction of the problem of managing buffers where traffic is subject to service level agreements (SLA). In our abstraction of SLAs, some packets are marked as ldquocommittedrdquo and the others are marked as ldquoexcess.rdquo The service provider must on one hand deliver all committed packets, and on the other hand can get extra revenue for any excess packet delivered. We study online algorithms managing a buffer with limited space, whose task is to decide which packets should be delivered and which should be dropped. Using competitive analysis, we show how to utilize additional buffer space and link bandwidth so that the number of excess packets delivered is comparable to the best possible by any off-line algorithm, while guaranteeing that no arriving committed packet is ever dropped. Simulations of such traffic (alone and combined with additional best-effort traffic) show that the performance of our algorithm is in fact much better than our analytical guarantees.

We present improved algorithms for finding approximately optimal matchings in both weighted and unweighted graphs. For unweighted graphs, we give an algorithm providing >(1-ε-approximation in O(log n) time for any constant ε > 0. This result improves on the classical 1 over 2-approximation due to Israeli and Itai. As a by-product, we also provide an improved algorithm for unweighted matchings in bipartite graphs. In the context of weighted graphs, we give another algorithm which provides (1 over 2-ε) approximation in general graphs in O(log n)time. The latter result improves on the known (1 over 4-ε-approximation in O(log n)time.

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an $e$-competitive randomized strategy for any (non-additive) instance.

No abstract available.

We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + ε)-approximation distributed algorithm for weighted maximum matching, whose running time is O(log n) for any constant ε > 0, where n is the number of nodes in the graph. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give an algorithm that maintains a (1 + ε)-approximation in O(1/ε) time for each node insertion or deletion. For weighted dynamic graphs we give a constant-factor approximation algorithm that runs in constant time for each insertion or deletion.

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.

We consider the following abstraction of competing publications. There are n players vying for the attention of the audience. The attention of the audience is abstracted by a single slot which holds, at any given time, the name of the latest release. Each player needs to choose, ahead of time, when to release its product, and the goal is to maximize the amount of time its product is the latest release. Formally, each player i chooses a point xi ∈ [0,1], and its payoff is the distance from its point xi to the next larger point, or to 1 if xi is the largest. For this game, we give a complete characterization of the Nash equilibrium for the two-player, continuous-action game, and, more important, we give an efficient approximation algorithm to compute numerically the symmetric Nash equilibrium for the n-player game. The approximation is computed via a discrete-action version of the game. In both cases, we show that the (symmetric) equilibrium is unique. Our algorithmic approach to the n-player game is non-standard in that it does not involve solving a system of differential equations. We believe that our techniques can be useful in the analysis of other timing games.

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

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.

We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm which constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to every other process. If message size is $\Theta(n^\epsilon)$ for some $\epsilon>0$, then the number of communication rounds is $O(\log{1\over\epsilon})$.

Summary form only given. We consider an asymmetric wireless communication setting, where a server periodically broadcasts data items to different mobile clients. The goal is to serve items in a prescribed rate, while minimizing the energy consumption of the mobile users. Abstractly, we are presented with a set of jobs, each with a known execution time and a requested period, and the task is to design a schedule for these jobs over a single shared resource without preemption. Given any solution schedule, its period approximation is the maximal factor by which the average period of a job in the schedule is blown up w.r.t. its requested period, and the jitter ratio is roughly the maximal variability of times between two consecutive occurrences of the same job. Schedules with low jitter ratio allow the mobile devices to save power by having their receivers switched off longer. We consider a scenario where clients may be willing to settle for nonoptimal period approximation so that the jitter ratio is improved. We present a parametric jitter-approximation tradeoff algorithm that allows us to choose various combinations between jitter optimality and period optimality for any given set of jobs.

We consider a scenario where nodes in a sensor network hold numeric items, and the task is to evaluate simple functions of the distributed data. In this note we present distributed protocols for computing the median with sublinear space and communication complexity per node. Specifically, we give a deterministic protocol for computing median with polylog complexity and a randomized protocol that computes an approximate median with polyloglog communication complexity per node. On the negative side, we observe that any deterministic protocol that counts the number of distinct data items must have linear complexity in the worst case.

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

We consider two types of buffering policies that are used in network switches supporting Quality of Service (QoS). In the FIFO type, packets must be transmitted in the order in which they arrive; the constraint in this case is the limited buffer space. In the bounded-delay type, each packet has a maximum delay time by which it must be transmitted, or otherwise it is lost. We study the case of overloads resulting in packet loss. In our model, each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. Our main contribution is a thorough investigation of some natural greedy algorithms in various models. For the FIFO model we prove tight bounds on the competitive ratio of the greedy algorithm that discards packets with the lowest value when an overflow occurs. We also prove that the greedy algorithm that drops the earliest packets among all low-value packets is the best greedy algorithm. This algorithm can be as much as 1.5 times better than the tail-drop greedy policy, which drops the latest lowest-value packets. In the bounded-delay model we show that the competitive ratio of any on-line algorithm for a uniform bounded-delay buffer is bounded away from 1, independent of the delay size. We analyze the greedy algorithm in the general case and in three special cases: delay bound 2, link bandwidth 1, and only two possible packet values. Finally, we consider the off-line scenario. We give efficient optimal algorithms and study the relation between the bounded-delay and FIFO models in this case.

We consider the model of "adversarial queuing theory" for packet networks introduced by Borodin et al. [J. ACM, 48 (2001), pp. 13--38].We show that the scheduling protocol first-in-first-out (FIFO) can be unstable at any injection rate larger than 1/2 and that it is always stable if the injection rate is less than 1/d, where d is the length of the longest route used by any packet. We further show that every work-conserving (i.e., greedy) scheduling policy is stable if the injection rate is less than 1/(d+1).

Separation of concerns and loose coupling of concerns are important issues in software enginnering. In this paper we show how to separate traversal-related concerns from other concerns, how to loosely couple traversal-related concerns to the structural concern, and how to efficiently implement traversal-related concerns. The stress is on the detailed description of our algorithms and the traversal specifications they operate on.Traversal of object structures is a ubiquitous routine in most types of information processing. Ad hoc implementations of traversals lead to scattered and tangled code and in this paper we present a new approach, called traversal strategies, to succinctly modularize traversals. In our approach traversals are defined using a high-level directed graph description, which is compiled into a dynamic road map to assist run-time traversals. The complexity of the compilation algorithm is polynomial in the size of the traversal strategy graph and the class graph of the given application. Prototypes of the system have been developed and are being successfully used to implement traversals for Java and AspectJ [Kiczales et al. 2001] and for generating adapters for software components. Our previous approach, called traversal specifications [Lieberherr 1992; Palsberg et al. 1995], was less general and less succinct, and its compilation algorithm was of exponential complexity in some cases. In an additional result we show that this bad behavior is inherent to the static traversal code generated by previous implementations, where traversals are carried out by invoking methods without parameters.

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

Consider an Internet service provider (ISP), or a corporate intranet, that connects a large number of users with the Internet backbone using an "uplink." Within such a system, consider the traffic oriented towards the uplink, namely the streams whose start points are the local users and whose destination is outside the local domain. These streams are merged by a network that consists of merge nodes, typically arranged in a tree topology whose root is directly connected to the uplink. Without loss of generality, we may assume that the bandwidth of the link emanating from a merge node is less than the sum of bandwidths of incoming links (otherwise, we can assume that the incoming links are connected directly to the next node up). Hence, when all users inject data at maximum local speed, packets will eventually be discarded. A very effective way to mitigate some of the losses due to temporary overloads is to equip the merge nodes with buffers, that can absorb transient bursts by storing incoming packets while the outgoing link is busy. The merge nodes are controlled by local on-line buffer management algorithms whose job is to decide which packets to forward and which to drop so as to minimize the damage in case of an overflow.

We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm that constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to each other process. This result is the first to break the ω(log n) parallel time complexity barrier with small message sizes.

In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design algorithm is a frequency request for each client, and its task is to construct a perfectly periodic schedule that matches the requests as "closely" as possible. The quality of the schedule is measured by the ratios between the requested frequency and the allocated frequency for each client (either by the weighted average or by the maximum of these ratios over all clients). Periodic schedules enjoy maximal fairness, and are very useful in many contexts of asymmetric communication, e.g., push systems and Bluetooth networks. However, finding an optimal periodic schedule is NP-hard in general. Tree scheduling is a methodology for developing perfectly periodic schedules with quality guarantees by constructing trees that correspond to periodic schedules. We explore a few aspects of tree scheduling. First, noting that a complete schedule table may be exponential in size, and that using the tree for scheduling directly may require logarithmic time on average, we give algorithms that find the next client to schedule in constant amortized time, using only polynomial space in most practical cases. Second, we present a few heuristic algorithms for generating schedules, based on analysis of optimal tree-scheduling algorithms, for both the average and maximum measures. Simulation results indicate that some of these heuristics produce excellent schedules in practice, sometimes even beating the best known non-periodic schedules.

In a perfectly-periodic schedule, time is divided into time-slots, and each client is scheduled precisely every some predefined number of slots, called the period of that client. Periodic schedules are useful in wireless communication and other settings. The quality of a schedule is measured by the proportion between the requested and the granted periods: either the maximum over all jobs, or the average. There exist good scheduling algorithms for the average measure in the unit-length single-server model in which all jobs are one slot long, and at most one job is served in each time unit. In this paper we study the general model, where each job may have a different length, and m jobs can be served in parallel for some given m. We give a lower bound for this model which demonstrates the inherent difficulty of multiple lengths, and present a sequence of algorithms, culminating in an algorithm for the general case which is asymptotically optimal under the maximum ratio measure (and hence also the average ratio measure). The new algorithms utilize new techniques which are rather different from the known algorithms used for the unit-length model. Some of the algorithms improve on the best known bounds for the unit-length model.

We consider a FIFO buffer with finite storage space. An arbitrary input stream of packets arrives at the buffer, but the output stream rate is bounded, so overflows may occur. Motivated by DiffServ, we assume that each packet has value either 1 or α, for some α > 1. The buffer management task is to decide which packets to drop so as to minimize the total value of lost packets, subject to the buffer space bound, and to the FIFO order of sent packets. We consider push-out buffers, where the algorithm may eject packets from anywhere in the buffer. The best lower bound on the competitive ratio of on-line algorithms for buffer management is approximately 1.28. In this paper we present an on-line algorithm whose competitive ratio is approximately 1.30 for the worst case α. The best previous general upper bound was about 1.888.

We consider the model of "adversarial queuing theory" for packet networks introduced by Borodin et al. [6]. We show that the scheduling protocol First-In-First-Out (FIFO) can be unstable at any injection rate larger than $1/2$, and that it is always stable if the injection rate is no more than 1/d, where d is the length of the longest route used by any packet. We further show that every work-conserving (i.e., greedy) scheduling policy is stable if the injection rate is no more than 1/(d+1).

We consider the problem of scheduling a set of jobs on a single shared resource using time-multiplexing. A perfectly-periodic schedule is one where resource time is divided into equal size “time-slots” quanta, and each job gets a time slot precisely every fixed interval of time (the period of the job). Periodic schedules are advantageous in distributed settings with synchronized clocks, since they require very little communication to establish, and thereafter no additional communication overhead is needed.

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at most B bits for some parameter B. It is shown that the time required to compute an MST for graphs of diameter 4 or 3 can be as high as Ω(3√n/B) and Ω(4√n/2√B), respectively. The lower bound holds even if the algorithm is allowed to be randomized. On the other hand, it is shown that O(log n) time units suffice to compute an MST deterministically for graphs with diameter 2, when B = O(log n). These results complement a previously known lower bound of Ω(2√n/B) for graphs of diameter Ω(log n).

We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difficulty in this case is the limited buffer space. In the bounded-delay type, each packet has a maximum delay time by which it must be released, or otherwise it is lost. We study the cases where the incoming streams overload the buffers, resulting in packet loss. In our model, each packet has an intrinsic value; the goal is to maximize the total value of packets transmitted

We study jitter control in networks with guaranteed quality of service (QoS) from the competitive analysis point of view: we propose on-line algorithms that control jitter and compare their performance to the best possible (by an off-line algorithm) for any given arrival sequence. For delay jitter, where the goal is to minimize the difference between delay times of different packets, we show that a simple on-line algorithm using a buffer of B slots guarantees the same delay jitter as the best off-line algorithm using buffer space B/2. We prove that the guarantees made by our on-line algorithm hold, even for simple distributed implementations, where the total buffer space is distributed along the path of the connection, provided that the input stream satisfies a certain simple property. For rate jitter, where the goal is to minimize the difference between inter-arrival times, we develop an on-line algorithm using a buffer of size 2B+h for any h/spl ges/1, and compare its jitter to the jitter of an optimal off-line algorithm using buffer size B. We prove that our algorithm guarantees that the difference is bounded by a term proportional to B/h.

In broadcast disk systems, information is broadcast in a shared medium. When a client needs an item from the disk, it waits until that item is broadcast. The fundamental algorithmic problem for such systems is to determine the broadcast schedule based on the demand probability of items, and the cost incurred to the system by clients waiting. The goal is to minimize the mean access cost of a random client. Typically, it was assumed that the access cost is proportional to the waiting time. In this paper, we ask what are the best broadcast schedules for access costs which are arbitrary polynomials in the waiting time. These may serve as reasonable representations of reality in many cases, where the "patience" of a client is not necessarily proportional to its waiting time. We present an asymptotically optimal algorithm for a fluid model, where the bandwidth may be divided to allow for fractional concurrent broadcasting. This algorithm, besides being justified in its own right, also serves as a lower bound against which we test known discrete algorithms. We show that the Greedy algorithm has the best performance in most cases. Then we show that the performance of other algorithms deteriorate exponentially with the degree of the cost polynomial and approach the fractional solution for sub-linear cost. Finally, we study the quality of approximating the greedy schedule by a finite schedule.

We study the average number of delays suffered by packets routed using greedy (work conserving) scheduling policies. We obtain tight bounds on the worst-case average number of delays in a few cases as follows. First, we show that the average number of delays is a function of the number of sources of packets, which is interesting in case a node may send many packets. Then, using a new concept we call delay race, we prove a tight bound on the average number of delays in a leveled graph. Finally, using delay races in a more involved way, we prove nearly-tight bounds on the average number of delays in directed acyclic graphs (DAGs). The upper bound for DAGs is expressed in terms of the underlying topology, and as a result it holds for any acyclic set of routes, even if they are not shortest paths. The lower bound for DAGs, on the other hand, holds even for shortest paths routes.

We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variable-bandwidth stream remotely, while minimizing bandwidth cost, space overhead, and playback delay. We focus on lossy schedules, where some bytes may be dropped due to limited bandwidth or space. We present the following results. First, we determine the optimal tradeoff between buffer space, queuing delay, and link bandwidth for lossy smoothing schedules. Specifically, this means that if one of these parameters is under our control, we can precisely calculate the optimal value which minimizes data loss while avoiding resource wastage. The tradeoff is accomplished by a simple generic algorithm, that allows one some freedom in choosing which data to discard. This algorithm is very easy to implement both at the server and at the client, and it enjoys the nice property that only the server decides which data to discard, and the client needs only to reconstruct the stream.

We introduce the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using k disjoint subsets of the coins. The goal is to minimize the number of coins for any given N and k, while allowing the actual payments to be made on-line, namely without the need to know all payment requests in advance. The problem is motivated by the electronic cash model, where each coin is a long bit sequence, and typical electronic wallets have only limited storage capacity. The k-payment problem has additional applications in other resource-sharing scenarios. Our results include a complete characterization of the k-payment problem as follows. First, we prove a necessary and sufficient condition for a given set of coins to solve the problem. Using this characterization, we prove that the number of coins in any solution to the k-payment problem is at least k H N/k , where H n denotes the nth element in the harmonic series. This condition can also be used to efficiently determine k (the maximal number of exact payments) which a given set of coins allows in the worst case. Secondly, we give an algorithm which produces, for any N and k, a solution with a minimal number of coins. In the case that all denominations are available, the algorithm finds a coin allocation with at most (k+1)H N /(k+1) coins. (Both upper and lower bounds are the best possible.) Finally, we show how to generalize the algorithm to the case where some of the denominations are not available.

Article Optimal and efficient clock synchronization under drifting clocks Share on Authors: Rafail Ostrovsky Bellcore, Morristown, NJ Bellcore, Morristown, NJView Profile , Boaz Patt-Shamir Dept. of Electrical Engineering-Systems, Tel-Aviv University Dept. of Electrical Engineering-Systems, Tel-Aviv UniversityView Profile Authors Info & Claims PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computingMay 1999 Pages 3–12https://doi.org/10.1145/301308.301316Online:01 May 1999Publication History 35citation619DownloadsMetricsTotal Citations35Total Downloads619Last 12 Months12Last 6 weeks4 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

We study jitter control in networks guaranteeing quality of service (QoS). Jitter measures variability of delivery times in packet streams. We propose on-line algorithms that control jitter and compare their performance to the best possible (by an off-line algorithm) for any given arrival sequence. For delay jitter, where the goal is to minimize the difference between delay times of different packets, we give an on-line algorithm using buffer size of 2B which guarantees the same delay-jitter as an off-line algorithm using buffer space B. We show that 2B space is the minimum space required by any on-line algorithm to provide delay-jitter related to the best possible delay-jitter using B buffer space. We also show that the guarantees made by our online algorithm hold even for distributed implementations, where the total buffer space is distributed along the path of the connection, provided that the input stream satisfies a certain simple property. For rate jitter, where the goal is to minimize the difference between inter-arrival times, we develop an on-line algorithm using a buffer of size 2B+h for any h/spl ges/1, and compare its jitter to the jitter of an optimal off-line algorithm using buffer size B. Our algorithm guarantees that the difference is bounded by a term proportional to B/h. We also prove that 2B space is necessary for on-line algorithms with non trivial guarantees for rate-jitter control.

No abstract available.

We study the scenario where a transient fault hit f of the n nodes of a distributed system by corrupting their state. We consider the basic persistent bit problem, where the system is required to maintain a 0/1 value in the face of transient failures by means of replication. We give an algorithm to recover the value quickly: the value of the bit is recovered at all nodes in O(f) time units for an unknown f ! n=2. Moreover, complete state quiescence occurs in O(diam) time units, where diam denotes the actual diameter of the network. This means that the value persists indefinitely so long as any f ! n=2 faults are followed by \\Omega\\Gamma diam) fault-free time units. We prove matching lower bounds on both the output stabilization time and the state quiescence time. Using our persistent bit algorithm, we present a general transformer which takes a distributed non-reactive non-stabilizing protocol P , and produces a self-stabilizing protocol P 0 which solves the problem P solv...

Article Free Access Share on Many-to-one packet routing on grids Authors: Yishay Mansour Department of Computer Science, Tel-Aviv University Department of Computer Science, Tel-Aviv UniversityView Profile , Boaz Patt-Shamir College of Computer Science, Northeastern University College of Computer Science, Northeastern UniversityView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 258–267https://doi.org/10.1145/225058.225136Online:29 May 1995Publication History 15citation283DownloadsMetricsTotal Citations15Total Downloads283Last 12 Months9Last 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

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

We consider the problem of clock synchronization with uncertain message delays and bounded clock drifts. To analyze this classical problem we introduce a characterization theorem for the tightest achievable estimate of the readings of a remote clock in any given execution of the system. Using this theorem, we obtain the first optimal on-line distributed algorithms for clock synchronization. The algorithms are optimal for all executions, rather than only worst cases. The general algorithm for systems with drifting clocks has high space overhead, which is unavoidable, as we show. For systems with drift-free clocks (i.e., clocks that run at the rate of real time), we present a remarkably simple and efficient algorithm. The discussion focuses on the variant where one of the clocks shows real time, but we present results also for the case where real time...

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

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.

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

We investigate the simple class of greedy scheduling algorithms, that is, algorithms that always forward a packet if they can.Assuming that the routes traversed by a set of packets are distance optimal ("shortest pat hs" ), we prove that the time required to complete transmission of a packet in a the set is bounded by its route length plus the number of other packets in the set.This bound holds for any greedy algorithm, even, in the case of different starting times and different route lengths.Furthermore, the result holds in the asynchronous model, using the same proof technique.The generality of our result is demonstrated by a variety of applications.We present a simple protocol, for which we derive a general bound on the throughput with any greedy scheduling.Another protocol for the dynamic case is presented, whose packet delivery time is bounded by the length of the route of the packet plus the number of packets in the network in the time it is sent.