Steady-state performance analysis of multiserver queueing models with redundancy

Cover Page

Cite item

Full Text

Abstract

An approach to study of the stochastic models of distributed computing systems by means of the multiserver queueing models with redundancy is suggested. Perspectives and limitations of the approach, as well as possible future research directions are presented.

About the authors

Alexander Sergeevich Rumyantsev

Institute of Applied Mathematical Research KarRC of RAS

Author for correspondence.
Email: ar0@krc.karelia.ru
ORCID iD: 0000-0003-2364-5939
senior researcher, PhD, key interests: queueing theory, multiserver systems, stochastic modeling and analysis, high-performance and distributed computing, matrix-analytic method, regenerative approach, three-level modeling

Diana Sergeevna Dolgaleva

Institute of Applied Mathematical Research KarRC of RAS

Email: abcdi_do@mail.ru
ORCID iD: 0000-0002-0606-6583
intern-researcher, key interests: queueing theory, matrix-analytic method, bioinformatics, gene networks, distributed computing

Alexander Stanislavovich Golovin

Institute of Applied Mathematical Research KarRC of RAS

Email: golovin@krc.karelia.ru
ORCID iD: 0000-0003-1325-3739
leading engineer-researcher, PhD student, key interests: queueing theory, matrix-analytic method, energy efficiency, simulation, distributed computing, multiserver queues

