1. A method, comprising: performing, at a particular node of a rewriting decisions tier of a stateful network flow management service, a plurality of metadata update iterations, wherein a particular metadata update iteration of the plurality of metadata update iterations comprises: substituting, within a metadata collection used for packet rewriting decisions at the particular node, a first local decisions summary with a second local decisions summary, wherein the second local decisions summary comprises indications of one or more packet rewriting decisions made at the particular node for one or more network flows subsequent to a set of packet rewriting decisions indicated in the first local decisions summary, wherein a particular network flow is distinguishable from other network flows by a combination of one or more of: a network protocol, a source network address, a source network port, a destination network address and a destination network port; substituting, within the metadata collection, a first flow state summary with a second flow state summary, wherein the second flow state summary corresponds to one or more packet rewriting decision notifications received at a different tier of the stateful network flow management system from the rewriting decisions tier subsequent to a set of packet rewriting decision notifications corresponding to the first flow state summary; initializing, within the metadata collection, a third local decisions summary to be used to store indications of additional packet rewriting decisions made at the particular node; storing, within the metadata collection, a third flow state summary received from the different tier, wherein the third flow state summary corresponds to one or more additional packet rewriting decision notifications received at the different tier subsequent to packet rewriting decision notifications corresponding to the second flow state summary; and determining, at the particular node of the rewriting decisions tier using an aggregation of at least a portion of the metadata collection, at least one element of a rewrite entry to be used to generate, in accordance with a packet processing requirement of a client, one or more transformed packets corresponding to one or more received packets.