A central feature of many deliberative processes, such as citizens' assemblies and deliberative polls, is the opportunity for participants to engage directly with experts. While participants are typically invited to propose questions for expert panels, only a limited number can be selected due to time constraints. This raises the challenge of how to choose a small set of questions that best represent the interests of all participants. We introduce an auditing framework for measuring the level of representation provided by a slate of questions, based on the social choice concept known as justified representation (JR). We present the first algorithms for auditing JR in the general utility setting, with our most efficient algorithm achieving a runtime of $O(mn\log n)$, where $n$ is the number of participants and $m$ is the number of proposed questions. We apply our auditing methods to historical deliberations, comparing the representativeness of (a) the actual questions posed to the expert panel (chosen by a moderator), (b) participants' questions chosen via integer linear programming, (c) summary questions generated by large language models (LLMs). Our results highlight both the promise and current limitations of LLMs in supporting deliberative processes. By integrating our methods into an online deliberation platform that has been used for over hundreds of deliberations across more than 50 countries, we make it easy for practitioners to audit and improve representation in future deliberations.

Participatory budgeting is a popular method to engage residents in budgeting decisions by local governments. The AnonPB Platform is an online platform that has been used to engage residents in more than 150 budgeting processes. We present a data set with anonymized budget opinions from these processes with K-approval, K-ranking or knapsack primary ballots. For a subset of the voters, it includes paired votes with a different elicitation method in the same process. This presents a unique data set, as the voters, projects and setting are all related to real-world decisions that the voters have an actual interest in. With data from primary ballots we find that while ballot complexity (number of projects to choose from, number of projects to select and ballot length) is correlated with a higher median time spent by voters, it is not correlated with a higher abandonment rate. We use vote pairs with different voting methods to analyze the effect of voting methods on the cost of selected projects, more comprehensively than was previously possible. In most elections, voters selected significantly more expensive projects using K-approval than using knapsack, although we also find a small number of examples with a significant effect in the opposite direction. This effect happens at the aggregate level as well as for individual voters, and is influenced both by the implicit constraints of the voting method and the explicit constraints of the voting interface. Finally, we validate the use of K-ranking elicitation to offer a paper alternative for knapsack voting.

How can we order transactions in a replicated state machine "fairly?" In the model of prior work [2, 8, 9, 13], each of n replicas observes transactions in a different order, and the system aggregates these observed orderings into a single order. We argue that this problem is best viewed through the lens of the classic preference aggregation problem of social choice theory, in which rankings on candidates are aggregated into an election result.

Batch auctions are a classical market microstructure, acclaimed for their fairness properties, and have received renewed interest in the context of blockchain-based financial systems. Constant function market makers (CFMMs) are another market design innovation praised for their computational simplicity. Liquidity provision in batch exchanges is an important problem, and CFMMs have recently shown promise in being useful within batch exchanges. Different real-world implementations have used fundamentally different approaches towards integrating CFMMs in batch exchanges, and there is a lack of formal understanding of the trade-offs of different design choices.

We study low sample complexity mechanisms in participatory budgeting (PB), where each voter votes for a preferred allocation of funds to various projects, subject to project costs and total spending constraints. We analyse the distortion that PB mechanisms introduce relative to the minimum-social-cost outcome in expectation. The Random Dictator mechanism for this problem obtains a distortion of 2. In a special case where every voter votes for exactly one project, [Fain et al., 2017] obtain a distortion of 4/3. We show that when PB outcomes are determined as any convex combination of the votes of two voters, the distortion is 2. When three uniformly randomly sampled votes are used, we give a PB mechanism that obtains a distortion of at most 1.66, thus breaking the barrier of 2 with the smallest possible sample complexity. We give a randomized Nash bargaining scheme where two uniformly randomly chosen voters bargain with the disagreement point as the vote of a voter chosen uniformly at random. This mechanism has a distortion of at most 1.66. We provide a lower bound of 1.38 for the distortion of this scheme. Further, we show that PB mechanisms that output a median of the votes of three voters chosen uniformly at random, have a distortion of at most 1.80.

Constant Function Market Makers (CFMMs) are a tool for creating exchange markets, have been deployed effectively in prediction markets, and are now especially prominent in the Decentralized Finance ecosystem. We show that for any set of beliefs about future asset prices, an optimal CFMM trading function exists that maximizes the fraction of trades that a CFMM can settle. We formulate a convex program to compute this optimal trading function. This program, therefore, gives a tractable framework for market-makers to compile their belief function on the future prices of the underlying assets into the trading function of a maximally capital-efficient CFMM. Our convex optimization framework further extends to capture the tradeoffs between fee revenue, arbitrage loss, and opportunity costs of liquidity providers. Analyzing the program shows how the consideration of profit and loss leads to a qualitatively different optimal trading function. Our model additionally explains the diversity of CFMM designs that appear in practice. We show that careful analysis of our convex program enables inference of a market-maker's beliefs about future asset prices, and show that these beliefs mirror the folklore intuition for several widely used CFMMs. Developing the program requires a new notion of the liquidity of a CFMM, and the core technical challenge is in the analysis of the KKT conditions of an optimization over an infinite-dimensional Banach space.

We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce {\emph diversity constraints} on the items they are allocated. We motivate this via settings where the items themselves correspond to user ad slots or task workers with attributes such as race and gender on which the principal seeks to achieve demographic parity. We consider the following question: When an agent expresses diversity constraints into an allocation rule, is the allocation of other agents hurt significantly? If this happens, the cost of introducing such constraints is disproportionately borne by agents who do not benefit from diversity. We codify this via two desiderata capturing {\em robustness}. These are {\emph no negative externality} -- other agents are not hurt -- and {\emph monotonicity} -- the agent enforcing the constraint does not see a large increase in value. We show in a formal sense that the Nash Welfare rule that maximizes product of agent values is {\emph uniquely} positioned to be robust when diversity constraints are introduced, while almost all other natural allocation rules fail this criterion. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules. We finally perform an empirical simulation on real-world data that models ad allocations to show that this gap between Nash Welfare and other rules persists in the wild.

To improve transaction rates, many cryptocurrencies have implemented so-called "Layer-2" transaction protocols, where payments are routed across networks of private payment channels. However, for a given transaction, not every network state provides a feasible route to perform the payment; in this case, the transaction must be put on the public ledger. The payment channel network thus multiplies the transaction rate of the overall system; the less frequently it fails, the higher the multiplier.

In order to scale transaction rates for deployment across the global web, many cryptocurrencies have deployed so-called ”Layer-2” networks of private payment channels. An idealized payment network behaves like a Credit Network, a model for transactions across a network of bilateral trust relationships. Credit Networks capture many aspects of traditional currencies as well as new virtual currencies and payment mechanisms. In the traditional credit network model, if an agent defaults, every other node that trusted it is vulnerable to loss. In a cryptocurrency context, trust is manufactured by capital deposits, and thus there arises a natural tradeoff between network liquidity (i.e. the fraction of transactions that succeed) and the cost of capital deposits.

We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize Distortion, the worst case social cost of an ordinal mechanism relative to underlying cardinal utilities. We consider two additional desiderata: Constant sample complexity and Squared Distortion. Constant sample complexity means that the mechanism (potentially randomized) only uses a constant number of ordinal queries regardless of the number of voters and alternatives. Squared Distortion is a measure of variance of the Distortion of a randomized mechanism.Our primary contribution is the first social choice mechanism with constant sample complexity and constant Squared Distortion (which also implies constant Distortion). We call the mechanism Random Referee, because it uses a random agent to compare two alternatives that are the favorites of two other random agents. We prove that the use of a comparison query is necessary: no mechanism that only elicits the top-k preferred alternatives of voters (for constant k) can have Squared Distortion that is sublinear in the number of alternatives. We also prove that unlike any top-k only mechanism, the Distortion of Random Referee meaningfully improves on benign metric spaces, using the Euclidean plane as a canonical example. Finally, among top-1 only mechanisms, we introduce Random Oligarchy. The mechanism asks just 3 queries and is essentially optimal among the class of such mechanisms with respect to Distortion.In summary, we demonstrate the surprising power of constant sample complexity mechanisms generally, and just three random voters in particular, to provide some of the best known results in the implicit utilitarian framework.

Elections and opinion polls often have many candidates, with the aim to either rank the candidates or identify a small set of winners according to voters’ preferences. In practice, voters do not provide a full ranking; instead, each voter provides their favorite K candidates, potentially in ranked order. The election organizer must choose K and an aggregation rule. We provide a theoretical framework to make these choices. Each K-Approval or K-partial ranking mechanism (with a corresponding positional scoring rule) induces a learning rate for the speed at which the election recovers the asymptotic outcome. Given the voter choice distribution, the election planner can thus identify the rate optimal mechanism. Earlier work in this area provides coarse order-of-magnitude guaranties which are not sufficient to make such choices. Our framework further resolves questions of when randomizing between multiple mechanisms may improve learning for arbitrary voter noise models. Finally, we use data from 5 large participatory budgeting elections that we organized across several US cities, along with other ranking data, to demonstrate the utility of our methods. In particular, we find that historically such elections have set K too low and that picking the right mechanism can be the difference between identifying the ultimate winner with only a 80% probability or a 99.9% probability after 400 voters.

