We examine sorting algorithms for $n$ elements whose basic operation is comparing $t$ elements simultaneously (a $t$-comparator). We focus on algorithms that use only a single round or two rounds -- comparisons performed in the second round depend on the outcomes of the first round comparators. We design deterministic and randomized algorithms. In the deterministic case, we show an interesting relation to design theory (namely, to 2-Steiner systems), which yields a single-round optimal algorithm for $n=t^{2^k}$ with any $k\ge 1$ and a variety of possible values of $t$. For some values of $t$, however, no algorithm can reach the optimal (information-theoretic) bound on the number of comparators. For this case (and any other $n$ and $t$), we show an algorithm that uses at most three times as many comparators as the theoretical bound. We also design a randomized Las-Vegas two-rounds sorting algorithm for any $n$ and $t$. Our algorithm uses an asymptotically optimal number of $O(\max(\frac{n^{3/2}}{t^2},\frac{n}{t}))$ comparators, with high probability, i.e., with probability at least $1-1/n$. The analysis of this algorithm involves the gradual unveiling of randomness, using a novel technique which we coin the binary tree of deferred randomness.

This paper initiates the study of the art of listening from a social network perspective. A conversation between several people is a significant human activity. We propose a novel structure, the directed conversation hypergraph, to capture the dynamic interplay between a speaker and a listener and further explore its evolution over time.

Theoretical study of optimization problems in wireless communication often deals with tasks that concern a single point. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting station s i is successfully received at a single receiver point r i . This paper aims at addressing communication applications that require handling two-dimensional tasks (e.g., guaranteeing successful transmission in entire regions rather than at specific points). The natural approach to two-dimensional optimization tasks is to discretize the optimization domain, e.g., by sampling points within the domain. The straightforward implementation of the discretization approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions. The alternative proposed and explored in this paper is based on establishing the minimum principle 1 for the signal to interference and noise ratio (SINR) function with free space path loss (i.e., when the signal decays in proportion to the square of the distance between the transmitter and receiver). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain without losing anything in the accuracy or quality of the solution. More specifically, when the two-dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize the SINR function over the boundary of the domain, as the “hardest” points to be satisfied reside on the boundary and not in the interior. We then utilize the minimum principle as the basis for an improved discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., power control, energy minimization); in providing tight bounds on the number of null cells in the reception map; and in approximating geometric and topological properties of the wireless reception map (e.g., maximum inscribed sphere). The minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, are expected to pave the way to future study of algorithmic SINR in higher dimensions.

Studying distributed computing through the lens of algebraic topology has been the source of many significant breakthroughs during the last two decades, especially in the design of lower bounds or impossibility results for deterministic algorithms. In a nutshell, this approach consists of capturing all the possible states of a distributed system at a certain time as a simplicial complex called protocol complex, and viewing computation as a simplicial map from that complex to the so-called output complex, that captures all possible legal output states of the system.

In the future, analysis of social networks will conceivably move from graphs to hypergraphs. However, theory has not yet caught up with this type of data organizational structure. By introducing and analyzing a general model of preferential attachment hypergraphs, this paper makes a step towards narrowing this gap. We consider a random preferential attachment model H(p, Y) for network evolution that allows arrivals of both nodes and hyperedges of random size. At each time step t, two possible events may occur: (1) [vertex arrival event:] with probability p > 0 a new vertex arrives and a new hyperedge of size Yt, containing the new vertex and Yt − 1 existing vertices, is added to the hypergraph; or (2) [hyperedge arrival event:] with probability 1 − p, a new hyperedge of size Yt, containing Yt existing vertices, is added to the hypergraph. In both cases, the involved existing vertices are chosen independently at random according to the preferential attachment rule, i.e., with probability proportional to their degree, where the degree of a vertex is the number of edges containing it. Assuming general restrictions on the distribution of Yt, we prove that the H(p, Y) model generates power law networks, i.e., the expected fraction of nodes with degree k is proportional to k−1−⌈, where [EQUATION]. This extends the special case of preferential attachment graphs, where Yt = 2 for every t, yielding ⌈ = 2/(2 − p). Therefore, our results show that the exponent of the degree distribution is sensitive to whether one considers the structure of a social network to be a hypergraph or a graph. We discuss, and provide examples for, the implications of these considerations.

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.

