Arrow Research search

Author name cluster

Michael Mitzenmacher

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

46 papers
2 author rows

Possible papers

46

ICLR Conference 2025 Conference Paper

Don't stop me Now: Embedding based Scheduling for LLMS

  • Rana Shahout
  • Eran Malach
  • Chunwei Liu
  • Weifan Jiang
  • Minlan Yu
  • Michael Mitzenmacher

Efficient scheduling is crucial for interactive Large Language Model (LLM) applications, where low request completion time directly impacts user engagement. Size-based scheduling algorithms like Shortest Remaining Process Time (SRPT) aim to reduce average request completion time by leveraging known or estimated request sizes and allowing preemption by incoming jobs with shorter service times. However, two main challenges arise when applying size-based scheduling to LLM systems. First, accurately predicting output lengths from prompts is challenging and often resource-intensive, making it impractical for many systems. As a result, the state-of-the-art LLM systems default to first-come, first-served scheduling, which can lead to head-of-line blocking and reduced system efficiency. Second, preemption introduces extra memory overhead to LLM systems as they must maintain intermediate states for unfinished (preempted) requests. In this paper, we propose TRAIL, a method to obtain output predictions from the target LLM itself. After generating each output token, we recycle the embedding of its internal structure as input for a lightweight classifier that predicts the remaining length for each running request. Using these predictions, we propose a prediction-based SRPT variant with limited preemption designed to account for memory overhead in LLM systems. This variant allows preemption early in request execution when memory consumption is low but restricts preemption as requests approach completion to optimize resource utilization. On the theoretical side, we derive a closed-form formula for this SRPT variant in an M/G/1 queue model, which demonstrates its potential value. In our system, we implement this preemption policy alongside our embedding-based prediction method. Our refined predictions from layer embeddings achieve 2.66x lower mean absolute error compared to BERT predictions from sequence prompts. TRAIL achieves 1.66x to 2.01x lower mean latency on the Alpaca dataset and 1.76x to 24.07x lower mean time to the first token compared to the state-of-the-art serving system.

Details

NeurIPS Conference 2025 Conference Paper

Fast Inference for Augmented Large Language Models

  • Rana Shahout
  • Cong Liang
  • Shiji Xin
  • Qianru Lao
  • Yong Cui
  • Minlan Yu
  • Michael Mitzenmacher

Augmented Large Language Models (LLMs) enhance standalone LLMs by integrating external data sources through API calls. In interactive applications, efficient scheduling is crucial for maintaining low request completion times, directly impacting user engagement. However, these augmentations introduce new scheduling challenges: the size of augmented requests (in tokens) no longer correlates proportionally with execution time, making traditional size-based scheduling algorithms like Shortest Job First less effective. Additionally, requests may require different handling during API calls, which must be incorporated into scheduling. This paper presents MARS, a novel inference framework that optimizes augmented LLM latency by explicitly incorporating system- and application-level considerations into scheduling. MARS introduces a predictive, memory-aware scheduling approach that integrates API handling and request prioritization to minimize completion time. We implement MARS on top of vLLM and evaluate its performance against baseline LLM inference systems, demonstrating improvements in end-to-end latency by 27%-85% and reductions in TTFT by 4%-96% compared to the existing augmented-LLM system, with even greater gains over vLLM. Our implementation is available online.

PDF Details

ICML Conference 2024 Conference Paper

Accelerating Federated Learning with Quick Distributed Mean Estimation

  • Ran Ben-Basat
  • Shay Vargaftik
  • Amit Portnoy
  • Gil Einziger
  • Yaniv Ben-Itzhak
  • Michael Mitzenmacher

Distributed Mean Estimation (DME), in which $n$ clients communicate vectors to a parameter server that estimates their average, is a fundamental building block in communication-efficient federated learning. In this paper, we improve on previous DME techniques that achieve the optimal $O(1/n)$ Normalized Mean Squared Error (NMSE) guarantee by asymptotically improving the complexity for either encoding or decoding (or both). To achieve this, we formalize the problem in a novel way that allows us to use off-the-shelf mathematical solvers to design the quantization. Using various datasets and training tasks, we demonstrate how QUIC-FL achieves state of the art accuracy with faster encoding and decoding times compared to other DME methods.