Measuring the distances between vertices on graphs is one of the most fundamental components in network analysis. Since finding shortest paths requires traversing the graph, it is challenging to obtain distance information on large graphs very quickly. In this work, we present a preprocessing algorithm that is able to create landmark based distance sketches efficiently, with strong theoretical guarantees. When evaluated on a diverse set of social and information networks, our algorithm significantly improves over existing approaches by reducing the number of landmarks stored, preprocessing time, or stretch of the estimated distances.

Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a algorithm called Iterative Local Voting for collective decision-making in this setting. In this algorithm, voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm, with the size of the ball shrinking at a specified rate. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to Pareto optimal solutions with desirable fairness properties in certain natural settings: when the voters' utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution.We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 2,000 workers, employing neighborhoods defined by various L-Norm balls. We make several observations that inform future implementations of such a procedure.

We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternatives. Social choice rules have access to only the ordinal preferences of agents but not the latent cardinal costs that induce them. Distortion is then defined as the ratio between the social cost (typically the sum of agent costs) of the alternative chosen by the mechanism at hand, and that of the optimal alternative chosen by an omniscient algorithm. The worst-case distortion of a social choice rule is, therefore, a measure of how close it always gets to the optimal alternative without any knowledge of the underlying costs. Under this model, it has been conjectured that Ranked Pairs, the well-known weighted-tournament rule, achieves a distortion of at most 3 (Anshelevich et al. 2015). We disprove this conjecture by constructing a sequence of instances which shows that the worst-case distortion of Ranked Pairs is at least 5. Our lower bound on the worst-case distortion of Ranked Pairs matches a previously known upper bound for the Copeland rule, proving that in the worst case, the simpler Copeland rule is at least as good as Ranked Pairs. And as long as we are limited to (weighted or unweighted) tournament rules, we demonstrate that randomization cannot help achieve an expected worst-case distortion of less than 3. Using the concept of approximate majorization within the distortion framework, we prove that Copeland and Randomized Dictatorship achieve low constant factor fairness-ratios (5 and 3 respectively), which is a considerable generalization of similar results for the sum of costs and single largest cost objectives. In addition to all of the above, we outline several interesting directions for further research in this space.

Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a meta-algorithm called Iterative Local Voting for collective decision-making in this setting, in which voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm. In general, such schemes do not converge, or, when they do, the resulting solution does not have a natural description.

Finding similar user pairs is a fundamental task in social networks, with numerous applications in ranking and personalization tasks such as link prediction and tie strength detection. A common manifestation of user similarity is based upon network structure: each user is represented by a vector that represents the user's network connections, where pairwise cosine similarity among these vectors defines user similarity. The predominant task for user similarity applications is to discover all similar pairs that have a pairwise cosine similarity value larger than a given threshold τ. In contrast to previous work where τ is assumed to be quite close to 1, we focus on recommendation applications where τ is small, but still meaningful. The all pairs cosine similarity problem is computationally challenging on networks with billions of edges, and especially so for settings with small τ. To the best of our knowledge, there is no practical solution for computing all user pairs with, say τ = 0.2 on large social networks, even using the power of distributed algorithms.

We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our algorithms are natural dynamic versions of two known local variations of power iteration. One, Forward Push, propagates probability mass forwards along edges from a source node, while the other, Reverse Push, propagates local changes backwards along edges from a target. In both variations, we maintain an invariant between two vectors, and when an edge is updated, our algorithm first modifies the vectors to restore the invariant, then performs any needed local push operations to restore accuracy.

Though deliberation is a critical component of democratic decision-making, existing deliberative processes do not scale to large groups of people. Motivated by this, we propose a model in which large-scale decision-making takes place through a sequence of small group interactions. Our model considers a group of participants, each having an opinion which together form a graph. We show that for median graphs, a class of graphs including grids and trees, it is possible to use a small number of three-person interactions to tightly approximate the wisdom of the crowd, defined here to be the generalized median of participant opinions, even when agents are strategic. Interestingly, we also show that this sharply contrasts with small groups of size two, for which we prove an impossibility result. Specifically, we show that it is impossible to use sequences of two-person interactions satisfying natural axioms to find a tight approximation of the generalized median, even when agents are non-strategic. Our results demonstrate the potential of small group interactions for reaching global decision-making properties.

We present new algorithms for Personalized PageRank estimation and Personalized PageRank search. First, for the problem of estimating Personalized PageRank (PPR) from a source distribution to a target node, we present a new bidirectional estimator with simple yet strong guarantees on correctness and performance, and 3x to 8x speedup over existing estimators in experiments on a diverse set of networks. Moreover, it has a clean algebraic structure which enables it to be used as a primitive for the Personalized PageRank Search problem: Given a network like Facebook, a query like "people named John," and a searching user, return the top nodes in the network ranked by PPR from the perspective of the searching user. Previous solutions either score all nodes or score candidate nodes one at a time, which is prohibitively slow for large candidate sets. We develop a new algorithm based on our bidirectional PPR estimator which identifies the most relevant results by sampling candidates based on their PPR; this is the first solution to PPR search that can find the best results without iterating through the set of all candidate results. Finally, by combining PPR sampling with sequential PPR estimation and Monte Carlo, we develop practical algorithms for PPR search, and we show via experiments that our algorithms are efficient on networks with billions of edges.

Recent work has highlighted credit networks as an effective mechanism for modeling trust in a network: agents issue their own currency and trust each other for a certain amount of each other's currency, allowing two nodes to transact if there is a chain of sufficient residual trust between them. Under a natural model of repeated transactions, the probability that two agents can successfully transact in a credit network (i.e. the liquidity between these two agents) is the same as the probability that they are connected to each other in a uniformly random forest of the network. Motivated by this connection, we define the RF-connectivity between a pair of nodes in a graph G as the probability that the two nodes belong to the same connected component in a uniformly random forest of G. Our first result is that for an arbitrary subset S of nodes in G, the average RF-connectivity between pairs of nodes in S is at least 1–2/h(GS), where h(GS) is the edge expansion of the subgraph GS induced by S. Informally, this implies that a well-connected “community” of nodes S in a credit network will have high liquidity among themselves, regardless of the structure of the remaining network. We extend this result to show that in fact every node in S has good average RF-connectivity to other nodes in S whenever S has good edge expansion. We also show that our results are nearly tight by proving an upper bound on the liquidity of regular graphs. For our motivating application, it is important that we relate the average RF-connectivity in S to the expansion inside S and not merely to expansion of G since we would like to assert that a well-connected community has high liquidity even if the graph as a whole is not well-connected. This naturally leads to a monotonicity conjecture: the RF-connectivity of two nodes can not decrease when a new edge is added to G. We show that the monotonicity conjecture is equivalent to showing negative correlation between inclusion of any two edges in a random forest, a long-standing open problem. Our result about the average RF-connectivity of nodes in S may be viewed as establishing a weak version of the monotonicity conjecture.

Credit networks are an abstraction for modeling trust among agents in a network. Agents who do not directly trust each other can transact through exchange of IOUs (obligations) along a chain of trust in the network. Credit networks are robust to intrusion, can enable transactions between strangers in exchange economies, and have the liquidity to support a high rate of transactions. We study the formation of such networks when agents strategically decide how much credit to extend each other. We find strong positive network formation results for the simplest theoretical model. When each agent trusts a fixed set of other agents and transacts directly only with those it trusts, all pure-strategy Nash equilibria are social optima. However, when we allow transactions over longer paths, the price of anarchy may be unbounded. On the positive side, when agents have a shared belief about the trustworthiness of each agent, simple greedy dynamics quickly converge to a star-shaped network, which is a social optimum. Similar star-like structures are found in equilibria of heuristic strategies found via simulation studies. In addition, we simulate environments where agents may have varying information about each others’ trustworthiness based on their distance in a social network. Empirical game analysis of these scenarios suggests that star structures arise only when defaults are relatively rare, and otherwise, credit tends to be issued over short social distances conforming to the locality of information. Overall, we find that networks formed by self-interested agents achieve a high fraction of available value, as long as this potential value is large enough to enable any network to form.

We present theoretical and empirical results demonstrating the usefulness of social choice functions in crowdsourcing for participatory democracies. First, we demonstrate the scalability of social choice functions by defining a natural notion of epsilon-approximation, and giving algorithms which efficiently elicit such approximations for two prominent social choice functions: the Borda rule and the Condorcet winner. This result circumvents previous prohibitive lower bounds and is surprisingly strong: even if the number of ideas is as large as the number of participants, each participant will only have to make a logarithmic number of comparisons, an exponential improvement over the linear number of comparisons previously needed. Second, we apply these ideas to Finland's recent off-road traffic law reform, an experiment on participatory democracy in real life. This allows us to verify the scaling predicted in our theory and show that the constant involved is also not large. In addition, by collecting data on the time that users take to complete rankings of varying sizes, we observe that eliciting partial rankings can further decrease elicitation time as compared to the common method of eliciting pairwise comparisons.