This paper demonstrates that the Preferential Attachment rule naturally emerges in the context of evolutionary network formation, as the unique Nash equilibrium of a simple social network game. In this game, each node aims at maximizing its degree in the future, representing its social capital in the "society" formed by the nodes and their connections. This result provides additional formal support to the commonly used Preferential Attachment model, initially designed to capture the "rich get richer" aphorism. In the process of establishing our result, we expose new connections between Preferential Attachment, random walks, and Young»s Lattice.

Population control policies are proposed and in some places employed as a means towards curbing population growth. This paper is concerned with a disturbing side-effect of such policies, namely, the potential risk of societal fragmentation due to changes in the distribution of family sizes. This effect is illustrated in some simple settings and demonstrated by simulation. In addition, the dependence of societal fragmentation on family size distribution is analyzed. In particular, it is shown that under the studied model, any population control policy that disallows families of 3 or more children incurs the possible risk of societal fragmentation.

Consider a random preferential attachment model G(p) for network evolution that allows both node and edge arrivals. Starting with an arbitrary nonempty graph G0, at each time step, there are two possible events: with probability p > 0 a new node arrives and a new edge is added between the new node and an existing node, and with probability 1 - p a new edge is added between two existing nodes. In both cases, the involved existing nodes are chosen at random according to preferential attachment, i.e., with probability proportional to their degree. G(p) is known to generate power law networks, i.e., the fraction of nodes with degree k is proportional to k-β. Here β=(4-p)/(2-p) is in the range (2,3].

In this paper we analyse the core-periphery clustering properties of collaboration networks, where the core of a network is formed by the nodes with highest degree. In particular, we first observe that, even for random graph models aiming at matching the degree-distribution and/or the clustering coefficient of real networks, these models produce synthetic graphs which have a spatial distribution of the triangles with respect to the core and to the periphery which does not match the spatial distribution of the triangles in the real networks. We therefore propose a new model, called CPCL, whose aim is to distribute the triangles in a way fitting with their real core-periphery distribution, and thus producing graphs matching the core-periphery clustering of real networks.

The main question that this paper addresses is how to identify critical events in the evolution of a social network. The paper uses ideas from psychology about time perception. It is well known that time flows differently in different emotional situations. Equipped with this idea, this paper studies the relationship between two clocks. As opposed to standard synchronization, where everything is done in order to force clocks to agree on the time, the paper embraces the discrepancy between the clocks. This paper presents a standard model where two natural clocks exists simultaneously: the event clock Ceand the weighted clock Cw. As the paper shows, using the drift between those two clocks is useful to understand the dynamics in social networks. The main claim is that the drift between different clocks points to a critical event in the evolution of the social network, similar to time perception in psychology. In order to demonstrate this claim, plays by William Shakespeare were used, and from them two clocks were created: the “word time”, which is the weighted clock, and the “response time”, which is the event clock. The paper will introduce the concept of a single clock drift. A play can have many, or a single clock drift events. It is shown that in the single clock drift plays, the beginning of the drift points to a critical event in the play. The results are compared with the “standard common” opinion.

Leskovec, Kleinberg and Faloutsos (2005) observed that many social networks exhibit properties such as shrinking (i.e. bounded) diameter, densification, and (power-law) heavy tail degree distributions. To explain these phenomena, they introduced a generative model, called the Forest Fire model, and using simulations showed that this model indeed exhibited these properties; however, proving this rigorously was left as an open problem. In this paper, we analyse one of these properties, shrinking diameter. We define a restricted version of their model that incorporates the main features that seem to contribute towards this property, and prove that the graphs generated by this model exhibit shrinking distance to the seed graph. We prove that an even simpler model, the random walk model, already exhibits this phenomenon.