Details

NeurIPS Conference 2024 Conference Paper

Optimal and Approximate Adaptive Stochastic Quantization

  • Ran B. Basat
  • Yaniv Ben-Itzhak
  • Michael Mitzenmacher
  • Shay Vargaftik

Quantization is a fundamental optimization for many machine learning (ML) use cases, including compressing gradients, model weights and activations, and datasets. The most accurate form of quantization is adaptive, where the error is minimized with respect to a given input rather than optimizing for the worst case. However, optimal adaptive quantization methods are considered infeasible in terms of both their runtime and memory requirements. We revisit the Adaptive Stochastic Quantization (ASQ) problem and present algorithms that find optimal solutions with asymptotically improved time and space complexities. Our experiments indicate that our algorithms may open the door to using ASQ more extensively in a variety of ML applications. We also present an even faster approximation algorithm for quantizing large inputs on the fly.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

SkipPredict: When to Invest in Predictions for Scheduling

  • Rana Shahout
  • Michael Mitzenmacher

Expanding on recent work on scheduling with predicted job sizes, we consider the effect of the cost of predictions in queueing systems, removing the assumption in prior research that predictions are external to the system’s resources and/or cost-free. Additionally, we introduce a novel approach to utilizing predictions, SkipPredict, designed to address their inherent cost. Rather than uniformly applying predictions to all jobs, we propose a tailored approach that categorizes jobs to improve the effectiveness of prediction on performance. To achieve this, we employ one-bit “cheap predictions” to classify jobs as either short or long. SkipPredict prioritizes predicted short jobs over long jobs, and for the long jobs, SkipPredict applies a second round of more detailed “expensive predictions” to approximate Shortest Remaining Processing Time for these jobs. Importantly, our analyses take into account the cost of prediction. We derive closed-form formulas that calculate the mean response time of jobs with size predictions accounting for the prediction cost. We examine the effect of this cost for two distinct models in real-world and synthetic datasets. In the external cost model, predictions are generated by external method without impacting job service times but incur a cost. In the server time cost model, predictions themselves require server processing time and are scheduled on the same server as the jobs.

PDF Details DOI

TMLR Journal 2024 Journal Article

Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference

  • Max Lam
  • Michael Mitzenmacher
  • Vijay Janapa Reddi
  • Gu-Yeon Wei
  • David Brooks

Multiparty computation approaches to secure neural network inference commonly rely on garbled circuits for securely executing nonlinear activation functions. However, garbled circuits require excessive communication between server and client, impose significant storage overheads, and incur large runtime penalties; for example, securely evaluating ResNet-32 using standard approaches requires more than 300MB of communication, over 10s of runtime, and around 5 GB of preprocessing storage. To reduce these costs, we propose an alternative to garbled circuits: Tabula, an algorithm based on secure lookup tables. Our approach precomputes lookup tables during an offline phase that contains the result of all possible nonlinear function calls. Because these tables incur exponential storage costs in the number of operands and the precision of the input values, we use quantization to reduce these storage costs to make this approach practical. This enables an online phase where securely computing the result of a nonlinear function requires just a single round of communication, with communication cost equal to twice the number of bits of the input to the nonlinear function. In practice our approach costs 2 bytes of communication per nonlinear function call in the online phase. Compared to garbled circuits with quantized inputs, when computing individual nonlinear functions during the online phase, experiments show Tabula uses between $280$-$560 \times$ less communication, is over $100\times$ faster, and uses a comparable amount of storage; compared against other state-of-the-art protocols Tabula achieves greater than $40\times$ communication reduction. This leads to significant performance gains over garbled circuits with quantized inputs during the online phase of secure inference of neural networks: Tabula reduces end-to-end inference communication by up to $9 \times$ and achieves an end-to-end inference speedup of up to $50 \times$, while imposing comparable storage and offline preprocessing costs.

