Stochastic control optimization for sender-based flow control in a distributed stateful messaging system
First Claim
1. A computer implemented method for generating a propagation policy for controlling message flow in an information dissemination environment, the computer implemented method comprising:
- identifying a Markov model having one state per staleness value of data;
determining state transition probabilities in the Markov model for a decision to send a new message comprising updates of data to information subscribers and for a decision to withhold the new message from the information subscribers using expected message rates from a information provider;
using a cost function to annotate each state transition in the Markov model with a state transition cost for the decision to send the new message and the decision to withhold the new message;
determining a propagation policy for each state, wherein the propagation policy specifies whether to send the new message to the information subscribers or to withhold the new message from information subscribers; and
deploying the propagation policy.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and system for controlling message flow in distributed stream processing. State transition probabilities in a Markov model having one state per staleness value of data are determined for sending or withholding updates of data to subscribers using expected message rates from an information provider. A cost function annotates each state transition in the model with a state transition cost for each decision to “send” or “withhold”. A propagation policy specifying whether to send or withhold the message is determined for each state. The propagation policy is then deployed. If a new message comprising an update of data is received during a lapsed time unit, a staleness value of the data held by subscribers is increased. The propagation policy is used to determine whether to send or withhold the message. If the message should be sent, the message is propagated and the staleness value of the data is reset.
14 Citations
18 Claims
-
1. A computer implemented method for generating a propagation policy for controlling message flow in an information dissemination environment, the computer implemented method comprising:
-
identifying a Markov model having one state per staleness value of data; determining state transition probabilities in the Markov model for a decision to send a new message comprising updates of data to information subscribers and for a decision to withhold the new message from the information subscribers using expected message rates from a information provider; using a cost function to annotate each state transition in the Markov model with a state transition cost for the decision to send the new message and the decision to withhold the new message; determining a propagation policy for each state, wherein the propagation policy specifies whether to send the new message to the information subscribers or to withhold the new message from information subscribers; and deploying the propagation policy. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer implemented method for controlling message flow in distributed stream processing, the computer implemented method comprising:
-
responsive to a lapse of a time unit, determining whether a new message comprising an update of data was received from an information provider during the time unit; responsive to a determination that a new message was received during the time unit, increasing a staleness value of data held by information subscribers and associated with the new message; determining whether to send or withhold the new message to the information subscribers based on a propagation policy; and responsive to a determination to send the new message, propagating the new message toward the information subscribers and resetting the staleness value of the data held by the information subscribers and associated with the new message. - View Dependent Claims (8, 9)
-
-
10. A computer program product for generating a propagation policy for controlling message flow in an information dissemination environment, the computer program product comprising:
-
a non-transitory computer usable medium having computer usable program code tangibly embodied thereon, the computer usable program code comprising; computer usable program code for identifying a Markov model having one state per staleness value of data; computer usable program code for determining state transition probabilities in the Markov model for a decision to send a new message comprising updates of data to information subscribers and for a decision to withhold the new message from the information subscribers using expected message rates from a information provider; computer usable program code for using a cost function to annotate state transitions in the Markov model with a state transition cost for the decision to send the new message and the decision to withhold the new message; computer usable program code for determining a propagation policy for each state, wherein the propagation policy specifies whether to send the new message to the information subscribers or to withhold the new message from information subscribers; and computer usable program code for deploying the propagation policy. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A computer program product for controlling message flow in distributed stream processing, the computer program product comprising:
-
a non-transitory computer usable medium having computer usable program code tangibly embodied thereon, the computer usable program code comprising; computer usable program code for determining, in response to a lapse of a time unit, whether a new message comprising an update of data was received from an information provider during the time unit; computer usable program code for increasing, in response to a determination that a new message was received during the time unit, a staleness value of data held by information subscribers and associated with the new message; computer usable program code for determining whether to send or withhold the new message to the information subscribers based on a propagation policy; and computer usable program code for propagating the new message toward the information subscribers and resetting the staleness value of the data held by the information subscribers and associated with the new message in response to a determination to send the new message. - View Dependent Claims (17, 18)
-
Specification