Optimal Randomized Scheduling by Replacement

Isaac Saias
Additional contact information
Isaac Saias: Los Alamos National Laboratory

Journal of Combinatorial Optimization, 1998, vol. 1, issue 4, No 7, 427-456

Abstract: Abstract In the replacement scheduling problem, a system consists of n processors drawn from a pool of p,all initially “alive”. At any time some processor can die. The scheduler is immediately informed of the fault butnot of its location. It must then choose another set of n processors. If this new set contains a dead processor, the system crashes and halts. The performance of a scheduling protocol is measured by the expected number of deaths the system tolerates before it crashes. We provide an optimal randomized scheduling protocol for this problem. The framework of this work combines an absolute performance measure for protocols and so-called adaptive online adversaries. This framework is rarely addressed because of the complexity of the interaction between protocols and adversaries. A major contribution of ourwork is to provide a theoretical foundation for the analysis of this interaction. In particular we make explicit how the protocol and the adversary affect the probability distribution of the analysis—a very general problem. We carefully analyze the exchange of sinformation between the two players, and reveal how they use their information optimally. The optimality of the protocol is established by using of a saddle point method for protocols and adversaries.

Keywords: Mathematical Modeling; Probability Distribution; Schedule Problem; Saddle Point; Industrial Mathematic (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009703014438 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:1:y:1998:i:4:d:10.1023_a:1009703014438

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009703014438

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().