PDF Details

ICML Conference 2022 Conference Paper

EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning

  • Shay Vargaftik
  • Ran Ben-Basat
  • Amit Portnoy
  • Gal Mendelson
  • Yaniv Ben-Itzhak
  • Michael Mitzenmacher

Distributed Mean Estimation (DME) is a central building block in federated learning, where clients send local gradients to a parameter server for averaging and updating the model. Due to communication constraints, clients often use lossy compression techniques to compress the gradients, resulting in estimation inaccuracies. DME is more challenging when clients have diverse network conditions, such as constrained communication budgets and packet losses. In such settings, DME techniques often incur a significant increase in the estimation error leading to degraded learning performance. In this work, we propose a robust DME technique named EDEN that naturally handles heterogeneous communication budgets and packet losses. We derive appealing theoretical guarantees for EDEN and evaluate it empirically. Our results demonstrate that EDEN consistently improves over state-of-the-art DME techniques.

Details

NeurIPS Conference 2021 Conference Paper

DRIVE: One-bit Distributed Mean Estimation

  • Shay Vargaftik
  • Ran Ben-Basat
  • Amit Portnoy
  • Gal Mendelson
  • Yaniv Ben-Itzhak
  • Michael Mitzenmacher

We consider the problem where $n$ clients transmit $d$-dimensional real-valued vectors using $d(1+o(1))$ bits each, in a manner that allows the receiver to approximately reconstruct their mean. Such compression problems naturally arise in distributed and federated learning. We provide novel mathematical results and derive computationally efficient algorithms that are more accurate than previous compression techniques. We evaluate our methods on a collection of distributed and federated learning tasks, using a variety of datasets, and show a consistent improvement over the state of the art.

PDF Details

ICML Conference 2021 Conference Paper

Gradient Disaggregation: Breaking Privacy in Federated Learning by Reconstructing the User Participant Matrix

  • Maximilian Lam
  • Gu-Yeon Wei
  • David M. Brooks
  • Vijay Janapa Reddi
  • Michael Mitzenmacher

We show that aggregated model updates in federated learning may be insecure. An untrusted central server may disaggregate user updates from sums of updates across participants given repeated observations, enabling the server to recover privileged information about individual users’ private training data via traditional gradient inference attacks. Our method revolves around reconstructing participant information (e. g: which rounds of training users participated in) from aggregated model updates by leveraging summary information from device analytics commonly used to monitor, debug, and manage federated learning systems. Our attack is parallelizable and we successfully disaggregate user updates on settings with up to thousands of participants. We quantitatively and qualitatively demonstrate significant improvements in the capability of various inference attacks on the disaggregated updates. Our attack enables the attribution of learned properties to individual users, violating anonymity, and shows that a determined central server may undermine the secure aggregation protocol to break individual users’ data privacy in federated learning.

Details

SODA Conference 2021 Conference Paper

Improved Sublinear Time Algorithm for Longest Increasing Subsequence

  • Michael Mitzenmacher
  • Saeed Seddighin

We present a novel sublinear time algorithm for approximating LIS. If we denote the ratio of the solution size over the input size by λ, our approach yields an algorithm with an approximation factor of Ω( λ∊ ) for any constant ∊ > 0, and a truly sublinear runtime. This improves over for example the recent work of Rubinstein et al. [RSSS19] that approximates LIS within a factor Ω( λ 3 ) in truly sublinear time. Our work makes use of a grid packing technique recently introduced by Mitzenmacher and Seddighin to approximate LIS in the dynamic setting [MS20], providing another application for this technique.

Details

ICLR Conference 2021 Conference Paper

Partitioned Learned Bloom Filters

  • Kapil Vaidya
  • Eric Knorr
  • Michael Mitzenmacher
  • Tim Kraska