This paper initiates the study of locally self-adjusting networks: networks whose topology adapts dynamically and in a decentralized manner, to the communication pattern σ. Our vision can be seen as a distributed generalization of the self-adjusting datastructures introduced by Sleator and Tarjan, 1985: In contrast to their splay trees which dynamically optimize the lookup costs from a single node (namely the tree root), we seek to minimize the routing cost between arbitrary communication pairs in the network. As a first step, we study distributed binary search trees (BSTs), which are attractive for their support of greedy routing. We introduce a simple model which captures the fundamental tradeoff between the benefits and costs of self-adjusting networks. We present the SplayNet algorithm and formally analyze its performance, and prove its optimality in specific case studies. We also introduce lower bound techniques based on interval cuts and edge expansion, to study the limitations of any demand-optimized network. Finally, we extend our study to multi-tree networks, and highlight an intriguing difference between classic and distributed splay trees.

Is there a bias in paper selection processes for conferences? This work addresses one aspect of this question, and empirically examines if there is a bias in favor of the collaborators of the technical program committee members. Specifically, we check whether a paper written by a past collaborator of a program committee member is more likely to be accepted to the conference. If so, one might say that the program committee members were biased; if not, then they are fair. In order to answer the bias question, we studied 12 ACM/IEEE conferences over several years. For each annual meeting of a conference we constructed its social network, whose vertices are the program committee members and the authors of the papers accepted to the meeting. Two researchers are collaborators (neighbors in the network) if they have co-authored a paper before the meeting. In turn, for each meeting network, we calculated the coverage of the program committee in the network, which is the ratio between the number of authors that are collaborators of the program committee, and the total number of the authors-vertices of the meeting. We compared the coverage of the real meeting's social networks, to the coverage in artificially generated meetings (random and others). We view a program committee as coverage biased if its coverage is significantly higher than that of corresponding artificially generated meetings of the conference. Our findings show that, although there are some coverage biased program committees, in most meetings, the coverage in the real meetings is the same as, and sometimes less than, the artificially generated ones, indicating that on average there is probably no bias in favor of papers written by collaborators of the program committee members for these high quality conferences.

This paper suggests a voting algorithm for predicting people's choices. Usually, once a new algorithm is offered, one needs to prove the soundness of the algorithm, i.e., showing that the algorithm does the thing it is set up to do. But in the case of election prediction algorithms it's not clear how to prove their soundness. This paper offers a way to deal with this problem by analysing the social networks of plays, following Shakespeare dictum: "all the world is a stage, and all the men and women merely players", As you like it, act I scene VII.

Theoretical study of optimization problems in wireless communication often deals with zero-dimensional tasks. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting station is successfully received at a single receiver point. This paper aims at addressing communication applications that require handling 2-dimensional tasks (e.g., Guaranteeing successful transmission in entire regions rather than in specific points). A natural approach to such tasks is to discretize the 2-dimensional optimization domain, e.g., By sampling points within the domain. This approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions. Towards this goal, we establish the minimum principle for the SINR function with free-space path loss (i.e., When the signal decays in proportion to the square of the distance between the transmitter and receiver). We then utilize it as a discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., Power control, energy minimization), in providing tight bounds on the number of null-cells in the reception map, and in approximating geometrical and topological properties of the wireless reception map (e.g., Maximum inscribed sphere). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain without losing anything in the accuracy or quality of the solution. More specifically, when the two dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize over the boundary of the domain, as the "hardest" points to be satisfied reside on boundary and not in the interior. We believe that the minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, may pave the way to future study of algorithmic SINR in higher dimensions.

The glass ceiling effect has been defined in a recent US Federal Commission report as "the unseen, yet unbreakable barrier that keeps minorities and women from rising to the upper rungs of the corporate ladder, regardless of their qualifications or achievements". It is well documented that many societies and organizations exhibit a glass ceiling. In this paper we formally define and study the glass ceiling effect in social networks and propose a natural mathematical model, called the biased preferential attachment model, that partially explains the causes of the glass ceiling effect. This model consists of a network composed of two types of vertices, representing two sub-populations, and accommodates three well known social phenomena: (i) the "rich get richer" mechanism, (ii) a minority-majority partition, and (iii) homophily. We prove that our model exhibits a strong moment glass ceiling effect and that all three conditions are necessary, i.e., removing any one of them will prevent the appearance of a glass ceiling effect. Additionally, we present empirical evidence taken from a mentor-student network of researchers (derived from the DBLP database) that exhibits both a glass ceiling effect and the above three phenomena.

