Backlogged computing work exchange

• US 10,366,358 B1
• Filed: 12/19/2014
• Issued: 07/30/2019
• Est. Priority Date: 12/19/2014
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roth, Gregory Branchek, Behm, Bradley Jeffery
• Primary Examiner(s): Kamran, Mehran
• Application Number:
  US14/577,693
• Time in Patent Office: 1,684 Days
• Field of Search: 718102
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

A method and apparatus for providing a backlogged computing work exchange are provided. In the method and apparatus, a computer system receives a request, whereby satisfaction of the request requires enqueuing computing work, The computer system determines a queued computing work quota of a plurality of queued computing work quotas for use in enqueuing the computing work and submits the request for execution, whereby the request is associated with a second client and the queued computing work quota of the plurality of queued computing work quotas is associated with a first client different from the second client.

Claims

1. A computer-implemented method, comprising:

identifying a total capacity for a computing service, the total capacity representing a maximum amount of computing work pending execution by one or more computing resources and is dynamically configured based at least in part on submission times associated with computing work pending execution by one or more computing resources that has not exceeded a time limit;

allocating a first portion of the total capacity to a first client, a subset of the first portion being reallocatable from the first client to a second client;

obtaining a request from the second client, satisfaction of the request is associated with a capacity that exceeds a second portion of the total capacity;

generating a determination that processing of the request complies with a set of conditions on exchange of the subset of the first portion of the total capacity to the second client, the set of conditions comprises a condition that is satisfied by;

trading the subset of the first portion with the second client for a monetary amount and reallocating the subset of the first portion to the second client for a duration of an interval of time; and

trading for another portion of the total capacity associated with the second client to be allotted to the first client at a future time; and

processing the request based at least in part on the determination.

2. The computer-implemented method of claim 1, further comprising:

enqueuing one or more computing tasks associated with the request as a result of accepting the request, the one or more computing tasks being enqueued pending execution by the one or more computing resources.

3. The computer-implemented method of claim 1, wherein the monetary amount comprises tokens that can be exchanged for portions of the total capacity.

4. The computer-implemented method of claim 1, further comprising:

obtaining an ask offer from the first client, the ask offer specifying a first consideration to be received by the first client in exchange for reallocating the subset of the first portion of the total capacity to another client;

obtaining a bid offer from the second client, the bid offer specifying a second consideration to be provided by the second client in exchange for reallocating the subset of the first portion of the total capacity to the second client; and

determining that the subset of the first portion is reallocated to the second client is performed as a result of matching the ask offer with the bid offer.

5. A system, comprising:

one or more processors; and

memory to store executable instructions that, if executed by the one or more processors, cause the system to;

obtain a request, from a second client, satisfaction of the request requiring enqueuing computing work;

determine a queued computing work quota for a first client of a plurality of queued computing work quotas for use in enqueuing the computing work, wherein the queued computing work quota is dynamically configured based at least on part on queued computing work submission times not exceeding a time limit;

generate a determination that processing of the request complies with a set of conditions on exchange of a portion of the queued computing work quota from the first client to the second client, the set of conditions comprises a condition that is satisfied by;

trade the portion of the queued computing work quota with the second client for a monetary amount and reallocate the portion of the queued computing work quota to the second client for a duration of an interval of time; and

trade for another portion of the queued computing work quota associated with the second client to be allotted to the first client at a future time; and

process the request, based at least in part on the determination, for execution.

6. The system of claim 5, wherein the instructions further cause the system to:

reallocate the portion of the queued computing work quota of the plurality of queued computing work quotas from the first client to the second client as a result of the portion of the queued computing work quota being traded from the first client to the second client and credit the first client with the monetary amount.

7. The system of claim 6, wherein the portion of the queued computing work quota is traded from the first client to the second client in exchange for another portion of a queued computing work quota to be reallocated from the second client to the first client.

8. The system of claim 5, wherein the instructions further cause the system to:

obtain a bid offer for the queued computing work quota; and

obtain an ask offer for the queued computing work quota.

9. The system of claim 8, wherein the instructions further cause the system to:

reallocate the queued computing work quota on a condition that the bid offer is matched with the ask offer.

10. The system of claim 8, wherein:

the bid offer indicates a monetary amount to be obtained in exchange for the queued computing work quota; and

the instructions further cause the system to credit the monetary amount to the first client as a result of matching the bid offer with the ask offer.

11. The system of claim 8, wherein the instructions further cause the system to:

obtain the request by obtaining the bid offer in connection with the request.

12. A non transitory computer readable storage medium comprising executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

obtain, from a first client, a request, fulfillment of the request requiring enqueuing computing work pending execution;

determine an available enqueued computing work capacity associated with a second client for use in enqueuinq the computing work pending execution, wherein the available enqueued computing work capacity is dynamically configured based at least on part on submission times associated with enqueueinq computing work pending execution not exceeding a time limit;

reallocate a portion of the enqueued computing work capacity associated with a second client to the first client, after an expiration of a duration of time, as a result of obtaining an indication that the portion of the enqueued computing work capacity is traded from the first client to the second client for a monetary amount; and

cause the request to be fulfilled, based at least in part on determining that processing of the request complies with a set of conditions on exchange of the portion of the enqueued computing work capacity from the second client to the first client; and

fulfillment of the request utilizing the portion of enqueued computing work capacity for enqueuing the computing work.

13. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to accept the request as a result of determining that an available enqueued computing work capacity associated with the first client that includes the portion of the enqueued computing work capacity is sufficient for enqueuing the computing work.

14. The non-transitory computer-readable storage medium of claim 13, wherein the request is accepted synchronously in relation to obtaining the request.

15. The non-transitory computer-readable storage medium of claim 12, wherein the instructions that cause the computer system to reallocate the portion of the enqueued computing work capacity further include instructions that cause the computer system to reallocate the portion of the enqueued computing work capacity for a second duration of time.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to allocate the portion of the enqueued computing work capacity back to the second client after the expiration of the second duration of time.

17. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to obtain, from the first client, a bid offer for the portion of the enqueued computing work capacity indicating a monetary fee to be paid in exchange for the portion of the enqueued computing work capacity.

18. The non-transitory computer-readable storage medium of claim 17, wherein the instructions that cause the computer system to reallocate the portion of the enqueued computing work capacity further include instructions that cause the computer system to reallocate the portion of the enqueued computing work capacity as a result of matching the bid offer with an ask offer of the second client.

19. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to:

maintain an association between the first client and a first enqueued computing work capacity available to the first client; and

increase the first enqueued computing work capacity by the portion of the enqueued computing work capacity as a result of the portion of the enqueued computing work capacity being traded from the second client to the first client.