Competitive snoopy caching
From MaRDI portal
Publication:1103391
DOI10.1007/BF01762111zbMath0645.68034OpenAlexW2011670396WikidataQ56140916 ScholiaQ56140916MaRDI QIDQ1103391
Publication date: 1988
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01762111
potential functionsshared memorycommunication costspage replacementmultiprocessor systemcache coherenceamortized analysisshared-bus multiprocessorssnoopy caching
Related Items
Competitive randomized algorithms for nonuniform problems ⋮ Competitive \(k\)-server algorithms ⋮ Online-bounded analysis ⋮ Methods for message routing in parallel machines ⋮ MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling ⋮ The list update problem and the retrieval of sets ⋮ Competitive algorithms for the weighted server problem ⋮ An improved lower bound for load balancing of tasks with unknown duration ⋮ The working set algorithm has competitive ratio less than two ⋮ Uniform multipaging reduces to paging ⋮ Online companion caching ⋮ New results for online page replication ⋮ The CNN problem and other \(k\)-server variants ⋮ Online bin covering: expectations vs. guarantees ⋮ Evaluating the quality of online optimization algorithms by discrete event simulation ⋮ On multi-threaded metrical task systems ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ Online scheduling problems with flexible release dates: applications to infrastructure restoration ⋮ Online ordering policies for a two-product, multi-period stationary newsvendor problem ⋮ Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence ⋮ The work function algorithm for the paging problem ⋮ Competitive distributed decision-making ⋮ Online multi-coloring on the path revisited ⋮ The relative worst-order ratio applied to paging ⋮ Paging with connections: FIFO strikes again ⋮ A theoretical comparison of LRU and LRU-K ⋮ Better bounds on online unit clustering ⋮ Stochastization of Weighted Automata ⋮ Online search for a hyperplane in high-dimensional Euclidean space ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ The Frequent Items Problem in Online Streaming Under Various Performance Measures ⋮ Group parking permit problems ⋮ Paging more than one page ⋮ An online algorithm for the inventory retrieval problem with an uncertain selling duration, uncertain prices, and price-dependent demands ⋮ The advice complexity of a class of hard online problems ⋮ Connection caching: Model and algorithms. ⋮ Risk-reward models for on-line leasing of depreciable equipment ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Comparing online algorithms for bin packing problems ⋮ A new variable-sized bin packing problem ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Optimal randomized algorithm for a generalized ski-rental with interest rate ⋮ List factoring and relative worst order analysis ⋮ Competitive analysis for online leasing problem with compound interest rate ⋮ Competitive strategy for on-line leasing of depreciable equipment ⋮ Online stochastic optimization under time constraints ⋮ The \(k\)-server problem ⋮ More on weighted servers or FIFO is better than LRU. ⋮ Competitive distributed file allocation. ⋮ Online failure diagnosis in interdependent networks ⋮ Calculating lower bounds for caching problems ⋮ A comparison of performance measures for online algorithms ⋮ On bin packing with clustering and bin packing with delays ⋮ The optimal structure of algorithms for \(\alpha\)-paging ⋮ Online traveling salesman problem with deadlines and service flexibility ⋮ Online dominating set ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ On Variants of File Caching ⋮ Online algorithms with advice: the tape model ⋮ Comparing first-fit and next-fit for online edge coloring ⋮ The weighted list update problem and the lazy adversary ⋮ Clever or smart: strategies for the online target date assignment problem ⋮ Probability-free solutions to the non-stationary newsvendor problem ⋮ On-line algorithms for 2-coloring hypergraphs via chip games ⋮ Scheduling jobs on grid processors ⋮ Ski rental with two general options ⋮ Competitive analysis for the on-line truck transportation problem ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ Paging with request sets ⋮ An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones ⋮ Competitive analysis of the online inventory problem ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection ⋮ Weighted online problems with advice ⋮ The maximum resource bin packing problem ⋮ Equilibria in Online Games ⋮ Relative interval analysis of paging algorithms on access graphs ⋮ Exact distributional analysis of online algorithms with lookahead ⋮ Weighted Online Problems with Advice ⋮ Randomized online interval scheduling ⋮ Guessing fractions of online sequences ⋮ Engineering Efficient Paging Algorithms ⋮ Unfair problems and randomized algorithms for metrical task systems ⋮ Bounds for Scheduling Jobs on Grid Processors ⋮ Machine learning advised algorithms for the ski rental problem with a discount ⋮ The fast algorithm for online \(k\)-server problem on trees ⋮ Randomized strategies for non-additive 3-slope ski rental ⋮ Preemptive on-line scheduling for two uniform processors ⋮ \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm ⋮ Non-additive two-option ski rental ⋮ On the power of randomization in on-line algorithms ⋮ Randomized competitive algorithms for the list update problem ⋮ On-line algorithms for locating checkpoints ⋮ A new measure for the study of on-line algorithms ⋮ Rent or buy problems with a fixed time horizon ⋮ Online Bin Covering: Expectations vs. Guarantees ⋮ Online file caching with rejection penalties ⋮ Non-Additive Two-Option Ski Rental ⋮ Asymptotically optimal online page migration on three points ⋮ Online multi-coloring with advice ⋮ Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ Randomized online multi-threaded paging ⋮ Online Multi-Coloring with Advice ⋮ Online Dual Edge Coloring of Paths and Trees ⋮ Page migration with limited local memory capacity ⋮ Measuring the problem-relevant information in input ⋮ On-line scheduling with hard deadlines ⋮ Online \(L(2,1)\)-coloring problem on paths with restricted size of memory ⋮ Non-linear ski rental ⋮ Joint replenishment meets scheduling ⋮ Online Parallel-Batch Scheduling of Learning Effect Jobs with Incompatible Job Families for Prefabricated Components ⋮ Relative Worst-Order Analysis: A Survey ⋮ Online minimum spanning trees with weight predictions ⋮ Tight Bounds for Restricted Grid Scheduling ⋮ ON THE k-TRUCK SCHEDULING PROBLEM ⋮ On packet scheduling with adversarial jamming and speedup ⋮ Price Fluctuations: To Buy or to Rent ⋮ Online Vehicle Routing Problems: A Survey ⋮ Online Bounded Analysis ⋮ Unnamed Item ⋮ The list update problem and the retrieval of sets ⋮ Handling Critical Jobs Online: Deadline Scheduling and Convex-Body Chasing ⋮ Preemptive multiprocessor scheduling with rejection ⋮ Online algorithms for page replication in rings ⋮ Online paging and file caching with expiration times ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ On the Bahncard problem ⋮ On the best possible competitive ratio for the multislope ski-rental problem ⋮ Scheduling in the dark ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Multi-Priority Online Scheduling with Cancellations ⋮ Discrete online TSP ⋮ Online traveling salesman problems with service flexibility ⋮ Paging more than one page ⋮ Unnamed Item ⋮ On multi-threaded Paging
