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)

Quantum online streaming algorithms with logarithmic memory
Title not available (Why is that?)
Multi-Priority Online Scheduling with Cancellations
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 Vehicle Routing Problems: A Survey
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
Online scheduling problems with flexible release dates: applications to infrastructure restoration
Two-sided online bipartite matching and vertex cover: beating the greedy algorithm
Competitive distributed decision-making
On variants of file caching
Exact distributional analysis of online algorithms with lookahead
Competitive analysis for the on-line truck transportation problem
Non-linear ski rental
Relative Worst-Order Analysis: A Survey
Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence
Online search for a hyperplane in high-dimensional Euclidean space
Engineering efficient paging algorithms
Methods for message routing in parallel machines
Online algorithms for page replication in rings
An online algorithm for the inventory retrieval problem with an uncertain selling duration, uncertain prices, and price-dependent demands
On bin packing with clustering and bin packing with delays
Tight bounds for restricted grid scheduling
Guessing fractions of online sequences
Group parking permit problems
Page migration with limited local memory capacity
Joint replenishment meets scheduling
Non-additive two-option ski rental
Online paging with heterogeneous cache slots
Optimal online edge coloring of planar graphs with advice
Equilibria in online games
The list update problem and the retrieval of sets
The list update problem and the retrieval of sets
New results for online page replication
An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones
Machine learning advised algorithms for the ski rental problem with a discount
On multi-threaded Paging
Randomized strategies for non-additive 3-slope ski rental
A new variable-sized bin packing problem
The fast algorithm for online \(k\)-server problem on trees
Competitive algorithms for the bicriteria \(k\)-server problem
Handling critical jobs online: deadline scheduling and convex-body chasing
Outperforming LRU via competitive analysis on parametrized inputs for paging
\textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm
Relaxing the irrevocability requirement for online graph algorithms
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 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
A comparison of performance measures for online algorithms

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)