Bloom filters are space-efficient probabilistic data structures that are used to test whether an element is a member of a set, and may return false positives. Recently, variations referred to as learned Bloom filters were developed that can provide improved performance in terms of the rate of false positives, by using a learned model for the represented set. However, previous methods for learned Bloom filters do not take full advantage of the learned model. Here we show how to frame the problem of optimal model utilization as an optimization problem, and using our framework derive algorithms that can achieve near-optimal performance in many cases.

Details

ICML Conference 2021 Conference Paper

Putting the "Learning" into Learning-Augmented Algorithms for Frequency Estimation

  • Elbert Du
  • Franklyn Wang
  • Michael Mitzenmacher

In learning-augmented algorithms, algorithms are enhanced using information from a machine learning algorithm. In turn, this suggests that we should tailor our machine-learning approach for the target algorithm. We here consider this synergy in the context of the learned count-min sketch from (Hsu et al. , 2019). Learning here is used to predict heavy hitters from a data stream, which are counted explicitly outside the sketch. We show that an approximately sufficient statistic for the performance of the underlying count-min sketch is given by the coverage of the predictor, or the normalized $L^1$ norm of keys that are filtered by the predictor to be explicitly counted. We show that machine learning models which are trained to optimize for coverage lead to large improvements in performance over prior approaches according to the average absolute frequency error. Our source code can be found at https: //github. com/franklynwang/putting-the-learning-in-LAA.

Details

STOC Conference 2020 Conference Paper

Dynamic algorithms for LIS and distance to monotonicity

  • Michael Mitzenmacher
  • Saeed Seddighin

In this paper, we provide new approximation algorithms for dynamic variations of the longest increasing subsequence (LIS) problem, and the complementary distance to monotonicity (DTM) problem. In this setting, operations of the following form arrive sequentially: (i) add an element, (ii) remove an element, or (iii) substitute an element for another. At every point in time, the algorithm has an approximation to the longest increasing subsequence (or distance to monotonicity). We present a (1+є)-approximation algorithm for DTM with polylogarithmic worst-case update time and a constant factor approximation algorithm for LIS with worst-case update time Õ( n є ) for any constant є > 0.

Details

AAAI Conference 2019 Conference Paper

Online Pandora’s Boxes and Bandits

  • Hossein Esfandiari
  • MohammadTaghi Hajiaghayi
  • Brendan Lucier
  • Michael Mitzenmacher

We consider online variations of the Pandora’s box problem (Weitzman 1979), a standard model for understanding issues related to the cost of acquiring information for decision-making. Our problem generalizes both the classic Pandora’s box problem and the prophet inequality framework. Boxes are presented online, each with a random value and cost drawn jointly from some known distribution. Pandora chooses online whether to open each box given its cost, and then chooses irrevocably whether to keep the revealed prize or pass on it. We aim for approximation algorithms against adversaries that can choose the largest prize over any opened box, and use optimal offline policies to decide which boxes to open (without knowledge of the value inside)1. We consider variations where Pandora can collect multiple prizes subject to feasibility constraints, such as cardinality, matroid, or knapsack constraints. We also consider variations related to classic multi-armed bandit problems from reinforcement learning. Our results use a reduction-based framework where we separate the issues of the cost of acquiring information from the online decision process of which prizes to keep. Our work shows that in many scenarios, Pandora can achieve a good approximation to the best possible performance.

PDF Details

NeurIPS Conference 2018 Conference Paper

A Bayesian Nonparametric View on Count-Min Sketch

  • Diana Cai
  • Michael Mitzenmacher
  • Ryan Adams

