Vivacidad y justicia en entornos no deterministas

El problema de la vivacidad y la selección justa surge en el contexto de los sistemas con ejecuciones no deterministas. El concepto de selección completamente justa ´ sirve para garantizar que todos los elementos que se habilitan infinitamente a menudo se ejecutan infinitamente a menudo. Esta noción...

Full description

Autores:
Ruiz Cortés, David
Corchuelo, Rafael
Ruiz Cortés, Antonio
Tipo de recurso:
Trabajo de grado de pregrado
Fecha de publicación:
2002
Institución:
Universidad Autónoma de Bucaramanga - UNAB
Repositorio:
Repositorio UNAB
Idioma:
spa
OAI Identifier:
oai:repository.unab.edu.co:20.500.12749/9064
Acceso en línea:
http://hdl.handle.net/20.500.12749/9064
Palabra clave:
Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Distributed systems
Interactions between multiple participants
Vivacity
fair selection
Innovaciones tecnológicas
Ciencias de la computación
Desarrollo tecnológico
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
Sistemas distribuidos
Interacciones entre múltiples participantes
Vivacidad
Selección justa
Rights
License
Derechos de autor 2002 Revista Colombiana de Computación
id UNAB2_02b205a8ab0aff21ff10c0d793f4a913
oai_identifier_str oai:repository.unab.edu.co:20.500.12749/9064
network_acronym_str UNAB2
network_name_str Repositorio UNAB
repository_id_str
dc.title.spa.fl_str_mv Vivacidad y justicia en entornos no deterministas
dc.title.translated.eng.fl_str_mv Liveliness and fairness in non-deterministic environments
title Vivacidad y justicia en entornos no deterministas
spellingShingle Vivacidad y justicia en entornos no deterministas
Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Distributed systems
Interactions between multiple participants
Vivacity
fair selection
Innovaciones tecnológicas
Ciencias de la computación
Desarrollo tecnológico
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
Sistemas distribuidos
Interacciones entre múltiples participantes
Vivacidad
Selección justa
title_short Vivacidad y justicia en entornos no deterministas
title_full Vivacidad y justicia en entornos no deterministas
title_fullStr Vivacidad y justicia en entornos no deterministas
title_full_unstemmed Vivacidad y justicia en entornos no deterministas
title_sort Vivacidad y justicia en entornos no deterministas
dc.creator.fl_str_mv Ruiz Cortés, David
Corchuelo, Rafael
Ruiz Cortés, Antonio
dc.contributor.author.spa.fl_str_mv Ruiz Cortés, David
Corchuelo, Rafael
Ruiz Cortés, Antonio
dc.contributor.googlescholar.spa.fl_str_mv Corchuelo, Rafael [xH6ErLQAAAAJ]
Ruiz Cortés, Antonio [Ka-FHBQAAAAJ]
dc.contributor.orcid.spa.fl_str_mv Corchuelo, Rafael [0000-0003-1563-6979]
Ruiz Cortés, Antonio [0000-0001-9827-1834]
dc.contributor.researchgate.spa.fl_str_mv Ruiz Cortés, Antonio [Antonio-Ruiz-Cortes]
dc.subject.none.fl_str_mv Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
topic Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Distributed systems
Interactions between multiple participants
Vivacity
fair selection
Innovaciones tecnológicas
Ciencias de la computación
Desarrollo tecnológico
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
Sistemas distribuidos
Interacciones entre múltiples participantes
Vivacidad
Selección justa
dc.subject.keywords.eng.fl_str_mv Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Distributed systems
Interactions between multiple participants
Vivacity
dc.subject.keywords.none.fl_str_mv fair selection
dc.subject.lemb.spa.fl_str_mv Innovaciones tecnológicas
Ciencias de la computación
Desarrollo tecnológico
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
dc.subject.proposal.spa.fl_str_mv Sistemas distribuidos
Interacciones entre múltiples participantes
Vivacidad
Selección justa
description El problema de la vivacidad y la selección justa surge en el contexto de los sistemas con ejecuciones no deterministas. El concepto de selección completamente justa ´ sirve para garantizar que todos los elementos que se habilitan infinitamente a menudo se ejecutan infinitamente a menudo. Esta noción de selección presenta dos anomalías: la finitud justa y las conspiraciones. Este articulo se centra en la selección justa de interacciones en sistemas basados en ´ interacciones entre múltiples participantes ´ y presenta una nueva noción llamada ´ selección completamente ´ k–justa cuya principal ventaja sobre otras propuestas es que da solución a las dos anomalías de forma simultanea. Para ello, hemos descrito un marco de trabajo teórico para caracterizar los sistemas ´ basados en interacciones entre múltiples participantes que hace independiente el criterio de selección del lenguaje de programación . También presentamos un algoritmo general para implementar ´ la selección completamente ´ k–justa de interacciones que no requiere acceder al estado local de los procesos del sistema.
publishDate 2002
dc.date.issued.none.fl_str_mv 2002-06-01
dc.date.accessioned.none.fl_str_mv 2020-10-27T00:21:30Z
dc.date.available.none.fl_str_mv 2020-10-27T00:21:30Z
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/article
dc.type.local.spa.fl_str_mv Artículo
dc.type.coar.none.fl_str_mv http://purl.org/coar/resource_type/c_7a1f
dc.type.redcol.none.fl_str_mv http://purl.org/redcol/resource_type/CJournalArticle
format http://purl.org/coar/resource_type/c_7a1f
dc.identifier.issn.none.fl_str_mv 2539-2115
1657-2831
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/20.500.12749/9064
dc.identifier.instname.spa.fl_str_mv instname:Universidad Autónoma de Bucaramanga UNAB
dc.identifier.repourl.none.fl_str_mv repourl:https://repository.unab.edu.co
identifier_str_mv 2539-2115
1657-2831
instname:Universidad Autónoma de Bucaramanga UNAB
repourl:https://repository.unab.edu.co
url http://hdl.handle.net/20.500.12749/9064
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1109/1081
dc.relation.uri.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1109
dc.relation.references.none.fl_str_mv R. Alur and T. A. Henzinger. Finitary fairness. ACM Transactions on Programming Languages and Systems, 20(6):1171–1194, November 1998.
P.C. Attie, N. Francez, and O. Grumberg. Fairness and hyperfairness in multiparty interactions. Distributed Computing, 6(4):245–254, 1993.
R.L. Bagrodia. Process synchronization: Design and performance evaluation of distributed algorithms. IEEE Transactions on Software Engineering, 15(9):1053–1065, September 1989.
E. Best. Fairness and conspiracies. Information Processing Letters, 18(4):215–220, 1984.
E. Best. Semantics of Sequential and Parallel Programs. Prentice Hall, New York, 1996.
J.R. Buchi. On a decision method in restricted second order arithmetic. In ¨ Proceedings of the International Congress on Logic, Method, and Philosophy of Science, pages 1–12, Stanford, CA, USA, 1962. Stanford University Press.
K.M. Chandy and J. Misra. Parallel Program Design: A Foundation. Addison–Wesley, 1988.
R. Corchuelo, J.A. Perez, and M. Toro. A multiparty coordination aspect language. ´ ACM Sigplan, 35(12):24–32, December 2000.
R. Corchuelo, D. Ruiz, M. Toro, and A. Ruiz. Implementing multiparty interactions on a network computer. In Proceedings of the XXVth Euromicro Conference (Workshop on Network Computing), Milan, September 1999. IEEE Press.
M. Evangelist, V.Y. Shen, I.R. Forman, and M. Graf. Using Raddle to design distributed systems. In Proceedings of the 10th International Conference on Software Engineering, pages 102–115. IEEE Computer Society Press, April 1988.
N. Francez. Fairness. Springer–Verlag, 1986.
N. Francez and I. Forman. Interacting processes: A multiparty approach to coordinated distributed programming. Addison–Wesley, 1996.
N. Francez and M. Rodeh. A distributed abstract data type implemented by a probabilistic communication scheme. In Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science, pages 373–379, 1980.
Y.J. Joung. Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability. Theoretical Computer Science, 243(1–2):307–338, 2000.
Y.J. Joung and S.A. Smolka. Strong interaction fairness via randomization. IEEE Transactions on Parallel and Distributed Systems, 9(2):137–149, February 1998.
E. Olderog and K.R. Apt. Fairness in parallel programs: The transformational approach. ACM Transactions on Programming Languages and Systems, 10(3):420–455, July 1988.
J. A. Perez, R. Corchuelo, D. Ruiz, and M. Toro. An order-based, distributed algorithm for im- ´ plementing multiparty interactions. In Fifth International Conference on Coordination Models and Languages COORDINATION 2002, pages 250–257, York, UK, 2002. Springer–Verlag.
J.A. Perez, R. Corchuelo, D. Ruiz, and M. Toro. A framework for aspect–oriented multiparty ´ coordination. In New Developments in Ditributed Applications and Interoperable Systems, pages 161–173. Kluwer Academic Publishers, 2001.
J.A. Perez, R. Corchuelo, D. Ruiz, and M. Toro. An enablement detection algorithm for open ´ multiparty interactions. In ACM Symposium on Applied Computing SAC’02, pages 378–384, Madrid, Spain, 2002. Springer–Verlag.
D. Ruiz, R. Corchuelo, J.A. Perez, and M. Toro. Un algoritmo descentralizado de selecci ´ on´ justa de interacciones entre multiples participantes. In ´ Simposio Espanol de Inform ˜ atica Dis- ´ tribuida 2000, pages 419–427, Ourense, Spain, 2000.
A.S. Tanenbaum. Modern Operating Systems. Prentice Hall, New Jersey, 1992.
Y.K. Tsay and R.L. Bagrodia. Some impossibility results in interprocess synchronization. Distributed Computing, 6(4):221–231, 1993.
dc.rights.none.fl_str_mv Derechos de autor 2002 Revista Colombiana de Computación
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rights.uri.none.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/2.5/co/
dc.rights.creativecommons.*.fl_str_mv Atribución-NoComercial-SinDerivadas 2.5 Colombia
rights_invalid_str_mv Derechos de autor 2002 Revista Colombiana de Computación
http://creativecommons.org/licenses/by-nc-sa/4.0/
http://creativecommons.org/licenses/by-nc-nd/2.5/co/
Atribución-NoComercial-SinDerivadas 2.5 Colombia
http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
dc.source.none.fl_str_mv Revista Colombiana de Computación; Vol. 3 Núm. 1 (2002): Revista Colombiana de Computación; 73-92
institution Universidad Autónoma de Bucaramanga - UNAB
bitstream.url.fl_str_mv https://repository.unab.edu.co/bitstream/20.500.12749/9064/1/2002_Articulo_Vivacidad%20y%20justicia%20en%20entornos%20no%20deterministas.pdf
https://repository.unab.edu.co/bitstream/20.500.12749/9064/2/2002_Articulo_Vivacidad%20y%20justicia%20en%20entornos%20no%20deterministas.pdf.jpg
bitstream.checksum.fl_str_mv 253825b494c818f3e2dbada64d4f9f2b
2f9a2c4c36fd9fa133036857dc47786d
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional | Universidad Autónoma de Bucaramanga - UNAB
repository.mail.fl_str_mv repositorio@unab.edu.co
_version_ 1814277260120686592
spelling Ruiz Cortés, David5f38c460-58af-4420-ba35-4b04efe7d977Corchuelo, Rafael2a54952c-c61d-4272-b03d-8575c3aff518Ruiz Cortés, Antonioe3c7bbfe-5cc1-4355-a0a9-f7f3735a1fe2Corchuelo, Rafael [xH6ErLQAAAAJ]Ruiz Cortés, Antonio [Ka-FHBQAAAAJ]Corchuelo, Rafael [0000-0003-1563-6979]Ruiz Cortés, Antonio [0000-0001-9827-1834]Ruiz Cortés, Antonio [Antonio-Ruiz-Cortes]2020-10-27T00:21:30Z2020-10-27T00:21:30Z2002-06-012539-21151657-2831http://hdl.handle.net/20.500.12749/9064instname:Universidad Autónoma de Bucaramanga UNABrepourl:https://repository.unab.edu.coEl problema de la vivacidad y la selección justa surge en el contexto de los sistemas con ejecuciones no deterministas. El concepto de selección completamente justa ´ sirve para garantizar que todos los elementos que se habilitan infinitamente a menudo se ejecutan infinitamente a menudo. Esta noción de selección presenta dos anomalías: la finitud justa y las conspiraciones. Este articulo se centra en la selección justa de interacciones en sistemas basados en ´ interacciones entre múltiples participantes ´ y presenta una nueva noción llamada ´ selección completamente ´ k–justa cuya principal ventaja sobre otras propuestas es que da solución a las dos anomalías de forma simultanea. Para ello, hemos descrito un marco de trabajo teórico para caracterizar los sistemas ´ basados en interacciones entre múltiples participantes que hace independiente el criterio de selección del lenguaje de programación . También presentamos un algoritmo general para implementar ´ la selección completamente ´ k–justa de interacciones que no requiere acceder al estado local de los procesos del sistema.The problem of liveliness and fair selection arises in the context of systems with executing non-deterministic tions. The concept of completely fair selection serves to ensure that all items that are enabled infinitely often are executed infinitely often. This notion of selection presents two anomalies: fair finitude and conspiracies. East The article focuses on the fair selection of interactions in systems based on multi-participant interactions and introduces a new notion called completely k-fair selection. whose main advantage over other proposals is that it solves the two anomalies simultaneously. To do this, we have described a theoretical framework to characterize the systems based on interactions between multiple participants that makes the selection criteria independent tion of the programming language. We also present a general algorithm to implement the completely k-fair selection of interactions that does not require access to the local state of system processes.application/pdfspaUniversidad Autónoma de Bucaramanga UNABhttps://revistas.unab.edu.co/index.php/rcc/article/view/1109/1081https://revistas.unab.edu.co/index.php/rcc/article/view/1109R. Alur and T. A. Henzinger. Finitary fairness. ACM Transactions on Programming Languages and Systems, 20(6):1171–1194, November 1998.P.C. Attie, N. Francez, and O. Grumberg. Fairness and hyperfairness in multiparty interactions. Distributed Computing, 6(4):245–254, 1993.R.L. Bagrodia. Process synchronization: Design and performance evaluation of distributed algorithms. IEEE Transactions on Software Engineering, 15(9):1053–1065, September 1989.E. Best. Fairness and conspiracies. Information Processing Letters, 18(4):215–220, 1984.E. Best. Semantics of Sequential and Parallel Programs. Prentice Hall, New York, 1996.J.R. Buchi. On a decision method in restricted second order arithmetic. In ¨ Proceedings of the International Congress on Logic, Method, and Philosophy of Science, pages 1–12, Stanford, CA, USA, 1962. Stanford University Press.K.M. Chandy and J. Misra. Parallel Program Design: A Foundation. Addison–Wesley, 1988.R. Corchuelo, J.A. Perez, and M. Toro. A multiparty coordination aspect language. ´ ACM Sigplan, 35(12):24–32, December 2000.R. Corchuelo, D. Ruiz, M. Toro, and A. Ruiz. Implementing multiparty interactions on a network computer. In Proceedings of the XXVth Euromicro Conference (Workshop on Network Computing), Milan, September 1999. IEEE Press.M. Evangelist, V.Y. Shen, I.R. Forman, and M. Graf. Using Raddle to design distributed systems. In Proceedings of the 10th International Conference on Software Engineering, pages 102–115. IEEE Computer Society Press, April 1988.N. Francez. Fairness. Springer–Verlag, 1986.N. Francez and I. Forman. Interacting processes: A multiparty approach to coordinated distributed programming. Addison–Wesley, 1996.N. Francez and M. Rodeh. A distributed abstract data type implemented by a probabilistic communication scheme. In Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science, pages 373–379, 1980.Y.J. Joung. Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability. Theoretical Computer Science, 243(1–2):307–338, 2000.Y.J. Joung and S.A. Smolka. Strong interaction fairness via randomization. IEEE Transactions on Parallel and Distributed Systems, 9(2):137–149, February 1998.E. Olderog and K.R. Apt. Fairness in parallel programs: The transformational approach. ACM Transactions on Programming Languages and Systems, 10(3):420–455, July 1988.J. A. Perez, R. Corchuelo, D. Ruiz, and M. Toro. An order-based, distributed algorithm for im- ´ plementing multiparty interactions. In Fifth International Conference on Coordination Models and Languages COORDINATION 2002, pages 250–257, York, UK, 2002. Springer–Verlag.J.A. Perez, R. Corchuelo, D. Ruiz, and M. Toro. A framework for aspect–oriented multiparty ´ coordination. In New Developments in Ditributed Applications and Interoperable Systems, pages 161–173. Kluwer Academic Publishers, 2001.J.A. Perez, R. Corchuelo, D. Ruiz, and M. Toro. An enablement detection algorithm for open ´ multiparty interactions. In ACM Symposium on Applied Computing SAC’02, pages 378–384, Madrid, Spain, 2002. Springer–Verlag.D. Ruiz, R. Corchuelo, J.A. Perez, and M. Toro. Un algoritmo descentralizado de selecci ´ on´ justa de interacciones entre multiples participantes. In ´ Simposio Espanol de Inform ˜ atica Dis- ´ tribuida 2000, pages 419–427, Ourense, Spain, 2000.A.S. Tanenbaum. Modern Operating Systems. Prentice Hall, New Jersey, 1992.Y.K. Tsay and R.L. Bagrodia. Some impossibility results in interprocess synchronization. Distributed Computing, 6(4):221–231, 1993.Derechos de autor 2002 Revista Colombiana de Computaciónhttp://creativecommons.org/licenses/by-nc-sa/4.0/http://creativecommons.org/licenses/by-nc-nd/2.5/co/Atribución-NoComercial-SinDerivadas 2.5 Colombiahttp://purl.org/coar/access_right/c_abf2Revista Colombiana de Computación; Vol. 3 Núm. 1 (2002): Revista Colombiana de Computación; 73-92Innovaciones tecnológicasCiencia de los computadoresDesarrollo de tecnologíaIngeniería de sistemasInvestigacionesTecnologías de la información y las comunicacionesTIC´sTechnological innovationsComputer scienceTechnology developmentSystems engineeringInvestigationsInformation and communication technologiesICT'sDistributed systemsInteractions between multiple participantsVivacityfair selectionInnovaciones tecnológicasCiencias de la computaciónDesarrollo tecnológicoIngeniería de sistemasInvestigacionesTecnologías de la información y la comunicaciónSistemas distribuidosInteracciones entre múltiples participantesVivacidadSelección justaVivacidad y justicia en entornos no deterministasLiveliness and fairness in non-deterministic environmentsinfo:eu-repo/semantics/articleArtículohttp://purl.org/coar/resource_type/c_7a1fhttp://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/redcol/resource_type/CJournalArticleORIGINAL2002_Articulo_Vivacidad y justicia en entornos no deterministas.pdf2002_Articulo_Vivacidad y justicia en entornos no deterministas.pdfArtículoapplication/pdf680650https://repository.unab.edu.co/bitstream/20.500.12749/9064/1/2002_Articulo_Vivacidad%20y%20justicia%20en%20entornos%20no%20deterministas.pdf253825b494c818f3e2dbada64d4f9f2bMD51open accessTHUMBNAIL2002_Articulo_Vivacidad y justicia en entornos no deterministas.pdf.jpg2002_Articulo_Vivacidad y justicia en entornos no deterministas.pdf.jpgIM Thumbnailimage/jpeg8515https://repository.unab.edu.co/bitstream/20.500.12749/9064/2/2002_Articulo_Vivacidad%20y%20justicia%20en%20entornos%20no%20deterministas.pdf.jpg2f9a2c4c36fd9fa133036857dc47786dMD52open access20.500.12749/9064oai:repository.unab.edu.co:20.500.12749/90642022-11-23 17:46:36.973open accessRepositorio Institucional | Universidad Autónoma de Bucaramanga - UNABrepositorio@unab.edu.co

Publicaciones similares