Delay, stability, and resource tradeoffs in large distributed service systems
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/124124 |
| _version_ | 1826204418733768704 |
|---|---|
| author | Zubeldía Suárez, Martín. |
| author2 | David Gamarnik and John N. Tsitsiklis. |
| author_facet | David Gamarnik and John N. Tsitsiklis. Zubeldía Suárez, Martín. |
| author_sort | Zubeldía Suárez, Martín. |
| collection | MIT |
| description | This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. |
| first_indexed | 2024-09-23T12:54:46Z |
| format | Thesis |
| id | mit-1721.1/124124 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:54:46Z |
| publishDate | 2020 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1241242020-03-10T03:16:34Z Delay, stability, and resource tradeoffs in large distributed service systems Zubeldía Suárez, Martín. David Gamarnik and John N. Tsitsiklis. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019 Cataloged student-submitted from PDF version of thesis. Includes bibliographical references (pages 161-164). This thesis addresses fundamental tradeoffs in the design of dispatching policies in large-scale distributed service systems, motivated by examples such as cloud computing facilities and multi-core processors. A canonical framework for modeling such systems is provided by a parallel queueing model with n servers, where service requests arrive stochastically over time as a single stream of jobs of rate proportional to n, and where a central controller is responsible for all decisions. The central controller makes decisions based on limited information about the state of the queues, which is conveyed through messages from servers to the dispatcher, and stored in a limited local memory. Our objective is to understand the best possible performance of such systems (in terms of stability region and delay) and to propose optimal policies, with emphasis on the asymptotic regime when both the number of servers and the arrival rate are large. We study the tradeoffs between the resources available to the controller (memory size and message rate) and the achievable queueing delay performance and stability region of resource constrained dispatching policies. Our main findings are: 1. Queueing delay vs. resources tradeoff. We propose a family of dispatching policies, indexed by the size of their memories and by the average message rate, and show that the expected queueing delay vanishes as n --> [infinity symbol] when either (i) the number of memory bits is of the order of log(n) and the message rate grows superlinearly with n, or (ii) the number of memory bits grows superlogarithmically with n and the message rate is at least as large as the arrival rate (Chapter 3). Moreover, we develop a novel approach to show that, within a certain broad class of "symmetric" policies, every dispatching policy with a message rate of the order of n, and with a memory of the order of log(n) bits, results in an expected queueing delay which is bounded away from zero, uniformly as n --> [infinity symbol] (Chapter 4). 2. Stability region vs. resources tradeoff. We propose a dispatching policy that requires a memory size (in bits) of the order of log(n) and an arbitrarily small (but positive) message rate, and show that it is stable for all possible server rates for which the entire system is underloaded. Moreover, we show that within a certain broad class of "weakly symmetric" policies, every dispatching policy with a message rate of the order of o(n²) , and with a memory size that grows sublogarithmically with n, results in a reduced stability region (Chapter 5). by Martín Zubeldía Suárez. Ph. D. Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2020-03-09T18:59:03Z 2020-03-09T18:59:03Z 2019 2019 Thesis https://hdl.handle.net/1721.1/124124 1142634812 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 164 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Zubeldía Suárez, Martín. Delay, stability, and resource tradeoffs in large distributed service systems |
| title | Delay, stability, and resource tradeoffs in large distributed service systems |
| title_full | Delay, stability, and resource tradeoffs in large distributed service systems |
| title_fullStr | Delay, stability, and resource tradeoffs in large distributed service systems |
| title_full_unstemmed | Delay, stability, and resource tradeoffs in large distributed service systems |
| title_short | Delay, stability, and resource tradeoffs in large distributed service systems |
| title_sort | delay stability and resource tradeoffs in large distributed service systems |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/124124 |
| work_keys_str_mv | AT zubeldiasuarezmartin delaystabilityandresourcetradeoffsinlargedistributedservicesystems |