The count-min sketch is a time- and memory-efficient randomized data structure that provides a point estimate of the number of times an item has appeared in a data stream. The count-min sketch and related hash-based data structures are ubiquitous in systems that must track frequencies of data such as URLs, IP addresses, and language n-grams. We present a Bayesian view on the count-min sketch, using the same data structure, but providing a posterior distribution over the frequencies that characterizes the uncertainty arising from the hash-based approximation. In particular, we take a nonparametric approach and consider tokens generated from a Dirichlet process (DP) random measure, which allows for an unbounded number of unique tokens. Using properties of the DP, we show that it is possible to straightforwardly compute posterior marginals of the unknown true counts and that the modes of these marginals recover the count-min sketch estimator, inheriting the associated probabilistic guarantees. Using simulated data with known ground truth, we investigate the properties of these estimators. Lastly, we also study a modified problem in which the observation stream consists of collections of tokens (i. e. , documents) arising from a random measure drawn from a stable beta process, which allows for power law scaling behavior in the number of unique tokens.

PDF Details

NeurIPS Conference 2018 Conference Paper

A Model for Learned Bloom Filters and Optimizing by Sandwiching

  • Michael Mitzenmacher

Recent work has suggested enhancing Bloom filters by using a pre-filter, based on applying machine learning to determine a function that models the data set the Bloom filter is meant to represent. Here we model such learned Bloom filters, with the following outcomes: (1) we clarify what guarantees can and cannot be associated with such a structure; (2) we show how to estimate what size the learning function must obtain in order to obtain improved performance; (3) we provide a simple method, sandwiching, for optimizing learned Bloom filters; and (4) we propose a design and analysis approach for a learned Bloomier filter, based on our modeling approach.

PDF Details

FOCS Conference 2018 Conference Paper

Metric Sublinear Algorithms via Linear Sampling

  • Hossein Esfandiari
  • Michael Mitzenmacher

We provide a new technique to design fast approximation algorithms for graph problems where the points of the graph lie in a metric space. Specifically, we present a sampling approach for such metric graphs that, using a sublinear number of edge weight queries, provides a linear sampling, where each edge is (roughly speaking) sampled proportionally to its weight. For several natural problems, such as densest subgraph and max cut, we show that by sparsifying the graph using this sampling process, we can run a suitable approximation algorithm on the sparsified graph and the result remains a good approximation for the original problem. Our results have several interesting implications, such as providing the first sublinear time approximation algorithm for densest subgraph in a metric space, and improving the running time of estimating the average distance.

Details

ICML Conference 2018 Conference Paper

Weightless: Lossy weight encoding for deep neural network compression

  • Brandon Reagen
  • Udit Gupta 0001
  • Bob Adolf
  • Michael Mitzenmacher
  • Alexander M. Rush
  • Gu-Yeon Wei
  • David M. Brooks

The large memory requirements of deep neural networks limit their deployment and adoption on many devices. Model compression methods effectively reduce the memory requirements of these models, usually through applying transformations such as weight pruning or quantization. In this paper, we present a novel scheme for lossy weight encoding co-designed with weight simplification techniques. The encoding is based on the Bloomier filter, a probabilistic data structure that can save space at the cost of introducing random errors. Leveraging the ability of neural networks to tolerate these imperfections and by re-training around the errors, the proposed technique, named Weightless, can compress weights by up to 496x without loss of model accuracy. This results in up to a 1. 51x improvement over the state-of-the-art.

Details

JMLR Journal 2016 Journal Article

Measuring Dependence Powerfully and Equitably

  • Yakir A. Reshef
  • David N. Reshef
  • Hilary K. Finucane
  • Pardis C. Sabeti
  • Michael Mitzenmacher