We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s(t) from s to t, guaranteeing that the relative error is small as long πs(t) > δ. Existing algorithms for this problem have a running-time of Ω(1/δ in comparison, FAST-PPR has a provable average running-time guarantee of O(√d/δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O(1/n) (where n is the number of nodes) for applications. We also complement the algorithm with an Ω(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved.

An essential primitive for an efficient research ecosystem is partial-progress sharing (PPS) -- whereby a researcher shares information immediately upon making a breakthrough. This helps prevent duplication of work; however there is evidence that existing reward structures in research discourage partial-progress sharing. Ensuring PPS is especially important for new online collaborative-research platforms, which involve many researchers working on large, multi-stage problems.

A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naïve linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

We analyze several distributed, continuous time protocols for a fair allocation of bandwidths to flows in a network (or resources to agents). Our protocols converge to an allocation that is a logarithmic approximation, simultaneously, to all canonical social welfare functions (i.e., functions that are symmetric, concave, and nondecreasing). These protocols can be started in an arbitrary state. Although a similar protocol was known before, it only applied to the simple bandwidth allocation problem, and its stability and convergence time were not understood. In contrast, our protocols also apply to the more general case of Leontief utilities, where each user may place a different requirement on each resource. Furthermore, we prove that our protocols converge in polynomial time. The best convergence time we prove is O ( n log nc MAX a MAX / c MIN a MIN ), where n is the number of agents in the network, c MAX and c MIN are the maximum and minimum capacity of the links, and a max , a min are respectively the largest and smallest Leontief coefficients. This time is achieved by a simple Multiplicative Increase, Multiplicative Decrease (MIMD) protocol that had not been studied before in this setting. We also identify combinatorial properties of these protocols that may be useful in proving stronger convergence bounds. The final allocations by our protocols are supported by usage-sensitive dual prices that are fair in the sense that they shield light users of a resource from the impact of heavy users. Thus, our protocols can also be thought of as efficient distributed schemes for computing fair prices.

WTF ("Who to Follow") is Twitter's user recommendation service, which is responsible for creating millions of connections daily between users based on shared interests, common connections, and other related factors. This paper provides an architectural overview and shares lessons we learned in building and running the service over the past few years. Particularly noteworthy was our design decision to process the entire Twitter graph in memory on a single server, which significantly reduced architectural complexity and allowed us to develop and deploy the service in only a few months. At the core of our architecture is Cassovary, an open-source in-memory graph processing engine we built from scratch for WTF. Besides powering Twitter's user recommendations, Cassovary is also used for search, discovery, promoted products, and other services as well. We describe and evaluate a few graph recommendation algorithms implemented in Cassovary, including a novel approach based on a combination of random walks and SALSA. Looking into the future, we revisit the design of our architecture and comment on its limitations, which are presently being addressed in a second-generation system under development.

In this paper we consider the well-studied problem of finding a perfect matching in a $d$-regular bipartite graph on $2n$ nodes with $m=nd$ edges. The best known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time $O(m\sqrt{n})$. In regular bipartite graphs, however, a matching is known to be computable in $O(m)$ time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the $O(m)$ time bound was improved first to $\tilde O\left(\min\{m, n^{2.5}/d\}\right)$ and then to $\tilde O\left(\min\{m, n^2/d\}\right)$. In this paper, we give a randomized algorithm that finds a perfect matching in a $d$-regular graph and runs in $O(n\log n)$ time (both in expectation and with high probability). The algorithm performs an appropriately truncated alternating random walk to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (nonadaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time $O(n\log^2 n)$, with $O(m)$ preprocessing time; this gives a simple $O(m+mn\log^2 n)$ time algorithm for finding the Birkhoff--von Neumann decomposition of a doubly stochastic matrix. We show that randomization is crucial for obtaining $o(nd)$ time algorithms by establishing an $\Omega(nd)$ lower bound for deterministic algorithms. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes $o(n\log n)$ time with high probability.

Distributed frameworks are gaining increasingly widespread use in applications that process large amounts of data. One important example application is large scale similarity search, for which Locality Sensitive Hashing (LSH) has emerged as the method of choice, specially when the data is high-dimensional. To guarantee high search quality, the LSH scheme needs a rather large number of hash tables. This entails a large space requirement, and in the distributed setting, with each query requiring a network call per hash bucket look up, also a big network load. Panigrahy's Entropy LSH scheme significantly reduces the space requirement but does not help with (and in fact worsens) the search network efficiency. In this paper, focusing on the Euclidian space under ι2 norm and building up on Entropy LSH, we propose the distributed Layered LSH scheme, and prove that it exponentially decreases the network cost, while maintaining a good load balance between different machines. Our experiments also verify that our theoretical results.

Consider the following communication problem. Alice holds a graph GA = (P, Q, EA) and Bob holds a graph GB = (P, Q, EB), where |P| = |Q| = n. Alice is allowed to send Bob a message m that depends only on the graph GA. Bob must then output a matching M ⊆ EA ∪ EB. What is the minimum message size of the message m that Alice sends to Bob that allows Bob to recover a matching of size at least (1 − ∊) times the maximum matching in GA ∪ GB? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a (1 − ∊)-approximate bipartite matching. The focus of this work is to understand one-round communication complexity and one-pass streaming complexity of maximum bipartite matching. In particular, how well can one approximate these problems with linear communication and space? Prior to our work, only a ½-approximation was known for both these problems. In order to study these questions, we introduce the concept of an ∊-matching cover of a bipartite graph G, which is a sparse subgraph of the original graph that preserves the size of maximum matching between every subset of vertices to within an additive en error. We give a polynomial time construction of a ½-matching cover of size O(n) with some crucial additional properties, thereby showing that Alice and Bob can achieve a ⅔-approximation with a message of size O(n). While we do not provide bounds on the size of ∊-matching covers for ∊ < 1/2, we prove that in general, the size of the smallest ∊-matching cover of a graph G on n vertices is essentially equal to the size of the largest so-called ∊-Ruzsa Szemerédi graph on n vertices. We use this connection to show that for any δ > 0, a (⅔ + δ)-approximation requires a communication complexity of n1+Ω(1/ log log n). We also consider the natural restrictingon of the problem in which GA and GB are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a ¾ -approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation. Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated (1 − 1/ε)-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem [12]. We present here the first deterministic one-pass streaming (1 − 1/ε)-approximation algorithm using O(n) space for this setting.

Test cost is increasingly becoming a major component of a product's design cost in scaled technologies. Exponential increase in test data volumes for sub-45 designs, especially for testing delay faults has led to large increase in ATE cost and test application time. In order to reduce external test cost, Logic BIST has been explored as a possible alternative to manufacturing test [1-5]. However, this paper shows that a large number of faults in BIST logic of large IWLS'05 and ITC'99 benchmark processors remain undetected after BIST run (42% of stuck-at and 34% of transition faults on average) and thus, BIST logic needs to be tested properly. This paper proposes a hierarchical BIST methodology `HBIST' which uses different BIST techniques to obtain complete stuck-at and transition fault coverage of CUT and then introduces additional levels of BIST logic to test for faults in the BIST logic at the preceding levels. A design methodology is proposed to optimize the number of additional levels of BIST required while keeping the BIST area and power overhead, and the addition of extra faults in BIST logic minimal. Experiments on large benchmarks show an average of 95.9% CUT stuck-at fault coverage (ATPG coverage of 96.4%) and 93.5% CUT transition fault coverage (ATPG coverage of 95.3%) is obtained using HBIST. Also, up to 99.2% (average 93.2%) reduction in external ATE test cost (including cost needed to test additional BIST levels) is obtained using two levels of BIST at 7% average area overhead (compared to scan overhead of 38.2%) and 18% increase in test power.

To answer search queries on a social network rich with user-generated content, it is desirable to give a higher ranking to content that is closer to the individual issuing the query. Queries occur at nodes in the network, documents are also created by nodes in the same network, and the goal is to find the document that matches the query and is closest in network distance to the node issuing the query. In this paper, we present the "Partitioned Multi-Indexing" scheme, which provides an approximate solution to this problem. With m links in the network, after an offline ~O(m) pre-processing time, our scheme allows for social index operations (i.e., social search queries, as well as insertion and deletion of words into and from a document at any node), all in time ~O(1). Further, our scheme can be implemented on open source distributed streaming systems such as Yahoo! S4 or Twitter's Storm so that every social index operation takes ~O(1) processing time and network queries in the worst case, and just two network queries in the common case where the reverse index corresponding to the query keyword is much smaller than the memory available at any distributed compute node. Building on Das Sarma et al.'s approximate distance oracle, the worst-case approximation ratio of our scheme is ~O(1) for undirected networks. Our simulations on the social network Twitter as well as synthetic networks show that in practice, the approximation ratio is actually close to 1 for both directed and undirected networks. We believe that this work is the first demonstration of the feasibility of social search with real-time text updates at large scales.

Credit networks are an abstraction for modeling trust between agents in a network. Agents who do not directly trust each other can transact through exchange of IOUs (obligations) along a chain of trust in the network. Credit networks are robust to intrusion, can enable transactions between strangers in exchange economies, and have the liquidity to support a high rate of transactions. We study the formation of such networks when agents strategically decide how much credit to extend each other. When each agent trusts a fixed set of other agents, and transacts directly only with those it trusts, the formation game is a potential game and all Nash equilibria are social optima. Moreover, the Nash equilibria of this game are equivalent in a very strong sense: the sequences of transactions that can be supported from each equilibrium credit network are identical. When we allow transactions over longer paths, the game may not admit a Nash equilibrium, and even when it does, the price of anarchy may be unbounded. Hence, we study two special cases. First, when agents have a shared belief about the trustworthiness of each agent, the networks formed in equilibrium have a star-like structure. Though the price of anarchy is unbounded, myopic best response quickly converges to a social optimum. Similar star-like structures are found in equilibria of heuristic strategies found via simulation. In addition, we simulate a second case where agents may have varying information about each others' trustworthiness based on their distance in a social network. Empirical game analysis of these scenarios suggests that star structures arise only when defaults are relatively rare, and otherwise, credit tends to be issued over short social distances conforming to the locality of information.

Design objectives of robustness and low-power usually do not go hand in hand with the test objectives of maximum test coverage and minimum test cost. Low power robust design techniques such as dual-Vth, dual-VDD, or adaptive body biasing have negative impact on the associated test cost. Similarly, test techniques like enhanced scan have large overhead in terms of area and power. In this paper, we try to mitigate the conflicting design and test requirements using an integrated approach to design and test that utilizes the existing low power and error resilient design techniques and augments them to improve test coverage and cost. Simulation results on an example 8×8 Wallace tree multiplier in 90nm technology node show 20% reduction in operating power, 60% reduction in test power and 99% reduction in critical paths while at the same time improving the yield from 96% to 100%, compared to existing design and test methodologies. All this comes at the cost of a marginal increase in area (7.8%).

Credit networks represent a way of modeling trust between entities in a network. Nodes in the network print their own currency and trust each other for a certain amount of each other's currency. This allows the network to serve as a decentralized payment infrastructure---arbitrary payments can be routed through the network by passing IOUs between trusting nodes in their respective currencies---and obviates the need for a common currency. Nodes can repeatedly transact with each other and pay for the transaction using trusted currency. A natural question to ask in this setting is: how long can the network sustain liquidity, i.e. how long can the network support the routing of payments before credit dries up? We answer this question in terms of the long term failure probability of transactions for various network topologies and credit values.

In the stochastic knapsack problem, we are given a set of items each associated with a probability distribution on sizes and a profit, and a knapsack of unit capacity. The size of an item is revealed as soon as it is inserted into the knapsack, and the goal is to design a policy that maximizes the expected profit of items that are successfully inserted into the knapsack. The stochastic knapsack problem is a natural generalization of the classical knapsack problem, and arises in many applications, including bandwidth allocation, budgeted learning, and scheduling. An adaptive policy for stochastic knapsack specifies the next item to be inserted based on observed sizes of the items inserted thus far. The adaptive policy can have an exponentially large explicit description and is known to be PSPACE-hard to compute. The best known approximation for this problem is a (3 + ∊)-approximation for any ∊ > 0. Our first main result is a relaxed PTAS (Polynomial Time Approximation Scheme) for the adaptive policy, that is, for any ∊ > 0, we present a poly-time computable (1 + ∊)-approximate adaptive policy when knapsack capacity is relaxed to 1+e. At a high-level, the proof is based on transforming an arbitrary collection of item size distributions to canonical item size distributions that admit a compact description. We then establish a coupling that shows a (1 + ∊)-approximation can be achieved for the original problem by a canonical policy that makes decisions at each step by observing events drawn from the sample space of canonical size distributions. Finally, we give a mechanism for approximating the optimal canonical policy. Our second main result is an (8/3 + ∊)-approximate adaptive policy for any ∊ > 0 without relaxing the knapsack capacity, improving the earlier (3 + ∊)-approximation result. Interestingly, we obtain this result by using the PTAS described above. We establish an existential result that the optimal policy for the knapsack with capacity 1 can be folded to get a policy with expected profit 3OPT/8 for a knapsack with capacity (1 − ∊), with capacity relaxed to 1 only for the first item inserted. We then use our PTAS result to compute the (1 + ∊)-approximation to such policy. Our techniques also yield a relaxed PTAS for non-adaptive policies. Finally, we also show that our ideas can be extended to yield improved approximation guarantees for multi-dimensional and fixed set variants of the stochastic knapsack problem.

This paper presents memory-based embedded digital ATE (Automatic Test Equipment) - a new logic BIST methodology that can deliver deterministic test stimuli and stores output responses on a chip. The proposed scheme consists of test data compression logic and a new on-chip SRAM structure, which is operated as a ROM when the logic BIST mode is on. The new BIST-oriented RAM (BRAM) implements ROM features in the BIST mode and incurs no performance penalty in the normal SRAM mode of operation. BRAM can be designed by inserting an additional word line in a row to a conventional SRAM bit-cell (no increase in bit-cell area). BRAM stores the compressed test vectors that can be transmitted to on-chip decompressors during test mode. BRAM also accepts compacted output responses. Experimental results show that BRAM performs stable and high-performance ROM operations in the BIST mode. Run-length coding can be incorporated into the proposed test data compression to reduce test data volume further. Test data volume and fault coverage on ISCAS89 benchmark show that the proposed test methodology can be used as a stand-alone BIST scheme while providing test quality of deterministic tests.

We propose a read-disturb-free, 1-read/1-write port, 8-transistor (8T) bitcell utilizing differential sensing. The conflicting design requirement of read versus write operation in a conventional 6T SRAM bitcell is eliminated using separate read/write access transistors. A distributed read-access transistor shared across the bitcells of every row enables read-disturb-free differential sensing operation with eight transistors per bitcell. Write-access transistors are upsized to form a diffusion-notch-free layout which would result in improved manufacturability. 1R/1W port nature of the proposed 8T bitcell makes it an attractive choice for the high speed, dense register file (RF) designs. Bitcell failure measurements on 20 test-chips fabricated in 90-nm CMOS technology demonstrate that the proposed differential 8T bitcell shows 220 mV lower read-Vmin, 40 mV lower hold-Vmin, 25 mV higher weak-write voltage compared to the iso-area 6T bitcell at iso-performance. At 600 mV, the proposed 8T bitcell array operates up to 67.2 MHz.

We study the single-sink buy-at-bulk problem with an unknown cost function. We wish to route flow from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, non-decreasing function f satisfying f(0)=0. We present a simple, fast, combinatorial algorithm that takes a set of demands and constructs a single tree T such that for all f the cost f(T) is a 47.45-approximation of the optimal cost for that f. This is within a factor of 2.33 of the best approximation ratio currently achievable when the tree can be optimized for a specific function. Trees achieving simultaneous O(1)-approximations for all concave functions were previously not known to exist regardless of computation time.

Associative memories offer high levels of parallelism in matching a query against stored entries. We design and analyze an architecture which uses single lookup into a Ternary Content Addressable Memory (TCAM) to solve the subset query problem for small sets, i.e., to check whether a given set (the query) contains (or alternately, is contained in) any one of a large collection of sets in a database. We use each TCAM entry as a small Ternary Bloom Filter (each 'bit' of which is one of {0,1,wildcard}) to store one of the sets in the collection. Like Bloom filters, our architecture is susceptible to false positives. Since each TCAM entry is quite small, asymptotic analyses of Bloom filters do not directly apply. Surprisingly, we are able to show that the asymptotic false positive probability formula can be safely used if we penalize the small Bloom filter by taking away just one bit of storage and adding just half an extra set element before applying the formula. We believe that this analysis is independently interesting. The subset query problem has applications in databases, network intrusion detection, packet classification in Internet routers, and Information Retrieval. We demonstrate our architecture on one illustrative streaming application -- intrusion detection in network traffic. Be shingling (i.e., taking consecutive bytes of) the strings in the database, we can perform a single subset query and hence a single TCAM search, to skip many bytes in the stream. We evaluate our scheme on the open source CLAM anti-virus database, for worst-case as well as random streams. Our architecture appears to be at least one order of magnitude faster than previous approaches. Since the individual Bloom filters must fit in a single TCAM entry (currently 72 to 576 bits), our solution applies only when each set is of a small cardinality. However, this is sufficient for many typical applications. Also, recent algorithms for the subset-query problem use a small-set version as a subroutine

Similarity search methods are widely used as kernels in various data mining and machine learning applications including those in computational biology, web search/clustering. Nearest neighbor search (NNS) algorithms are often used to retrieve similar entries, given a query. While there exist efficient techniques for exact query lookup using hashing, similarity search using exact nearest neighbors suffers from a "curse of dimensionality", i.e. for high dimensional spaces, best known solutions offer little improvement over brute force search and thus are unsuitable for large scale streaming applications. Fast solutions to the approximate NNS problem include Locality Sensitive Hashing (LSH) based techniques, which need storage polynomial in n with exponent greater than 1, and query time sublinear, but still polynomial in n, where n is the size of the database. In this work we present a new technique of solving the approximate NNS problem in Euclidean space using a Ternary Content Addressable Memory (TCAM), which needs near linear space and has O(1) query time. In fact, this method also works around the best known lower bounds in the cell probe model for the query time using a data structure near linear in the size of the data base.

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m√n). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the O(m) time bound was improved first to ~ O(min m, n2.5/d) and then to ~O(min {m, n2/d\}).

In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on SALSA), on large-scale dynamically evolving social networks. We assume that the graph of friendships is stored in distributed shared memory, as is the case for large social networks such as Twitter. For global PageRank, we assume that the social network has n nodes, and m adversarially chosen edges arrive in a random order. We show that with a reset probability of ε, the expected total work needed to maintain an accurate estimate (using the Monte Carlo method) of the PageRank of every node at all times is [EQUATION]. This is significantly better than all known bounds for incremental PageRank. For instance, if we naively recompute the PageRanks as each edge arrives, the simple power iteration method needs [EQUATION] total time and the Monte Carlo method needs O ( mn /ε) total time; both are prohibitively expensive. We also show that we can handle deletions equally efficiently. We then study the computation of the top k personalized PageRanks starting from a seed node, assuming that personalized PageRanks follow a power-law with exponent α < 1. We show that if we store R > q ln n random walks starting from every node for large enough constant q (using the approach outlined for global PageRank), then the expected number of calls made to the distributed social network database is O ( k /( R (1-α)/α )). We also present experimental results from the social networking site, Twitter, verifying our assumptions and analyses. The overall result is that this algorithm is fast enough for real-time queries over a dynamic social network.

In several systems applications, parameters such as load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of the system optimization and monitoring schemes can be improved by spending resources such as time or bandwidth in observing or resolving the values of these parameters. In a resource-constrained situation, deciding which parameters to observe in order to best optimize the expected system performance (or in general, optimize the expected value of a certain objective function) itself becomes an interesting optimization problem. In this article, we initiate the study of such problems that we term “model-driven optimization”. In particular, we study the problem of optimizing the minimum value in the presence of observable distributions. We show that this problem is NP-Hard, and present greedy algorithms with good performance bounds. The proof of the performance bounds are via novel sub-modularity arguments and connections to covering integer programs.

In this article we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first nontrivial algorithm, with running time O ( mn ), dates back to König's work in 1916 (here m = nd is the number of edges in the graph, 2 n is the number of vertices, and d is the degree of each node). The currently most efficient algorithm takes time O(m) , and is due to Cole et al. [2001]. We improve this running time to O (min{ m , n 2.5 ln n / d }); this minimum can never be larger than O ( n 1.75 √ln n ). We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a d -regular bipartite graph independently with a probability p = O ( n ln n / d 2 ) then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to nonexistence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem [1994a, 1994b] for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the O ( m √ n ) algorithm (due to Hopcroft and Karp [1973]) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to polylogarithmic factors (in fact, up to ln 2 n ).

Spin-torque transfer magnetic RAM (STT MRAM) is a promising candidate for future embedded applications. It combines the desirable attributes of current memory technologies such as SRAM, DRAM, and flash memories (fast access time, low cost, high density, and non-volatility). It also solves the critical drawbacks of conventional MRAM technology: poor scalability and high write current. However, variations in process parameters can lead to a large number of cells to fail, severely affecting the yield of the memory array. In this paper, we analyzed and modeled the failure probabilities of STT MRAM cells due to parameter variations. Based on the model, we performed a thorough analysis of the impact of design parameters on parametric failures due to process variations. To achieve high memory yield without incurring expensive technology modification, we developed an efficient design paradigm from circuit and/or architecture perspective-to improve the robustness and integration density. The proposed technique effectively relaxes or completely decouples the conflicting design requirements for read stability, writability and cell area. It can be used at an early stage of the design cycle for yield enhancement.

Due to their small sizes, SRAMs are particularly vulnerable to parametric failures, resulting in significantly reduced yield. The underlying problem with SRAM is that there are conflicting requirements for read stability and writeability, such that optimizing the cell for read stability degrades its writeability. In this work, we present a circuit-architecture co-design technique that allows the decoupling of these conflicting requirements, resulting in significant yield enhancement at iso-area, while being scalable. Our technique is based on the observation that the write operation is not as performance critical as the read operation in high-performance microprocessors. Thus, the technique skews the cell design towards improving read stability at the circuit level at the expense of writeability. To handle the increased write failures in some dies, we apply simple architectural modifications that allow the write operation to take an additional cycle (stretched write cycle). By using our technique, we can improve yield from 37% to 69%, while having 3.4% performance impact on average, without increasing the size of the SRAM cell.

Spin-Torque Transfer Magnetic RAM (STT MRAM) is a promising candidate for future embedded applications. It provides desirable memory attributes such as fast access time, low cost, high density and non-volatility. However, variations in process parameters can lead to a large number of cells to fail, severely affecting the yield of the memory array. In this paper, we provide a thorough analysis of the impact of design parameters on parametric failures due to process variations. To achieve high memory yield without incurring expensive technology modification, we developed an alternate design paradigm -circuit/architecture co-design - to take advantage of different levels of design hierarchy (circuit and architecture) to improve the yield and memory density. The technique decouples the conflicting design requirements for read stability/writability and density. Consequently, the memory cell failure probability reduces by 48% and cell area reduces by 21% with negligible performance degradation (~0.4%).

We consider the single-source (or single-sink) buy-at-bulk problem with an unknown concave cost function. We want to route a set of demands along a graph to or from a designated root node, and the cost of routing x units of flow along an edge is proportional to some concave, non-decreasing function f such that f(0) = 0. We present a polynomial time algorithm that finds a distribution over trees such that the expected cost of a tree for any f is within an O(1)-factor of the optimum cost for that f. The previous best simultaneous approximation for this problem, even ignoring computation time, was O(log |D|), where D is the multi-set of demand nodes. We design a simple algorithmic framework using the ellipsoid method that finds an O(1)-approximation if one exists, and then construct a separation oracle using a novel adaptation of the Guha, Meyerson, and Munagala algorithm for the single-sink buy-at-bulk problem that proves an O(1) approximation is possible for all f. The number of trees in the support of the distribution constructed by our algorithm is at most 1+log |D|.

We present an incentive-based architecture for providing recommendations in a social network. We maintain a distinct reputation system for each individual and we rely on users to identify appropriate correlations and rate the items using asystem-providedrecommendationlanguage.Thekeyidea is to design an incentive structure and a ranking system such that any inaccuracy in the recommendations implies the existence of a profitable arbitrage opportunity, hence making the system resistant to malicious spam and presentation bias. We also show that, under mild assumptions, our architecture provides users with incentive to minimize the Kullback-Leibler divergence between the ratings and the actual item qualities, quickly driving the system to an equilibrium state with accurate recommendations.

In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to K\{o}nig's work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ is the number of vertices, and $d$ is the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. We improve this running time to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$; this minimum can never be larger than $O(n^{1.75}\sqrt{\ln n})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(\frac{n\ln n}{d^2})$ then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the $O(m\sqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to $\ln^2 n$).

In the budgeted learning problem, we are allowed to experiment on a set of alternatives (given a fixed experimentation budget) with the goal of picking a single alternative with the largest possible expected payoff. Constant factor approximation algorithms for this problem were developed by Guha and Munagala by rounding a linear program that couples the various alternatives together. In this paper we present an index for this problem, which we call the ratio index, which also guarantees a constant factor approximation. Index-based policies have the advantage that a single number (i.e. the index) can be computed for each alternative irrespective of all other alternatives, and the alternative with the highest index is experimented upon. This is analogous to the famous Gittins index for the discounted multi-armed bandit problem. The ratio index has several interesting structural properties. First, we show that it can be computed in strongly polynomial time. Second, we show that with the appropriate discount factor, the Gittins index and our ratio index are constant factor approximations of each other, and hence the Gittins index also gives a constant factor approximation to the budgeted learning problem. Finally, we show that the ratio index can be used to create an index-based policy that achieves an O(1)-approximation for the finite horizon version of the multi-armed bandit problem. Moreover, the policy does not require any knowledge of the horizon (whereas we compare its performance against an optimal strategy that is aware of the horizon). This yields the following surprising result: there is an index-based policy that achieves an O(1)-approximation for the multi-armed bandit problem, oblivious to the underlying discount factor.

Search auctions have become a dominant source of revenue generation on the Internet. Such auctions have typically used per-click bidding and pricing. We propose the use of hybrid auctions where an advertiser can make a per-impression as well as a per-click bid, and the auctioneer then chooses one of the two as the pricing mechanism. We assume that the advertiser and the auctioneer both have separate beliefs (called priors) on the click-probability of an advertisement. We first prove that the hybrid auction is truthful, assuming that the advertisers are risk-neutral. We then show that this auction is superior to the existing per-click auction in multiple ways: 1. We show that risk-seeking advertisers will choose only a per-impression bid whereas risk-averse advertisers will choose only a per-click bid, and argue that both kind of advertisers arise naturally. Hence, the ability to bid in a hybrid fashion is important to account for the risk characteristics of the advertisers. 2. For obscure keywords, the auctioneer is unlikely to have a very sharp prior on the click-probabilities. In such situations, we show that having the extra information from the advertisers in the form of a per-impression bid can result in significantly higher revenue. 3. An advertiser who believes that its click-probability is much higher than the auctioneer's estimate can use per-impression bids to correct the auctioneer's prior without incurring any extra cost. 4. The hybrid auction can allow the advertiser and auctioneer to implement complex dynamic programming strategies to deal with the uncertainty in the click-probability using the same basic auction. The per-click and per-impression bidding schemes can only be used to implement two extreme cases of these strategies. As Internet commerce matures, we need more sophisticated pricing models to exploit all the information held by each of the participants. We believe that hybrid auctions could be an important step in this direction. The hybrid auction easily extends to multiple slots, and is also applicable to scenarios where the hybrid bidding is per-impression and per-action (i.e. CPM and CPA), or per-click and per-action (i.e. CPC and CPA). Copyright is held by the International World Wide Web Conference Committee (IW3C2).

It is important in communication networks to use routes that are as short as possible (i.e have low stretch) while keeping routing tables small. Recent advances in compact routing show that a stretch of 3 can be achieved while maintaining a sub- linear (in the size of the network) space at each node [14]. It is also known that no routing scheme can achieve stretch less than 3 with sub-linear space for arbitrary networks. In contrast, simulations on real-life networks have indicated that stretch less than 3 can indeed be obtained using sub-linear sized routing tables[6]. We further investigate the space-stretch tradeoffs for compact routing by analyzing a specific class of graphs and by presenting an efficient algorithm that (approximately) finds the optimum space-stretch tradeoff for any given network. We first study a popular model of random graphs, known as Bernoulli random graphs or Erds-Renyi graphs, and prove that stretch less than 3 can be obtained in conjunction with sub- linear routing tables. In particular, stretch 2 can be obtained using routing tables that grow roughly as n3/4where n is the number of nodes in the network. Compact routing schemes often involve the selection of landmarks. We present a simple greedy scheme for landmark selection that takes a desired stretch s and a budget L on the number of landmarks as input, and produces a set of at most 0(L logn) landmarks that achieve stretch s. Our scheme produces routing tables that use no more than O(logn) more space than the optimum scheme for achieving stretch s with L landmarks. This may be a valuable tool for obtaining near-optimum stretch-space tradeoffs for specific graphs. We simulate this greedy scheme (and other heuristics) on multiple classes of random graphs as well as on Internet like graphs.

Multicast is a fundamental communication operation in wireless sensor networks whereby a source sensor transmits its information to a relevant subset of sensors in the network. Motivated by this, we study the advantage of network coding for minimizing the total power needed for multicast in wireless networks. We show that there is an absolute constant, depending only on the power gradient and the dimension of the underlying Euclidean space, that bounds the maximum advantage of network coding. An interesting aspect of our result is that it shows that the advantage of coding remains bounded by a constant even when compared to a multicast scheme without coding that is restricted to do only point-to-point transmissions.

In this paper we explore whether a general topology network built up of routers with very small buffers, can maintain high throughput under TCP's congestion control mechanism. Recent results on buffer sizing challenged the widely used assumption that routers should buffer millions of packets. These new results suggest that when smooth TCP traffic goes through a single tiny buffer of size O(log W), then close-to-peak throughput can be achieved; W is the maximum window size of TCP flows. In this work, we want to know if a network of many routers can perform well when all buffers in the network are made very small, independent of the structure of the network. This scenario represents a real network where packets go through several buffering stages on their routes. Assuming the ingress TCP traffic to a network is paced, we first prove that all routers can get by with very small buffers, if the network has a tree structure. For networks with general topology, we propose a simple active queue management policy called bounded jitter policy (BJP), and show that under the proposed policy each flow will preserve its smooth pattern across the network. Logarithmic size buffers would therefore be enough in every router of the network.

A number of algorithms have been proposed in the literature for scheduling CIOQ switches. The algorithms which have been proven to provide strict performance guarantees on delay (via the emulation of an output-queued switch) have been too complicated to implement because they require the exchange of a large amount of information between inputs and outputs. With implementation as our primary focus, we consider scheduling algorithms that are "fully local." This means inputs and outputs must be able to make decisions regarding matchings using only local information (except requests, grants and accepts). This constraint, which is essentially necessary for high-speed implementations, appears too restrictive for designing algorithms which enable the emulation of an output-queued switch. Rather surprisingly, we find a very simple and fully local algorithm FLGS (for fully local Gale-Shapley) which, at a speedup of 2, emulates an output-queued switch implementing a number of different output link scheduling algorithms such as weighted round robin and strict priority. We explore the performance of the algorithm at speedups between 1 and 2 using simulations and find that it partitions the bandwidth nearly as well as an output-queued switch at speedups 1.2 or higher.

Independent control of front and back gate in double gate (DG) devices can be used to merge parallel transistors in noncritical paths. This reduces the effective switching capacitance and, hence, the dynamic power dissipation of a circuit. However, efficient design of large-scale circuits with DG devices is not well explored due to lack of proper modeling and large-scale design simulation tools. In this paper, we propose several low-power circuit options using independent gate FinFETs. We developed semianalytical models for different FinFET logic gates to predict their performance. An efficient circuit synthesis methodology comprised of proposed low-power logic options in FinFET design library has been developed. Results show about 8.5% area savings and 18% power savings over conventional FinFET technology for ISCAS85 benchmark circuits in 45-nm technology with no performance penalty.

With technology scaling, soft error resilience is becoming a major concern in circuit design. This paper presents a class of low-overhead flip-flops suitable for soft error detection and correction. The proposed design reuses logic elements typically available in a standard-cell implementation of a flip-flop to reduce hardware overhead. We demonstrate that the proposed flip-flops are also suitable for enhanced scan based delay fault testing, which allows arbitrary two-pattern test application for the best combinational path testability. The proposed flip-flops show an average power reduction of 16% and area improvement of 17% compared to the best alternative techniques with no additional delay overhead

Abstract — Internet routers require buffers to hold packets during times of congestion. The buffers need to be fast, and so ideally they should be small enough to use fast memory technologies such as SRAM or all-optical buffering. Unfortunately, a widely used rule-of-thumb says we need a bandwidth-delay product of buffering at each router so as not to lose link utilization. This can be prohibitively large. In a recent paper, Appenzeller et al. challenged this rule-of-thumb and showed that for a backbone network, the buffer size can be divided by √ N without sacrificing throughput, where N is the number of flows sharing the bottleneck. In this paper, we explore how buffers in the backbone can be significantly reduced even more, to as little as a few dozen packets, if we are willing to sacrifice a small amount of link capacity. We argue that if the TCP sources are not overly bursty, then fewer than twenty packet buffers are sufficient for high throughput. Specifically, we argue that O(log W) buffers are sufficient, where W is the window size of each flow. We support our claim with analysis and a variety of simulations. The change we need to make to TCP is minimal—each sender just needs to pace packet injections from its window. Moreover, there is some evidence that such small buffers are sufficient even if we don’t modify the TCP sources so long as the access network is much slower than the backbone, which is true today and likely to remain true in the future. We conclude that buffers can be made small enough for all-optical routers with small integrated optical buffers. I.

In several database applications, parameters like selectivities and load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of query optimizers and monitoring schemes can be improved by spending resources like time or bandwidth in observing or resolving these parameters, so that better query plans can be generated. In a resource-constrained situation, deciding which parameters to observe in order to best optimize the expected quality of the plan generated (or in general, optimize the expected value of a certain objective function) itself becomes an interesting optimization problem.We present a framework for studying such problems, and present several scenarios arising in anomaly detection in complex systems, monitoring extreme values in sensor networks, load shedding in data stream systems, and estimating rates in wireless channels and minimum latency routes in networks, which can be modeled in this framework with the appropriate objective functions.Even for several simple objective functions, we show the problems are Np-Hard. We present greedy algorithms with good performance bounds. The proof of the performance bounds are via novel sub-modularity arguments.

We present a truthful auction for pricing advertising slots on a web-page assuming that advertisements for different merchants must be ranked in decreasing order of their (weighted) bids. This captures both the Overture model where bidders are ranked in order of the submitted bids, and the Google model where bidders are ranked in order of the expected revenue (or utility) that their advertisement generates. Assuming separable click-through rates, we prove revenue-equivalence between our auction and the non-truthful next-price auctions currently in use.

In this paper, we present a simple distributed algorithm for resource allocation which simultaneously approximates the optimum value for a large class of objective functions. In particular, we consider the class of canonical utility functions U that are symmetric, non-decreasing, concave, and satisfy U(0) = 0. Our distributed algorithm is based on primal-dual updates. We prove that this algorithm is an O(log ρ)-approximation for all canonical utility functions simultaneously, i.e. without any knowledge of U. The algorithm needs at most O(log2 ρ) iterations. Here n is the number of flows, m is the number of edges, R is the ratio between the maximum capacity and the minimum capacity of the edges in the network, and ρ is max (n, m, R).We extend this result to multi-path routing, and also to a natural pricing mechanism that results in a simple and practical protocol for bandwidth allocation in a network. When the protocol reaches equilibrium, the allocated bandwidths are the same as when the distributed algorithm converges; hence the protocol is also an O(log ρ) approximation for all canonical utility functions.

Providing approximate max-min fair bandwidth allocation among flows within a network or at a single router has been an important research problem. In this paper, we study the space complexity of fairness algorithms, and the communication complexity of distributed global fairness algorithms. We show that in order to enforce max-min fairness with bounded errors, a router must maintain per-flow state. Then we present a practical edge-marking based architecture to demonstrate the enforcement of approximate global max-min fairness for representative scenarios with multiple bottlenecks and non-responsive traffic. We validate our architecture using packet level simulations.

Medium access techniques for wireless sensor networks raise the important question of providing periodic energy-efficient radio sleep cycles while minimizing the end-to-end communication delays. This study aims to minimize the communication latency given that each sensor has a duty cycling requirement of being awake for only 1/k time slots on an average. As a first step we consider the single wake-up schedule case, where each sensor can choose exactly one of the k slots to wake up. We formulate a novel graph-theoretical abstraction of this problem in the general setting of a low-traffic wireless sensor network with arbitrary communication flows and prove that minimizing the end-to-end communication delays is in general NP-hard. However, we are able to derive and analyze optimal solutions for two special cases: tree topologies and ring topologies. Several heuristics for arbitrary topologies are proposed and evaluated by simulations. Our simulations suggest that distributed heuristics may perform poorly because of the global nature of the constraints involved. We also show that by carefully choosing multiple wake-up slots for each sensor significant delay savings can be obtained over the single wake-up schedule case while maintaining the same duty cycling. Using this technique, we propose algorithms that offer a desirable bound of d+O(k) on the delay for specialized topologies like the tree and grid and a weaker guarantee of O((d+k)log n) for arbitrary graphs, where d is the shortest path between 2 nodes in the underlying topology and n is the total number of nodes.

We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms.When the paths are known (either given by the adversary or computed as above), our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this article, we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet.Finally, we discuss the effects of combining routing with scheduling. We first show that some unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.

This article relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy et al. [1929]. We define α -supermajorization as an approximate form of vector majorization, and show that this definition generalizes and strengthens the prefix measure proposed by Kleinberg et al. [2001] as well as the popular notion of max-min fairness .The article revisits the problem of online load-balancing for unrelated 1-∞ machines from the viewpoint of fairness. We prove that a greedy approach is O (log n )-supermajorized by all other allocations, where n is the number of jobs. This means the greedy approach is globally O (log n )- fair . This may be contrasted with polynomial lower bounds presented by Goel et al. [2001] for fair online routing.We also define a machine-centric view of fairness using the related concept of submajorization . We prove that the greedy online algorithm is globally O (log m )- balanced , where m is the number of machines.

Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly different from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems. In this paper, we discuss a random sampling technique that incrementally improves lookup latency in DHT systems. Our sampling can be implemented using information gleaned from lookups traversing the overlay network. For this reason, we call our approach lookup-parasitic random sampling (LPRS). LPRS converges quickly, and requires relatively few modifications to existing DHT systems. For idealized versions of DHT systems like Chord, Tapestry, and Pastry, we analytically prove that LPRS can result in lookup latencies proportional to the average unicast latency of the network, provided the underlying physical topology has a power-law latency expansion. We then validate this analysis by implementing LPRS in the Chord simulator. Our simulations reveal that LPRS-Chord exhibits a qualitatively better latency scaling behavior relative to unmodified Chord. The overhead of LPRS is one sample per lookup hop in the worst case. Finally, we provide evidence which suggests that the Internet router-level topology resembles power-law latency expansion. This finding implies that LPRS has significant practical applicability as a general latency reduction technique for many DHT systems. This finding is also of independent interest since it might inform the design of latency-sensitive topology models for the Internet.

Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that partitions the sensors into covers, and then activates the covers iteratively in a round-robin fashion. This approach takes advantage of the overlap created when many sensors monitor a single area. Our work builds upon previous work in [13], where the model is first formulated. We have designed three approximation algorithms for a variation of the SET K-COVER problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized. The first algorithm is randomized and partitions the sensors, in expectation, within a fraction 1-1 e (~.63) of the optimum. We present two other deterministic approximation algorithms. One is a distributed greedy algorithm with a 1 2 approximation ratio and the other is a centralized greedy algorithm with a 1-1 e approximation ratio. We show that it is NP-Complete to guarantee better than 15 16 of the optimal coverage, indicating that all three algorithms perform well with respect to the best approximation algorithm possible in polynomial time, assuming P ≠ NP. Simulations indicate that in practice, the deterministic algorithms perform far above their worst case bounds, consistently covering more than 72% of what is covered by an optimum solution. Simulations also indicate that the increase in longevity is proportional to the amount of overlap amongst the sensors. The algorithms are fast, easy to use, and according to simulations, significantly increase the longevity of sensor networks. The randomized algorithm in particular seems quite practical.

We investigate the problem of online scheduling of jobs to minimize flow time and stretch on m identical machines. We consider the case where the algorithm is given either (1+ε)m machines or m machines of speed (1+ε), for arbitrarily small ε > 0. We show that simple randomized and deterministic load balancing algorithms, coupled with simple single machine scheduling strategies such as SRPT (shortest remaining processing time) and SJF (shortest job first), are O(poly(1/ε))-competitive for both flow time and stretch. These are the first results which prove constant factor competitive ratios for flow time or stretch with arbitrarily small resource augmentation. Both the randomized and the deterministic load balancing algorithms are non-migratory and do immediate dispatch of jobs.The randomized algorithm just allocates each incoming job to a random machine. Hence this algorithm is non-clairvoyant, and coupled with SETF (shortest elapsed time first), yields the first non-clairvoyant algorithm which is constant competitive for minimizing flow time with arbitrarily small resource augmentation. The deterministic algorithm that we analyze is due to Avrahami and Azar. For this algorithm, we show O(1/ε)-competitiveness for total flow time and stretch, and also for their Lp norms, for any fixed p ≥ 1.

Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0,1]d, and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of $n$ points distributed uniformly in [0,1]d. We present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.

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 study the stability of the commonly used packet forwarding protocol, FIFO (First In First Out), in the adversarial queuing model. We prove that FIFO can become unstable, i.e., lead to unbounded buffer-occupancies and queuing delays, at arbitrarily low injection rates. In order to demonstrate instability at rate r, we use a network of size polynomial in 1/r.

An oblivious active queue management scheme is one which does not differentiate between packets belonging to different flows. In this paper, we study the existence and the quality of Nash equilibria imposed by oblivious AQM schemes on selfish agents. Oblivious AQM schemes are of obvious importance because of the ease of implementation and deployment, and Nash equilibrium offers valuable clues into network performance under noncooperative user behavior. Specifically, we ask the following three questions: 1) do there exist oblivious AQM schemes that impose Nash equilibria on selfish agents? 2) Are the imposed equilibria, if they exist, efficient in terms of the goodput obtained and the drop probability experienced at the equilibrium? 3) How easy is it for selfish users to reach the Nash equilibrium state? We assume that the traffic sources are Poisson but the users can control the average rate. We show that drop-tail and RED do not impose Nash equilibria. We modify RED slightly to obtain an oblivious scheme, VLRED, that imposes a Nash equilibrium, but is not efficient. We then present another AQM policy, EN-AQM, that can impose an efficient Nash equilibrium. Finally, we show that for any oblivious AQM, the Nash equilibrium imposed on selfish agents is highly sensitive as the number of agents increases, thus making it hard for the users to converge to the Nash equilibrium, and motivating the need for equilibria-aware protocols.

Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly di#erent from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems.

