Negative frequency-dependent selection (i.e., declining fitness with increased frequency in the population) is thought to be one of the factors that maintains biological diversity. In this paper, we give a concrete mathematical argument supporting this. Our model is as follows: A collection of species derive their fitnesses via a rock-paper-scissors-type game whose precise payoffs are a function of the environment. The new aspect of our model lies in adding a feedback loop: the environment changes according to the relative fitnesses of the species (hence, payoffs change as a function of fitness, which in turn changes as a function of payoffs). The changes in the payoffs are in keeping with the principle of negative frequency-dependent selection, which is widespread in nature. In order to model our game as a continuous time dynamical system, we cast it in the setting of a differential game. We show that for certain parameters, this dynamics cycles, i.e., no species goes extinct and diversity is maintained. We believe that our techniques can be applied to optimization and machine learning to show that first order methods (e.g., gradient descent/ascent) do cycle even in online settings in which the loss function changes with time.

We focus on efficient protocols that enhance a network with topology awareness. We discuss centralized algorithms with provable performance, and introduce decentralized asynchronous heuristics that use only local information and local computations. These algorithms are based on distributed solutions of convex programs expressing optimization of various spectral properties of the matrix associated with the graph of the network topology. For example, these algorithms assign special weights to links crossing or directed towards small cuts by minimizing the second eigenvalue. Our main technical ingredient is to perform the decentralized asynchronous computations in a manner that preserves critical invariants of the exact second eigenvalue of the adjacency matrix associated with the network topology.

We propose a routing overlay system, MobCast, for simple and efficient routing to mobile hosts. Mobcast nodes advertise the same address space at each proxy location, and each mobile host is assigned a "universal" IP address from this address space, so packets sent to a mobile host's universal IP address automatically go to the nearest proxy on the overlay. The overlay then delivers the packets to the mobile host. Our architecture enables seamless mobility for both micro and macro mobility. While our initial design is not as mature as Mobile IP, it shows great promise to solve the traditional problems of ingress routing, firewalls, NATs, and rapid mobility with much lower complexity. We present our design as a scalable and deployable alternative to mobile IP. In this paper, we focus on describing the MobCast system architecture. We form our arguments for scalability, handoff-speed, and simplicity, and give our initial results for scalability. We postpone a detailed discussion of MobCast's security model for future work.

We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the flip. The motivation for studying the flip Markov chain arises in the context of unstructured peer-to-peer networks, which constantly perform such flips in an effort to randomize. We show that the flip Markov chain on regular graphs is rapidly mixing, thus justifying this widely used peer-to-peer networking practice. Our mixing argument uses the Markov chain comparison technique. In particular, we extend this technique to embedding arguments where the compared Markov chains are defined on different state spaces. We give several conditions which generalize our results beyond regular graphs

We study hybrid search schemes for unstructured peer-to-peer networks. We quantify performance in terms of number of hits, network overhead, and response time. Our schemes combine flooding and random walks, look ahead and replication. We consider both regular topologies and topologies with supernodes. We introduce a general search scheme, of which flooding and random walks are special instances, and show how to use locally maintained network information to improve the performance of searching. Our main findings are: (a) a small number of supernodes in an otherwise regular topology can offer sharp savings in the performance of search, both in the case of search by flooding and search by random walk, particularly when it is combined with 1-step replication. We quantify, analytically and experimentally, that the reason of these savings is that the search is biased towards nodes that yield more information. (b) There is a generalization of search, of which flooding and random walk are special instances, which may take further advantage of locally maintained network information, and yield better performance than both flooding and random walk in clustered topologies. The method determines edge critically and is reminiscent of fundamental heuristics from the area of approximation algorithms.

We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achieves better results than flooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its horizon does not change much. For construction, we argue that an expander can he maintained dynamically with constant operations per addition. The key technical ingredient of our approach is a deep result of stochastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical properties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such connectivity is desired, and believed to hold, in every reasonable network and network model). This property has been previously used in complexity theory for construction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random bits to savings in processing overhead.

We show that random graphs in the preferential connectivity model have constant conductance, and hence have worst-case routing congestion that scales logarithmically with the number of nodes. Another immediate implication is constant spectral gap between the first and second eigenvalues of the random walk matrix associated with these graphs. We also show that the expected frugality (overpayment in the Vickrey-Clarke-Groves mechanism for shortest paths) of a random graph is bounded by a small constant.

Spectral analysis of the Internet topology at the autonomous system (AS) level, by adapting the standard spectral filtering method of examining the eigenvectors corresponding to the largest eigenvalues of matrices related to the adjacency matrix of the topology is performed. We observe that the method suggests clusters of ASs with natural semantic proximity, such as geography or business interests. We examine how these clustering properties vary in the core and in the edge of the network, as well as across geographic areas, over time, and between real and synthetic data. We observe that these clustering properties may be suggestive of traffic patterns and thus have direct impact on the link stress of the network. Finally, we use the weights of the eigenvector corresponding to the first eigenvalue to obtain an alternative hierarchical ranking of the ASs.