Given a high-dimensional data set, we often wish to find the strongest relationships within it. A common strategy is to evaluate a measure of dependence on every variable pair and retain the highest-scoring pairs for follow-up. This strategy works well if the statistic used (a) has good power to detect non-trivial relationships, and (b) is equitable, meaning that for some measure of noise it assigns similar scores to equally noisy relationships regardless of relationship type (e.g., linear, exponential, periodic). In this paper, we define and theoretically characterize two new statistics that together yield an efficient approach for obtaining both power and equitability. To do this, we first introduce a new population measure of dependence and show three equivalent ways that it can be viewed, including as a canonical smoothing of mutual information. We then introduce an efficiently computable consistent estimator of our population measure of dependence, and we empirically establish its equitability on a large class of noisy functional relationships. This new statistic has better bias/variance properties and better runtime complexity than a previous heuristic approach. Next, we derive a second, related statistic whose computation is a trivial side-product of our algorithm and whose goal is powerful independence testing rather than equitability. We prove that this statistic yields a consistent independence test and show in simulations that the test has good power against independence. Taken together, our results suggest that these two statistics are a valuable pair of tools for exploratory data analysis. [abs] [ pdf ][ bib ] &copy JMLR 2016. ( edit, beta )

PDF Details

NeurIPS Conference 2016 Conference Paper

Quantized Random Projections and Non-Linear Estimation of Cosine Similarity

  • Ping Li
  • Michael Mitzenmacher
  • Martin Slawski

Random projections constitute a simple, yet effective technique for dimensionality reduction with applications in learning and search problems. In the present paper, we consider the problem of estimating cosine similarities when the projected data undergo scalar quantization to $b$ bits. We here argue that the maximum likelihood estimator (MLE) is a principled approach to deal with the non-linearity resulting from quantization, and subsequently study its computational and statistical properties. A specific focus is on the on the trade-off between bit depth and the number of projections given a fixed budget of bits for storage or transmission. Along the way, we also touch upon the existence of a qualitative counterpart to the Johnson-Lindenstrauss lemma in the presence of quantization.

PDF Details

ICML Conference 2014 Conference Paper

Coding for Random Projections

  • Ping Li 0001
  • Michael Mitzenmacher
  • Anshumali Shrivastava

The method of random projections has become popular for large-scale applications in statistical learning, information retrieval, bio-informatics and other applications. Using a well-designed \textbfcoding scheme for the projected data, which determines the number of bits needed for each projected value and how to allocate these bits, can significantly improve the effectiveness of the algorithm, in storage cost as well as computational speed. In this paper, we study a number of simple coding schemes, focusing on the task of similarity estimation and on an application to training linear classifiers. We demonstrate that \textbfuniform quantization outperforms the standard and influential method \citeProc: Datar_SCG04, which used a \em window-and-random offset scheme. Indeed, we argue that in many cases coding with just a small number of bits suffices. Furthermore, we also develop a \textbfnon-uniform 2-bit coding scheme that generally performs well in practice, as confirmed by our experiments on training linear support vector machines (SVM). Proofs and additional experiments are available at \em arXiv: 1308. 2218. In the context of using coded random projections for \textbfapproximate near neighbor search by building hash tables (\em arXiv: 1403. 8144) \citeReport: RPCodeLSH2014, we show that the step of random offset in \citeProc: Datar_SCG04 is again not needed and may hurt the performance. Furthermore, we show that, unless the target similarity level is high, it usually suffices to use only 1 or 2 bits to code each hashed value for this task. Section \refsec_LSH presents some experimental results for LSH.

Details

FOCS Conference 2002 Conference Paper

Load Balancing with Memory

  • Michael Mitzenmacher
  • Balaji Prabhakar
  • Devavrat Shah

A standard load balancing model considers placing n balls into n bins by choosing d possible locations for each ball independently and uniformly at random and sequentially placing each in the least loaded of its chosen bins. It is well known that allowing just a small amount of choice (d = 2) greatly improves performance over random placement (d = 1). In this paper, we show that similar performance gains occur by introducing memory. We focus on the situation where each time a ball is placed, the least loaded of that ball's choices after placement is remembered and used as one of the possible choices for the next ball. For example, we show that when each ball gets just one random choice, but can also choose the best of the last ball's choices, the maximum number of balls in a bin is log log n/2 log /spl phi/ + O(1) with high probability, where /spl phi/ = (1 + /spl radic/5)/2 is the golden ratio. The asymptotic performance is therefore better with one random choice and one choice from memory than with two fresh random choices for each ball; the performance with memory asymptotically matches the asymmetric policy, using two choices introduced by Vocking (1999). More generally, we find that a small amount of memory, like a small amount of choice, can dramatically improve the load balancing performance. We also investigate continuous time variations corresponding to queueing systems, where we find similar results.