DiffServ is an attractive candidate for providing relative QoS in the Internet. This is also easily amenable to simple and effective pricing mechanisms. By pricing access to a relative QoS, we can model a DiffServ node as a "join minimum cost queue" in which an arriving customer (packet or connection) determines the relative cost as a function of the congestion in the different queues and their access prices and decides to take service from that queue for which the cost is minimum. The Paris Metro pricing system and its work conserving variant called Tirupati pricing are analyzed in the presence of multiclass traffic and for static pricing. Two of the more interesting observations are that the disutility and revenue rate are not monotonic or convex functions of price and the revenue rate is very sensitive to the behavior of the delay sensitive class.

Scalable storage architectures allow for the addition of disks to increase storage capacity and/or bandwidth. In its general form, disk scaling also refers to disk removals when either capacity needs to be conserved or old disk drives are retired. Assuming random placement of blocks on multiple nodes of a continuous media server, our optimization objective is to redistribute a minimum number of media blocks after disk scaling. This objective should be met under two restrictions. First, uniform distribution and hence a balanced load should be ensured after redistribution. Second, the redistributed blocks should be retrieved at the normal mode of operation in one disk access and through low complexity computation. We propose a technique that meets the objective, while we prove that it also satisfies both restrictions. The SCADDAR approach is based on using a series of REMAP functions which can derive the location of a new block using only its original location as a basis.

