On Multi-threaded Metrical Task Systems

Mostrar todas las versiones(3)

Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests ar...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Feuerstein, E., Seiden, S.S., Strejilevich de Loma, A.
Formato:	Artículo publishedVersion
Publicado:	2006
Materias:	Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Multi-threaded Metrical Task Systems Multiprocessing systems
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_15708667_v4_n3_p401_Feuerstein http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15708667_v4_n3_p401_Feuerstein_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-paper_15708667_v4_n3_p401_Feuerstein_oai
record_format	dspace
spelling	I28-R145-paper_15708667_v4_n3_p401_Feuerstein_oai2020-10-19 Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A. 2006 Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information. © 2006 Elsevier B.V. All rights reserved. Fil:Strejilevich de Loma, A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_15708667_v4_n3_p401_Feuerstein info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar J. Discrete Algorithms 2006;4(3):401-413 Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems On Multi-threaded Metrical Task Systems info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15708667_v4_n3_p401_Feuerstein_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
topic	Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems
spellingShingle	Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A. On Multi-threaded Metrical Task Systems
topic_facet	Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems
description	Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information. © 2006 Elsevier B.V. All rights reserved.
format	Artículo Artículo publishedVersion
author	Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A.
author_facet	Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A.
author_sort	Feuerstein, E.
title	On Multi-threaded Metrical Task Systems
title_short	On Multi-threaded Metrical Task Systems
title_full	On Multi-threaded Metrical Task Systems
title_fullStr	On Multi-threaded Metrical Task Systems
title_full_unstemmed	On Multi-threaded Metrical Task Systems
title_sort	on multi-threaded metrical task systems
publishDate	2006
url	http://hdl.handle.net/20.500.12110/paper_15708667_v4_n3_p401_Feuerstein http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15708667_v4_n3_p401_Feuerstein_oai
work_keys_str_mv	AT feuersteine onmultithreadedmetricaltasksystems AT seidenss onmultithreadedmetricaltasksystems AT strejilevichdelomaa onmultithreadedmetricaltasksystems
_version_	1766026785362804736

On Multi-threaded Metrical Task Systems

Ejemplares similares