In Proc. ACM SIGCOMM '99
One-line summary: A very nice paper that attempts to define and model soft state, as well as present a soft-state protocol with tunable degrees of reliability. The paper also introduces the term "vertically robust" for applications that accommodate inconsistency across distributed components throughout their design.
The way they model soft data is a changeable table of {key, value} pairs. The owner of the table periodically publishes some of these tuples over a lossy channel. Subscribers listen to these announcements and update their own versions of the table. Each tuple has an associated timer and, if no update is received for that tuple within the time limit, the tuple expires from the receiver's table.
The consistency metric c(k,t) is defined as the probability that, at time t, the tuple corresponding to key k is the same at both sender and receiver. The model consists of a number of other metrics and formulae that are detailed in the paper. Based on the model they derive graphs evidencing how the expected value of consistency decreases with channel loss rate, how a decreasing loss rate makes the percentage of wasted bandwidth go up, due to redundant updates.
Observing that, with normal "open-loop" soft state refresh (where the sender has no feedback from the receiver), a lot of channel bandwidth can be wasted with unnecessary updates, they look at a two-queue model, where one (hot) queue is used for first-time transmissions and a second one (cold) is used for retransmissions. They perform simulations that show consistency improves and then levels off as we increase bandwidth assigned to the hot queue. Queueing delay improves as bandwidth allocated to the cold queue is increased.
Lastly, they talk about SSTP (soft-state protocol) in which they apply the above model; SSTP uses information on average packet loss rate, the app's consistency target, and total available bandwidth to tune its transmissions. They add NACKs as well, so that the receiver can inform the sender of perceived losses. SSTP allows the application to have a hierarchical data model, by preserving an index of pointers to the app's data. They compute at each level of the hierarchy a hash of the data in the corresponding subtree and retransmissions consist of sending the root hash, which the client can compare against its own. If inconsistent, it tells the publisher, which then sends the hashes of the root's children. The receiver compares those and tells the publisher which one is inconsistent, so then the publisher sends it the hashes of that node's children, etc. Once they figure out which data needs to be updated, the publisher updates the receiver. One cool thing is that the receiver may not care about a particular subtree's updates; in that case, if it sees the hash is incosistent, it can opt to simply ignore it for the time being.
If this model is to be used for network environments only, many of the results depicted in graphs are not necessarily interesting (e.g., a rapid change at 90% loss rate is not particularly relevant).