We demonstrate how to apply Coupling from the Past, a simulation technique for exact sampling, to Markov chains based on TCP variants. This approach provides a new, statistically sound paradigm for network simulations: instead of simulating a protocol over long times, or explicitly finding the stationary distribution of a Markov chain, use Coupling from the Past to quickly obtain samples from the stationary distribution. Coupling from the Past is most efficient when the underlying state space satisfies a partial order and certain monotonicity conditions. To efficiently apply this general paradigm to TCP, we demonstrate that the states of a simple TCP model possess a monotonic partial order; this order appears interesting in its own right. Preliminary simulation results indicate that this approach is quite efficient, and produces results which am similar to those obtained by simulating a TCP-Tahoe connection.

Efficient data retrieval in a peer-to-peer system like Freenet is a challenging problem. We study the impact of cache replacement policy on the performance of Freenet. We find that, with Freenet's LRU (least recently used) cache replacement, there is a steep reduction in the hit ratio with increasing load. Based on intuition from the small-world models and the recent theoretical results by Kleinberg, we propose an enhanced-clustering cache replacement scheme for use in place of LRU. Such a replacement scheme forces the routing tables to resemble neighbor relationships in a small-world acquaintance graph - clustering with light randomness. In our simulation, this new scheme improved the request hit ratio dramatically while keeping the small average hops per successful request comparable to LRU. A simple, highly idealized model of Freenet under clustering with light randomness proves that the expected message delivery time in Freenet is O(log/sup 2/n) if the routing tables satisfy the small-world model and have the size /spl theta/(log/sup 2/n).

Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.We prove that the first problem is NP-complete in general, and polynomial time solvable on trees and squares. In order to prove that the problem is in NP, we present a polynomial time algorithm to verify whether a given tile system uniquely produces a given shape. This algorithm is analogous to a program verifier for traditional computational systems, and may well be of independent interest. For the second problem, we present a polynomial time $O(\log n)$-approximation algorithm that works for a large class of tile systems that we call partial order systems.