This article studies the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multistation network, we use the convenient representation of a reception map, which partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in Avin et al. [2009] for the specific case where all stations use the same power. It was shown that the reception zones are convex (hence connected) and fat, and this was used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or nonuniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the nonuniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). Our key result exhibits a striking contrast between d - and ( d +1)-dimensional maps for a network embedded in d -dimensional space. Specifically, it is shown that whereas the d -dimensional map might be highly fractured, drawing the map in one dimension higher “heals” the zones, which become connected (in fact, hyperbolically connected). We also provide bounds for the fatness of reception zones. Subsequently, we consider algorithmic applications and propose a new variant of approximate point location.

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.

This paper initiates the study of self-adjusting networks (or distributed data structures) whose topologies dynamically adapt to a communication pattern σ. We present a fully decentralized self-adjusting solution called SplayNet. A SplayNet is a distributed generalization of the classic splay tree concept. It ensures short paths (which can be found using local-greedy routing) between communication partners while minimizing topological rearrangements. We derive an upper bound for the amortized communication cost of a SplayNet based on empirical entropies of σ, and show that SplayNets have several interesting convergence properties. For instance, SplayNets features a provable online optimality under special requests scenarios. We also investigate the optimal static network and prove different lower bounds for the average communication cost based on graph cuts and on the empirical entropy of the communication pattern σ. From these lower bounds it follows, e.g., that SplayNets are optimal in scenarios where the requests follow a product distribution as well. Finally, this paper shows that in contrast to the Minimum Linear Arrangement problem which is generally NP-hard, the optimal static tree network can be computed in polynomial time for any guest graph, despite the exponentially large graph family. We complement our formal analysis with a small simulation study on a Facebook graph.

The celebrated Perron–Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors and eigenvalues. The importance of this theorem stems from the fact that eigenvalue problems on such matrices arise in many fields of science and engineering, including dynamical systems theory, economics, statistics and optimization. However, many real-life scenarios give rise to nonsquare matrices. Despite the extensive development of spectral theories for nonnegative matrices, the applicability of such theories to non-convex optimization problems is not clear. In particular, a natural question is whether the PF Theorem (along with its applications) can be generalized to a nonsquare setting. Our paper provides a generalization of the PF Theorem to nonsquare multiple choice matrices. The extension can be interpreted as representing systems with additional degrees of freedom, where each client entity may choose between multiple servers that can cooperate in serving it (while potentially interfering with other clients). This formulation is motivated by applications to power control in wireless networks, economics and others, all of which extend known examples for the use of the original PF Theorem. We show that the option of cooperation does not improve the situation, in the sense that in the optimum solution, no cooperation is needed, and only one server per client entity needs to work. Hence, the additional power of having several potential servers per client translates into choosing the “best” single server and not into sharing the load between the servers in some way, as one might have expected. The two main contributions of the paper are (i) a generalized PF Theorem that characterizes the optimal solution for a non-convex problem, and (ii) an algorithm for finding the optimal solution in polynomial time. In addition, we extend the definitions of irreducibility and largest eigenvalue of square matrices to nonsquare ones in a novel and non-trivial way, which turns out to be necessary and sufficient for our generalized theorem to hold. To characterize the optimal solution, we use techniques from a wide range of areas. In particular, the analysis exploits combinatorial properties of polytopes, graph-theoretic techniques and analytic tools such as spectral properties of nonnegative matrices and root characterization of integer polynomials.

