Patent ID: 8150994
Filing Date: 2012-04-03
Classification: G06Q,H04L

Abstract:
1. A method for implementing workflow in a distributed system, the method comprising: performing workflow in a distributed system comprising a plurality of workflow stages operating in sequence to perform work associated with a given task, wherein each stage of the system performs a portion of the work associated with the given task and consumes one or more resources in performing such work; and performing a workflow control process to control workflow in the distributed system, wherein performing a workflow control process comprises: each stage monitoring its own capacity to perform work by using a sliding window to monitor a first number of items of work transmitted to the each stage during the sliding window and a second number of items of work processed by the each stage during the sliding window and to predict a rate of new work received by the each stage and a rate at which work is being completed by the each stage, the monitored capacity to perform work is based on the rate at which work is being completed by the each stage and an overdrive factor such that the monitored capacity to perform work is greater than the rate at which work is being completed, the monitoring performed by the stage comprising: where Ni is the first number of items of work received by the stage; Di is a duration over which Ni items of work were received by the stage; No is the second number of items of work processed by the stage; Do is a duration over which No items were processed by the stage; Of is the overdrive factor; and Ns is a number of items of work about to be received into the stage, wherein each of the stages of the system may perform throttling actions independently to improve the overall throughput of the system.