References

  1. Chernov I., Nikitina N., Ivashko E.. “Task scheduling in desktop grids: open problems”, Open Engineering, 7:1 (2017), pp. 343–357.
  2. Verma N., Singh D.. “Data redundancy implications in wireless sensor networks”, Procedia Computer Science, 132 (2018), pp. 1210–1217.
  3. Rumyantsev A., Ivashko E., Chernov I., Kositsyn D., Shabaev A., Ponomarev V.. “Latency/wearout in a flash-based storage system with replication on write”, 2019 24th Conference of Open Innovations Association (FRUCT) (08–12 April 2019, Moscow, Russia), pp. 360–366.
  4. Chernov I., Ivashko E., Kositsyn D., Ponomarev V., Rumyantsev A., Shabaev A.. “Flash-based storage deduplication techniques: A survey”, International Journal Of Embedded And Real-Time Communication Systems (IJERTCS), 10:3 (2019), pp. 32–48.
  5. Osipov O., Rogachko E.. “Fork-join queueing systems with heterogeneous servers threshold control policy”, SMARTY2020 (August 16–20, 2020, Petrozavodsk, Russia), CEUR Workshop Proc., vol. 2792, 2020, pp. 76–88.
  6. Rumyantsev A., Chakravarthy S., Morozov E., Remnev S.. “Cost and effect of replication and quorum in desktop grid computing”, Information Technologies And Mathematical Modelling. Queueing Theory And Applications, Springer CCIS Series, vol. 912, Springer, Cham, 2018, ISBN 978-3-319-97594-8, pp. 143–156.
  7. Thomasian A.. “Analysis of fork/join and related queueing systems”, ACM Computing Surveys, 47:2 (2014), 17, 71 pp.
  8. Baccelli F., Makowski A., Shwartz A.. “The fork-join queue and related systems with synchronization constraints: Stochastic ordering and computable bounds”, Advances in Applied Probability, 21:3 (1989), pp. 629–660.
  9. Gardner K., Zbarsky S., Doroudi S., Harchol-Balter M., Hyytia E., Scheller-Wolf A.. “Queueing with redundant requests: Exact analysis”, Queueing Systems, 83:3–4 (2016), pp. 227–259.
  10. Kim C., Agrawala A. K.. “Analysis of the fork-join queue”, IEEE Transactions on Computers, 38:2 (1989), pp. 250–255.
  11. Nelson R., Tantawi A. N.. “Approximate analysis of fork/join synchronization in parallel queues”, IEEE Transactions on Computers, 37:6 (1988), pp. 739–743.
  12. Joshi G., Soljanin E., Wornell G.. “Queues with redundancy: Latency-cost analysis”, ACM SIGMETRICS Performance Evaluation Review, 43:2 (2015), pp. 54–56.
  13. Joshi G.. Efficient redundancy techniques to reduce delay in cloud systems, Massachusetts Institute of Technology, 2016 URL https://www.rle.mit.edu/sia/wp-content/uploads/2016/11/2016-joshi-phd.pdf.
  14. Joshi G., Soljanin E., Wornell G.. “Efficient redundancy techniques for latency reduction in cloud systems”, ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2:2 (2017), 12, 30 pp.
  15. Asmussen S.. Applied Probability and Queues, SMAP, vol. 51, Springer, 2003, ISBN 978-0-387-00211-8, 452 pp.
  16. Balakrishnan N.. “Permanents, order statistics, outliers and robustness”, Revista Matematica Complutense, 20:1 (2007), pp. 7–107.
  17. Balakrishnan N., Joshi P. C.. “A note on order statistics from Weibull distribution”, Scandinavian Actuarial Journal, 1981:2 (1981), pp. 121–122.
  18. Whitt W.. “Comparing counting processes and queues”, Advances in Applied Probability, 13:1 (1981), pp. 207–220.
  19. Blanchet J., Pei Y., Sigman K.. “Exact sampling for some multi-dimensional queueing models with renewal input”, Advances in Applied Probability, 51:4 (2019), pp. 1179–1208.
  20. Bladt M., Nielsen B.. Matrix-Exponential Distributions in Applied Probability, PTSM, vol. 81, Springer US, Boston, MA, 2017, ISBN 978-1-4939-7047-6, 749 pp.
  21. Rumyantsev A., Chakravarthy S.. “Matrix-exponential distributions in applied probability”, Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development, BOINC:FAST 2017 (August 28–September 01, 2017, Petrozavodsk, Russia), CEUR Workshop Proc., vol. 1973, 2017, pp. 27–34.
  22. Buchholz P., Kriege J., Felko I.. Input Modeling with Phase-Type Distributions and Markov Models. Theory and Applications, SpringerBriefs in Mathematics, Springer International Publishing, Cham, 2014, ISBN 978-3-319-06673-8, xii+127 pp.
  23. Harchol-Balter M.. Performance Modeling and Design of Computer Systems: Queueing Theory in Action, Cambridge University Press, Cambridge, 2013, ISBN 9781107027503, 574 pp.
  24. Feitelson D.. Workload Modeling for Computer Systems Performance Evaluation, Cambridge University Press, Cambridge, 2015, ISBN 9781139939690.
  25. Malik H. J.. “Exact moments of order statistics from the Pareto distribution”, Scandinavian Actuarial Journal, 1966:3–4 (1966), pp. 144–157.
  26. Huang J. S.. “A note on order statistics from Pareto distribution”, Scandinavian Actuarial Journal, 1975:3 (1975), pp. 187–190.
  27. Daley D. J., Goldie C. M.. “The moment index of minima (II)”, Statistics & Probability Letters, 76:8 (2006), pp. 831–837.
  28. Daley D. J.. “The moment index of minima”, Journal of Applied Probability, 38, Issue A: Probability, Statistics and Seismology (2001), pp. 33–36.
  29. Scheller-Wolf A., Vesilo R.. “Sink or swim together: necessary and sufficient conditions for finite moments of workload components in FIFO multiserver queues”, Queueing Systems, 67:1 (2011), pp. 47–61.
  30. Hardy G. H., Littlewood J. E., Polya G.. Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1991, 340 pp.
  31. Lieblein J.. “On moments of order statistics from the Weibull distribution”, Ann. Math. Statist., 26:2 (1955), pp. 330–333.
  32. Sultan K. S., Moshref M. E.. “Moments of order statistics from Weibull distribution in the presence of multiple outliers”, Communications in Statistics – Theory and Methods, 43:10–12 (2014), pp. 2214–2226.
  33. Rinne H.. The Weibull Distribution. A Handbook, Chapman and Hall/CRC, New York, 2009, ISBN 9780367577469, 808 pp.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».