We use distributed computing tools to provide a new perspective on the behavior of cooperative biological ensembles. We introduce the Ants Nearby Treasure Search (ANTS) problem, a generalization of the classical cow-path problem [10, 20, 41, 42], which is relevant for collective foraging in animal groups. In the ANTS problem, k identical (probabilistic) agents, initially placed at some central location, collectively search for a treasure in the two-dimensional plane. The treasure is placed at a target location by an adversary and the goal is to find it as fast as possible as a function of both k and D, where D is the distance between the central location and the target. This is biologically motivated by cooperative, central place foraging, such as performed by ants around their nest. In this type of search there is a strong preference to locate nearby food sources before those that are further away. We focus on trying to find what can be achieved if communication is limited or altogether absent. Indeed, to avoid overlaps agents must be highly dispersed making communication difficult. Furthermore, if the agents do not commence the search in synchrony, then even initial communication is problematic. This holds, in particular, with respect to the question of whether the agents can communicate and conclude their total number, k. It turns out that the knowledge of k by the individual agents is crucial for performance. Indeed, it is a straightforward observation that the time required for finding the treasure is Ω(D + D2/k), and we show in this paper that this bound can be matched if the agents have knowledge of k up to some constant approximation.

This paper studies the reception zones of a wireless network in the SINR model with receivers that employ interference cancellation (IC). IC is a recently developed technique that allows a receiver to decode interfering signals, and cancel them from the received signal in order to decode its intended message. We first derive the important topological properties of the reception zones and their relation to high-order Voronoi diagrams and other geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings, and as a result, reception zones, in fact there are much fewer nonempty such zones. We prove a linear bound (hence tight) on the number of zones and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel parameter, the Compactness Parameter, which influences the tightness of our bounds. We then utilize these properties to devise a logarithmic time algorithm to answer point-location queries for networks with IC.

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks. This article focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, we have shown that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.

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.

The power control problem for wireless networks in the SINR model requires determining the optimal power assignment for a set of communication requests such that the SINR threshold is met for all receivers. If the network topology is known to all participants, then it is possible to compute an optimal power assignment in polynomial time. In realistic environments, however, such global knowledge is usually not available to every node. In addition, protocols that are based on global computation cannot support mobility and hardly adapt when participants dynamically join or leave the system. In this paper we present and analyze a fully distributed power control protocol that is based on local information. For a set of communication pairs, each consisting of a sender node and a designated receiver node, the algorithm enables the nodes to converge to the optimal power assignment (if there is one under the given constraints) quickly with high probability. Two types of bounded resources are considered, namely, the maximal transmission energy and the maximum distance between any sender and receiver. It is shown that the restriction to local computation increases the convergence rate by only a multiplicative factor of O(log n + log log Ψmax), where Ψmaxis the maximal power constraint of the network. If the diameter of the network is bounded by Lmaxthen the increase in convergence rate is given by O(log n + log log Lmax).

Consider the problem of source coding with side information in large networks with multiple receivers. In this case, standard coding techniques are either prohibitively complex to decode, or require source-network coding separation, resulting in sub-optimal transmission schemes. To alleviate this problem, we offer a joint network-source coding scheme based on matrix sparsification at the code design phase, which allows the terminals to use an efficient decoding procedure (syndrome decoding using LDPC), despite the network coding throughout the network. Via a novel relation between matrix sparsification and rate-distortion theory, we give lower and upper bounds on the best achievable sparsification performance, and analyze our scheme in the limit of weak side information at the receivers. Simulation results motivate the use of this scheme at non-limiting rates as well.

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate k distinct messages to all n nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of O((k + log n + D)Δ) rounds with high probability, where D and Δ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of k this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is Θ(k + D).

We consider an anchor-free, relative localization and synchronization problem where a set of n receiver nodes and m wireless signal sources are independently, uniformly, and randomly distributed in a disk in the plane. The signals can be distinguished and their capture times can be measured. At the beginning neither the positions of the signal sources and receivers are known nor the sending moments of the signals. Now each receiver captures each signal after its constant speed journey over the unknown distance between signal source and receiver position. Given these nm capture times the task is to compute the relative distances between all synchronized receivers. In a more generalized setting the receiver nodes have no synchronized clocks and need to be synchronized from the capture times of the stolen signals.