Strategyproof cost-sharing mechanisms, lying in the core, that recover 1/α fraction of the cost, are presented for the set cover and facility location games; α = O(log n) for the former and 1.861 for the latter. Our mechanisms utilize approximation algorithms for these problems based on the method of dual-fitting.

It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to support? How does performance scale with the size of the network? We study routing in families of sparse random graphs whose degrees follow heavy tailed distributions. Instantiations of such random graphs have been proposed as models for the topology of the Internet at the level of Autonomous Systems as well as at the level of routers. Let n be the number of nodes. Suppose that for each pair of nodes with degrees du and dv we have O(dudv ) units of demand. Thus the total demand is O(n ). We argue analytically and experimentally that in the considered random graph model such demand patterns can be routed so that the flow through each link is at most O . This is to be compared with a bound # that holds for arbitrary graphs. Similar results were previously known for sparse random regular graphs, a.k.a. "expander graphs." The significance is that Internet-like topologies, which grow in a dynamic, decentralized fashion and appear highly inhomogeneous, can support routing with performance characteristics comparable to those of their regular counterparts, at least under the assumption of uniform demand and capacities. Our proof uses approximation algorithms for multicommodity flow and establishes strong bounds of a generalization of "expansion," namely "conductance." Besides routing, our bounds on conductance have further implications, most notably on the gap between first and second eigenvalues of the stochastic normalization of the adjacency matrix of the graph.

A commonly used and powerful technique for improving query response time over very large databases is to precompute ('Lmaterialize") frequently' asked queries ("views").

We address efficient access to bandwidth in WDM (wavelength division multiplexing) optical networks. We consider tree topologies, ring topologies, as well as trees of rings. These are topologies of concrete practical relevance for which undirected underlying graph models have been studied before by P. Raghavan and E. Upfal (1993). As opposed to previous studies (A. Aggarwal et al., 1993; R. Pankaj, 1992; P. Raghavan and E. Upfal, 1993), we consider directed graph models. Directedness of fiber links is dictated by physical directedness of optical amplifiers. For trees, we give a polynomial time routing algorithm that satisfies requests of maximum load L/sub max/ per fiber link using no more than 15L/sub max//8/spl les/15OPT/8 optical wavelengths. This improves a 2L/sub max/ scheme that is implicit by P. Raghavan and E. Upfal by extending their undirected methods to our directed model. Alternatively stated, for fixed W wavelength technology, we can load the network up to L,, 8W/15 rather than W/2. In engineering terms, this is a so called "6.66% increase of bandwidth" and it is considered substantial. For rings, the approximation factor is 2OPT. For trees of rings, the approximation factor is 15OPT/4. Technically, optical routing requirements give rise to novel coloring paradigms. Our algorithms involve matchings and multicolored alternating cycles, combined with detailed potential and averaging analysis.

Abstract We examine a heuristic to approximate various reliability‐related parameters of communications networks under link failures. The heuristic is based on Monte Carlo and Markov chain simulation techniques. (These techniques have emerged in recent years in theoretical computer science in the context of obtaining efficient approximations forNP‐hard combinatorial optimization problems.) We present the ideas of these Monte Carlo and Markov chain techniques in terms of a specific reliability measure. The general method could be applicable to other reliability measures, just as it has been applied to other combinatorial problems. We present initial experimental results that suggest our approach is typically efficient in the computational complexity sense (running in time polynomial the size of the input); furthermore, our results suggest practical applicability for medium‐size networks and single‐edge parameters. As an example, we present the results of our experiments on a network that was posed for analysis by Applied Research at Bellcore: We estimated all single‐edge parameters on a single DEC‐5000 in less than 4 hours. The software that supported our experiments involves approximately 3000 lines of C code and is easy to adapt to other applications.

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut.This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem.If k is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal.Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.1

A direct combinatorial argument is given to bound the convergence rate of Markov chains in terms of their conductance (these are statements of the nature 'random walks on expanders converge fast'). In addition to showing that the linear algebra in previous arguments for such results on time-reversible Markov chains was unnecessary, the direct analysis applies to general irreversible Markov chains.>

Randomized algorithms for approximating the number of perfect matchings in a graph are considered. An algorithm that is a natural simplification of one suggested and analyzed previously is introduced and analyzed. One of the key ideas is to view the analysis from a geometric perspective: it is proved that for any graph G the k-slice of the well-known Edmonds matching polytope has magnification 1. For a bipartite graph G=(U, V, E), mod U mod = mod V mod =n, with d edge-disjoint perfect matchings, it is proved that the ratio of the number of almost perfect matchings to the number of perfect matchings is at most n/sup 3n/d/. For any constant alpha >0 this yields a a fully polynomial randomized algorithm for approximating the number of perfect matchings in bipartite graphs with d>or= alpha n. Moreover, for some constant c>0 it is the fastest known approximation algorithm for bipartite graphs with d>or= clog n.>