Details

I&C Journal 2001 Journal Article

Delayed Information and Action in On-Line Algorithms

  • Susanne Albers
  • Moses Charikar
  • Michael Mitzenmacher

Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time when relevant information is available and the time a decision has an effect may be decoupled. For example, when making an investment, one might not have completely up-to-date information on market prices. Similarly, a buy or sell order might only be executed some time in the future. We introduce and explore natural delayed models for several well-known on-line problems. Our analyses demonstrate the importance of considering timeliness in determining the competitive ratio of an on-line algorithm. For many problems, we demonstrate that there exist algorithms with small competitive ratios even when large delays affect the timeliness of information and the effect of decisions.

Details DOI

FOCS Conference 2000 Conference Paper

Linear Waste of Best Fit Bin Packing on Skewed Distributions

  • Claire Mathieu
  • Michael Mitzenmacher

We prove that best-fit bin packing has linear waste on the discrete distribution U{j, k} (where items are drawn uniformly from the set {1/k, 2/k, .. ., j/k}) for sufficiently large k when j=/spl alpha/k and 0. 66/spl les//spl alpha/<2/3. Our results extend to continuous skewed distributions, where items are drawn uniformly on [0, a], for 0. 66/spl les/a<2/3. This implies that the expected asymptotic performance ratio of best-fit bin packing is strictly greater than 1 for these distributions.

Details

FOCS Conference 1998 Conference Paper

Delayed Information and Action in On-line Algorithms

  • Susanne Albers
  • Moses Charikar
  • Michael Mitzenmacher

Most on-line analysis assumes that, at each time-step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time relevant information is available and the time a decision has an effect may be decoupled. For example, when making an investment, one might not have completely up-to-date information on market prices. Similarly, a buy or sell order might only be executed some time later in the future. We introduce and explore natural delayed models for several well-known on-line problems. Our analyses demonstrate the importance of considering timeliness in determining the competitive ratio of an on-line algorithm. For many problems, we demonstrate that there exist algorithms with small competitive ratios even when large delays affect the timeliness of information and the effect of decisions.

Details

FOCS Conference 1996 Conference Paper

Load Balancing and Density Dependent Jump Markov Processes (extended abstract)

  • Michael Mitzenmacher

We provide a new approach for analyzing both static and dynamic randomized load balancing strategies. We demonstrate the approach by providing the first analysis of the following model: customers arrive as a Poisson stream of rate /spl lambda//sub n/, /spl lambda/<1, at a collection of n servers. Each customer chooses some constant d servers independently and uniformly at random from the n servers, and waits for service at the one with the fewest customers. Customers are served according to the first-in first-out (FIFO) protocol, and the service time for a customer is exponentially distributed with mean 1. We call this problem the supermarket model. We wish to know how the system behaves, and in particular we are interested in the expected time a customer spends in the system in equilibrium. The model provides a good abstraction of a simple, efficient load balancing scheme in the setting where jobs arrive at a large system of parallel processors. This model appears more realistic than similar models studied previously, in that it is both dynamic and open: that is, customers arrive over time, and the number of customers is not fixed.

Details

TCS Journal 1994 Journal Article

Computational complexity of loss networks

  • Graham Louth
  • Michael Mitzenmacher
  • Frank Kelly

In this paper we examine the theoretical limits on developing algorithms to find blocking probabilities in a general loss network. We demonstrate that exactly computing the blocking probabilities of a loss network is a # P-complete problem. We also show that a general algorithm for approximating the blocking probabilities is also intractable unless RP = NP, which seems unlikely according to current common notions in complexity theory. Given these results, we examine implications for designing practical algorithms for finding blocking probabilities in special cases.

Details DOI
v2026.09.13