In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a reception map. In the SINR model, the resulting SINR diagram partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in [3] for the specific case where all stations use the same power. It is shown that the reception zones are convex (hence connected) and fat, and this is used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the non-uniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line and use this to derive a tight bound on the number of connected components in this case. In addition, one of our key results concerns the behavior of a (d+1)-dimensional map, i.e., a map in one dimension higher than the dimension in which stations are embedded. Specifically, although the d-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected (in fact hyperbolically connected). In addition, as a step toward establishing a weaker form of convexity for the d-dimensional map, we study the interference function and show that it satisfies the maximum principle. This is done through an analysis technique based on looking at the behavior of systems composed on lines of densely placed weak stations, as the number of stations tends to infinity, keeping their total transmission energy fixed. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.

We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size n is O(Δn) where Δ is the maximum degree of the graph. This leads to a tight bound of Θ(n) for bounded degree graphs and an upper bound of O(n2) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of Ω(n2). Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research.

In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining whether such an augmentation is possible for all graphs. In this paper, we answer this question negatively by exhibiting an infinite family of graphs that cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most $O(\log\log n)$ are navigable. We show that for doubling dimension $\gg\log\log n$, an infinite family of graphs cannot be augmented to become navigable. Finally, we present a positive navigability result by studying the special case of square meshes of arbitrary dimension that we prove to always be augmentable to become navigable. This latter result complements Kleinberg's original result and shows that adding extra links can sometimes break the navigability.

Ethernet is widely used in Local Area Networks (LANs) due to its simplicity and cost effectiveness. Today, a great deal of effort is being devoted to extending Ethernet capabilities in order to elevate it from a LAN technology to a ubiquitous networking technology, suitable for deployment in Metropolitan Area Networks (MANs) and even in core, Wide Area Networks (WANs). Current standardized Ethernet networks are based on a spanning tree topology, using the Rapid Spanning Tree Protocol (RSTP) or Multiple Spanning Tree Protocol (MSTP). The spanning tree architecture is useful for avoiding forwarding loops, but may lead to low link utilization and long failure recovery time. In this paper we propose to shift from tree to Directed Acyclic Graph (DAG) topologies and offer a new bridged Ethernet architecture called Orient. Orient is based on assigning an orientation state to each port in the network in order to prevent loops. Thus, the Orient architecture enables a full utilization of all network links and ports, while maintaining simplicity of implementation and compliance with the standardized spanning tree protocols.

Modeling communications in wireless networks is a challenging task, since it requires a simple mathematical object on which efficient algorithms can be designed but which must also reflect the complex physical constraints inherent in wireless networks, such as interferences, the lack of global knowledge, and purely local computations. As a tractable mathematical object, the unit disk graph (UDG) is a popular model that has enabled the development of efficient algorithms for crucial networking problems. In a rho-UDG, two nodes are connected if and only if their distance is at most rho, for some rho > 0. However, such a connectivity requirement is basically not compatible with the reality of wireless networks due to the environment of the nodes as well as the constraints of radio transmission. For this purpose, the signal interference plus noise ratio model (SINR) is the more commonly used model. The SINR model focuses on radio interferences created over the network depending on the distance to transmitters. Nevertheless, due to its complexity, this latter model has been the subject of very few theoretical investigations and lacks of good algorithmic features. In this paper, we demonstrate how careful scheduling of the nodes enables the two models to be combined to give the benefits of both the algorithmic features of the UDG and the physical validity of the SINR. Precisely, we show that it is possible to emulate a 1/radic(n ln n)-UDG that satisfies the constraints of the SINR over any set of n wireless nodes distributed uniformly in a unit square, with only a O(ln3n) time and power stretch factor. The main strength of our contribution lies in the fact that the scheduling is set in a fully distributed way and considers non-uniform power ranges, and it can therefore fit the sensor network setting. Moreover, our scheduling is optimal up to a polylogarithmic factor in terms of throughput capacity according to the lower bound of Gupta and Kumar.

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard.

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 pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probablistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

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.

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.