We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms. When the paths are known (either given by the adversary or computed as above) our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this paper we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet. Finally, we discuss the effects of combining routing with scheduling. We first show that some, unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.

In this paper we describe an efficient algorithm for the constrained shortest path problem which is defined as follows. Given a directed graph with two weights on each link e, a cost l/sub e/, and a delay t/sub e/, find the cheapest path from a source to all destinations such that the delay of each path is no more than a given threshold. The constrained shortest path problem arises in quality-of-service-sensitive routing in data networks and is of particular importance in real time services. The problem formulation and the algorithmic framework presented are quite general; they apply to IP, ATM, and optical networks. Unlike previous algorithms, our algorithm generates paths from one source to all destinations. Our algorithm is strongly polynomial, and is asymptotically faster than earlier algorithms. We corroborate our analysis by a preliminary simulation study.

Recently Rothemund and Winfree [6] have considered the program size complexity of constructing squares by self-assembly. Here, we consider the time complexity of such constructions using a natural generalization of the Tile Assembly Model defined in [6]. In the generalized model, the Rothemund-Winfree construction of n \times n squares requires time Θ(n log n) and program size Θ(log n). We present a new construction for assembling n \times n squares which uses optimal time Θ(n) and program size Θ(\frac{log n}{log log n}). This program size is also optimal since it matches the bound dictated by Kolmogorov complexity. Our improved time is achieved by demonstrating a set of tiles for parallel self-assembly of binary counters. Our improved program size is achieved by demonstrating that self-assembling systems can compute changes in the base representation of numbers. Self-assembly is emerging as a useful paradigm for computation. In addition the development of a computational theory of self-assembly promises to provide a new conduit by which results and methods of theoretical computer science might be applied to problems of interest in biology and the physical sciences.

