Probabilistic Analysis of a Network Resource Allocation Algorithm
A distributed algorithm is presented, for allocating a large number of identical resources (such as airline tickets) to requests which can arrive anywhere in a distributed network. Resources, one allocated, are never returned. The algorithm searches sequentially, exhausting certain neighborhoods of...
| Main Authors: | , , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149088 |
| _version_ | 1811088059483029504 |
|---|---|
| author | Fischer, Michael J. Griffeth, Nancy Guibas, Leonidas J. Lynch, Nancy A. |
| author_facet | Fischer, Michael J. Griffeth, Nancy Guibas, Leonidas J. Lynch, Nancy A. |
| author_sort | Fischer, Michael J. |
| collection | MIT |
| description | A distributed algorithm is presented, for allocating a large number of identical resources (such as airline tickets) to requests which can arrive anywhere in a distributed network. Resources, one allocated, are never returned. The algorithm searches sequentially, exhausting certain neighborhoods of the request origin before proceeding to search at great distances. Choice of search direction is made nondeterministically. Analysis of expected response time is simplified by assuming that the search direction is chosen probabilistically, that messages require constant time, that the network is a tree with all leaves at the same distance from the root, and that requests and resources occur only at leaves. It is shown that the response time is approximated by the number of messages of one that are sent during the execution of the algorithm, and that this number of messages is a nondecreasing function of the interarrival time for requests. Therefor, the worst case occurs when requests come in so far apart that they are processed sequentially. The expected time for the sequential case of the algorithm is analyzed by standard techniques. This time is shown to be bounded by a constant, independent of the size of the network. It follows that the expected response time for the algorithm is bounded in the same way. |
| first_indexed | 2024-09-23T13:55:37Z |
| id | mit-1721.1/149088 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:55:37Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490882023-03-30T03:34:20Z Probabilistic Analysis of a Network Resource Allocation Algorithm Fischer, Michael J. Griffeth, Nancy Guibas, Leonidas J. Lynch, Nancy A. A distributed algorithm is presented, for allocating a large number of identical resources (such as airline tickets) to requests which can arrive anywhere in a distributed network. Resources, one allocated, are never returned. The algorithm searches sequentially, exhausting certain neighborhoods of the request origin before proceeding to search at great distances. Choice of search direction is made nondeterministically. Analysis of expected response time is simplified by assuming that the search direction is chosen probabilistically, that messages require constant time, that the network is a tree with all leaves at the same distance from the root, and that requests and resources occur only at leaves. It is shown that the response time is approximated by the number of messages of one that are sent during the execution of the algorithm, and that this number of messages is a nondecreasing function of the interarrival time for requests. Therefor, the worst case occurs when requests come in so far apart that they are processed sequentially. The expected time for the sequential case of the algorithm is analyzed by standard techniques. This time is shown to be bounded by a constant, independent of the size of the network. It follows that the expected response time for the algorithm is bounded in the same way. 2023-03-29T14:26:08Z 2023-03-29T14:26:08Z 1985-06 https://hdl.handle.net/1721.1/149088 MIT-LCS-TM-278 application/pdf |
| spellingShingle | Fischer, Michael J. Griffeth, Nancy Guibas, Leonidas J. Lynch, Nancy A. Probabilistic Analysis of a Network Resource Allocation Algorithm |
| title | Probabilistic Analysis of a Network Resource Allocation Algorithm |
| title_full | Probabilistic Analysis of a Network Resource Allocation Algorithm |
| title_fullStr | Probabilistic Analysis of a Network Resource Allocation Algorithm |
| title_full_unstemmed | Probabilistic Analysis of a Network Resource Allocation Algorithm |
| title_short | Probabilistic Analysis of a Network Resource Allocation Algorithm |
| title_sort | probabilistic analysis of a network resource allocation algorithm |
| url | https://hdl.handle.net/1721.1/149088 |
| work_keys_str_mv | AT fischermichaelj probabilisticanalysisofanetworkresourceallocationalgorithm AT griffethnancy probabilisticanalysisofanetworkresourceallocationalgorithm AT guibasleonidasj probabilisticanalysisofanetworkresourceallocationalgorithm AT lynchnancya probabilisticanalysisofanetworkresourceallocationalgorithm |