Augmented graphs were introduced for the purpose of analyzing the "six degrees of separation between individuals" observed experimentally by the sociologist Standley Milgram in the 60's. Formally, an augmented graph is a pair (G,φ) where G is a graph, and φ is a collection of probability distributions {φu, u ∈ V(G)}. Every node u ∈ V(G) is given an extra link, called a long range link, pointing to some node v, called the long range contact of u. The head v of this link is chosen at random by Pr{u → v} = φu(v). In augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses among all its neighbors (including its long range contact) the one that is closest to the target according to the distance measured in the underlying graph G, and forwards to it. Roughly, augmented graphs aim at modeling the structure of social networks, while greedy routing aims at modeling the searching procedure applied in Milgram's experiment. Our objective is to design efficient universal augmentation schemes, i.e., augmentation schemes that give to any graph G a collection of probability distributions φ such that greedy routing in (G,φ) is fast. It is known that the uniform scheme φunif is a universal scheme ensuring that, for any n-node graph G, greedy routing in (G,φunif) performs in O(√n) expected number of steps. Our main result is the design of a universal augmentation scheme φ such that greedy routing in (G,φ) performs in Õ(n1/3) expected number of steps for any n-node graph G. We also show that under some more restricted model, the √n-barrier cannot be overcome.

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

Some of the first routing algorithms for position-aware wireless networks used the Delaunay triangulation of the point-locations of the network's nodes as the underlying connectivity graph. Later on these solutions were considered impractical because the Delaunay triangulation may in general contain arbitrarily long edges and because calculating the Delaunay triangulation may require a global view of the network. Many other algorithms were then suggested for geometric routing, often assuming random placement of network nodes for analysis or simulation [27, 5, 28, 15]. But as we show, when the nodes are uniformly placed in the unit disk the Delaunay triangulation does not contain long edges, it is easy to compute locally and it is in many ways optimal for geometric routing and flooding.In particular, we prove that with high probability the maximal length of an edge in Del(P), the Delaunay triangulation of a set P of n nodes uniformly placed in the unit disk, is O(3√3log novern), and that the expected sum of squares of all the edges in Del(P) is O(1). These geometric results imply that for wireless networks, randomly distributed in a unit disk (1) computing the Delaunay triangulation locally is asymptotically easy; (2) simple "face routing" through the Delaunay triangulation optimizes, up to poly-logarithmic factors, the energy load on the nodes, and (3) flooding the network, an operation quite common in sensor nets, is with high probability optimal up to a constant factor. The last property is particularly important for geocasting because the Delaunay triangulation is known to be a spanner.

We study the stability of the commonly used packet forwarding protocol, FIFO (first in first out), in the adversarial queueing model. We prove that FIFO can become unstable, i.e., lead to unbounded buffer-occupancies and queueing delays, at arbitrarily low injection rates. In order to demonstrate instability at rate r, we use a network of size $\tilde{O}(1/r)$.

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

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.

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system $(X,{\cal S})$, where each $S \in {\cal S}$ is a subset of X. The output is a coloring $\chi$ of the sets in ${\cal S}$ that satisfies the following constraint: for every $x \in X$ there exists a color i and a unique set $S \in {\cal S}$ such that $x \in S$ and $\chi(S) = i$. The goal is to minimize the number of colors used by the coloring $\chi$. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, $\Theta(\log n)$ colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system $(X,{\cal S})$, the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set $S \in {\cal S}$ contains a point whose color appears only once in S. We show that O(log |X|) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. This result is used in proving that O(log n) colors suffice in the primal version.

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem called minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system (X, S), where each S /spl isin/ S is a subset of X. The output is a coloring X of the sets in S that satisfies the following constraint: for every x /spl isin/ X there exists a color i and a unique set S /spl isin/ S, such that x /spl isin/ S and /spl chi/(S) = i. The goal is to minimize the number of colors used by the coloring X. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and non-congruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle) regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally-symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). For rectangles and hexagons we obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also show that, even in the case of unit disks, /spl Theta/(log n) colors may be necessary.

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

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