Abstract The adversarial queueing theory model for packet routing was suggested by Borodin et al. We give a complete and simple characterization of all networks that are universally stable in this model. We show that the same characterization also holds for networks which are stable given that the packet forwarding protocol is FIFO (First in First out). We also show that a specific greedy protocol, SIS (Shortest in System), is stable against 0/1 stochastic adversaries. © 2001 John Wiley & Sons, Inc.

This paper presents online algorithms for routing and bandwidth allocation which simultaneously approximate fair and max-throughput solutions.In fact, the algorithms solve a more difficult problem: for any bandwidth b, the number of sessions that get bandwidth b in the online algorithm is not smaller than the number of sessions receiving vb offiine, where V is the competitive ratio.This problem is provably harder than the problem of maximizing throughput (e.g.[4]) or the problem of maximizing the bandwidth assigned to the most starved session (e.g.[3]).For the case where the algorithm assigns bandwidths, we present an O(log 2 n log 1+~ U/e)-competitive algorithm, for any e, where U is the minimum (over all choices of routes) of the 'maximum number of sessions routed along any single link.We also show an ~(log 1+~ U/e) lower bound in this model.For a more practically interesting model where the algorithm assigns routes and weights, and where these weights are used to drive the Weighted Fair Queuing policy in the routers, we present an O(log2nlogU)competitive algorithm.We also show that the dependence on U is necessary by presenting an ~(~) lower bound. The upper and lower bounds presented in [4] for online maximization of throughput become invalid if we

