Competitive snoopy caching

DOI10.1007/BF01762111zbMATH Open0645.68034DBLPjournals/algorithmica/KarlinMRS88OpenAlexW2011670396WikidataQ56140916 ScholiaQ56140916MaRDI QIDQ1103391FDOQ1103391

Authors: B. George

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01762111

zbMATH Keywords

shared memory page replacement multiprocessor system potential functions amortized analysis cache coherence communication costs shared-bus multiprocessors snoopy caching

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Cited In (only showing first 100 items - show all)

Outperforming LRU via competitive analysis on parametrized inputs for paging
\textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm
Online traveling salesman problems with service flexibility
Comparing first-fit and next-fit for online edge coloring
Competitive distributed file allocation.
Ramsey-type theorems for metric spaces with applications to online problems
Probability-free solutions to the non-stationary newsvendor problem
Measuring the problem-relevant information in input
On-line algorithms for locating checkpoints
The work function algorithm for the paging problem
Clever or smart: strategies for the online target date assignment problem
Scheduling in the dark
The advice complexity of a class of hard online problems
Paging with request sets
Online Vehicle Routing Problems: A Survey
Online edge coloring of paths and trees with a fixed number of colors
Risk-reward models for on-line leasing of depreciable equipment
Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications
On multi-threaded metrical task systems
Preemptive on-line scheduling for two uniform processors
An improved lower bound for load balancing of tasks with unknown duration
The working set algorithm has competitive ratio less than two
Randomized online interval scheduling
On the power of randomization in on-line algorithms
Bounds for scheduling jobs on grid processors
Optimal randomized algorithm for a generalized ski-rental with interest rate
Weighted online problems with advice
Uniform multipaging reduces to paging
Online bin covering: expectations vs. guarantees
Preemptive multiprocessor scheduling with rejection
On the best possible competitive ratio for the multislope ski-rental problem
Competitive analysis for online leasing problem with compound interest rate
The CNN problem and other \(k\)-server variants
Relative interval analysis of paging algorithms on access graphs
Randomized competitive algorithms for the list update problem
Scheduling jobs on grid processors
Weighted Online Problems with Advice
The \(k\)-server problem
On-line algorithms for 2-coloring hypergraphs via chip games
The Frequent Items Problem in Online Streaming Under Various Performance Measures
The relative worst-order ratio applied to paging
Paging with connections: FIFO strikes again
Competitive randomized algorithms for nonuniform problems
A theoretical comparison of LRU and LRU-K
Price fluctuations: to buy or to rent
Stochastization of weighted automata
A new measure for the study of on-line algorithms
Online Dual Edge Coloring of Paths and Trees
Online bounded analysis
Paging more than one page
Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
More on weighted servers or FIFO is better than LRU.
An optimal online algorithm for scheduling two machines with release times
On the Bahncard problem
Online ordering policies for a two-product, multi-period stationary newsvendor problem
Ski rental with two general options
Competitive analysis of the online inventory problem
Competitive \(k\)-server algorithms
List factoring and relative worst order analysis
Rent or buy problems with a fixed time horizon
Competitive strategy for on-line leasing of depreciable equipment
The optimal structure of algorithms for \(\alpha\)-paging
MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
Online traveling salesman problem with deadlines and service flexibility
Comparing online algorithms for bin packing problems
On-line scheduling with hard deadlines
Online multi-coloring on the path revisited
Online Bin Covering: Expectations vs. Guarantees
Online stochastic optimization under time constraints
Competitive algorithms for the weighted server problem
The maximum resource bin packing problem
Better bounds on online unit clustering
Online algorithms with advice: the tape model
Online \(L(2,1)\)-coloring problem on paths with restricted size of memory
Quantum online streaming algorithms with logarithmic memory
Title not available (Why is that?)
Online Parallel-Batch Scheduling of Learning Effect Jobs with Incompatible Job Families for Prefabricated Components
Online Multi-Coloring with Advice
Online computation with untrusted advice
Non-additive two-option ski rental
ON THE k-TRUCK SCHEDULING PROBLEM
Online file caching with rejection penalties
Connection caching: Model and algorithms.
Discrete online TSP
Online dominating set
Online failure diagnosis in interdependent networks
Online-bounded analysis
Randomized online multi-threaded paging
Online companion caching
Calculating lower bounds for caching problems
Asymptotically optimal online page migration on three points
Unfair problems and randomized algorithms for metrical task systems
Online paging and file caching with expiration times
Online multi-coloring with advice
Paging more than one page
The weighted list update problem and the lazy adversary
On packet scheduling with adversarial jamming and speedup
Evaluating the quality of online optimization algorithms by discrete event simulation
Applying ``peeling onion approach for competitive analysis in online scheduling with rejection
Online minimum spanning trees with weight predictions

This page was built for publication: Competitive snoopy caching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103391)