On-line multi-threaded paging
In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which reques...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_01784617_v32_n1_p36_Feuerstein |
| Aporte de: |
| id |
todo:paper_01784617_v32_n1_p36_Feuerstein |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_01784617_v32_n1_p36_Feuerstein2023-10-03T15:08:18Z On-line multi-threaded paging Feuerstein, E. Strejilevich De Loma, A. Competitive analysis Fairness Multi-tasking systems On-line algorithms Paging In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. Four different on-line problems arise depending on whether we consider fairness restrictions or not, with finite or infinite input sequences. We study all of them, proving lower and upper bounds for the competitiveness of on-line algorithms. The main competitiveness results presented in this paper state that when no fairness restrictions are imposed it is possible to obtain competitive algorithms for finite and infinite inputs. On the other hand, for the fair case in general there exist no competitive algorithms. In addition, we consider three definitions of competitiveness for infinite inputs. One of them forces algorithms to behave efficiently at every finite stage, while the other two aim at comparing the algorithms' steady-state performances. A priori, the three definitions seem different. We study them and find, however, that they are essentially equivalent. This suggests that the competitiveness results that we obtain reflect the intrinsic difficulty of the problem and are not a consequence of a too strict definition of competitiveness. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_01784617_v32_n1_p36_Feuerstein |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Competitive analysis Fairness Multi-tasking systems On-line algorithms Paging |
| spellingShingle |
Competitive analysis Fairness Multi-tasking systems On-line algorithms Paging Feuerstein, E. Strejilevich De Loma, A. On-line multi-threaded paging |
| topic_facet |
Competitive analysis Fairness Multi-tasking systems On-line algorithms Paging |
| description |
In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. Four different on-line problems arise depending on whether we consider fairness restrictions or not, with finite or infinite input sequences. We study all of them, proving lower and upper bounds for the competitiveness of on-line algorithms. The main competitiveness results presented in this paper state that when no fairness restrictions are imposed it is possible to obtain competitive algorithms for finite and infinite inputs. On the other hand, for the fair case in general there exist no competitive algorithms. In addition, we consider three definitions of competitiveness for infinite inputs. One of them forces algorithms to behave efficiently at every finite stage, while the other two aim at comparing the algorithms' steady-state performances. A priori, the three definitions seem different. We study them and find, however, that they are essentially equivalent. This suggests that the competitiveness results that we obtain reflect the intrinsic difficulty of the problem and are not a consequence of a too strict definition of competitiveness. |
| format |
JOUR |
| author |
Feuerstein, E. Strejilevich De Loma, A. |
| author_facet |
Feuerstein, E. Strejilevich De Loma, A. |
| author_sort |
Feuerstein, E. |
| title |
On-line multi-threaded paging |
| title_short |
On-line multi-threaded paging |
| title_full |
On-line multi-threaded paging |
| title_fullStr |
On-line multi-threaded paging |
| title_full_unstemmed |
On-line multi-threaded paging |
| title_sort |
on-line multi-threaded paging |
| url |
http://hdl.handle.net/20.500.12110/paper_01784617_v32_n1_p36_Feuerstein |
| work_keys_str_mv |
AT feuersteine onlinemultithreadedpaging AT strejilevichdelomaa onlinemultithreadedpaging |
| _version_ |
1807316982771482624 |