We study the problems of makespan minimization (load balancing), knapsack, and bin packing when the jobs have stochastic processing requirements or sizes. If the jobs are all Poisson, we present a two approximation for the first problem using Graham's rule, and observe that polynomial time approximation schemes can be obtained for the last two problems. If the jobs are all exponential, we present polynomial time approximation schemes for all three problems. We also obtain quasi-polynomial time approximation schemes for the last two problems if the jobs are Bernoulli variables.

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure, and a need to introduce guaranteed qualities of service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars, instead of shared memory systems; and QoS can be provided using WFQ-based packet scheduling. However, until now, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing, or centralized shared memory. This paper demonstrates that a combined input output queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet scheduling algorithms, including WFQ and strict priorities. More precisely, we show that a "speedup" of 2 is sufficient, and a speedup of 2-1/N is necessary, for this exact emulation. We introduce a variety of algorithms that configure the crossbar so that emulation is achieved with a speedup of two, and consider their running time and implementation complexity. An interesting feature of our work is that the exact emulation holds for all input traffic patterns. We believe that, in the future, these results will make possible the support of QoS in very high bandwidth routers.

In this paper we consider the online ftp problem.The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network.The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as mu-stretch, total flow time, max flow time, and total completion time.In particular, we show how to achieve optimum total flow time and optimum max.stretch if we increase the capacity of the underlying network by a logarithmic factor.We show that the resource augmentation is necessary by proving polynomial lower bounds on the maxstretch and total flow time for the case where online and offline algorithms are using same-capacity edges.Moreover, we also give poly-logarithmic lower bounds on the resource augmentation factor necessary in order to keep the total Aow time and max.stretch within a constant factor of optimum.

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N/spl times/N switch, a "speedup" of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies.

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.

Article Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median Share on Authors: Moses Charikar Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile , Chandra Chekuri Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile , Ashish Goel Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile , Sudipto Guha Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 114–123https://doi.org/10.1145/276698.276719Online:23 May 1998Publication History 96citation795DownloadsMetricsTotal Citations96Total Downloads795Last 12 Months33Last 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

This research proposes and tests an approach to engineering distributed file systems that are aimed at wide-scale, Internet-based use. The premise is that replication is essential to deliver performance and availability, yet the traditional conservative replica consistency algorithms do not scale to this environment. Our Ficus replicated file system uses a single-copy availability, optimistic update policy with reconciliation algorithms that reliably detect concurrent updates and automatically restore the consistency of directory replicas. The system uses the peer-to-peer model in which all machines are architectural equals but still permits configuration in a client-server arrangement where appropriate. Ficus has been used for six years at several geographically scattered installations. This paper details and evaluates the use of optimistic replica consistency, automatic update conflict detection and repair, the peer-to-peer (as opposed to client-server) interaction model, and the stackable file system architecture in the design and construction of Ficus. The paper concludes with a number of lessons learned from the experience of designing, building, measuring, and living with an optimistically replicated file system. © 1998 John Wiley & Sons, Ltd.