Subject: Re: Entry deletion and distributed systems

From: Asbjørn Ulsberg <[email-masked]>
Date: Mon, 13 Sep 2004 20:36:40 +0200

On Mon, 13 Sep 2004 12:07:42 +0200, Danny Ayers <[email-masked]>  
wrote:

> If someone posts an entry and then later retracts it a local system
> can handle this ok, but distributing the retraction may not be quite
> so straightforward. Maybe it is feasible to distribute the entry
> identifier tagged as 'withdrawn' or even 'expired', but I suspect it
> may not be sensible to make anything of that at a global level, as it
> could never be 100% reliable and the inclusion of such a system in the
> specs may lead to unrealistic expectations.

This is exactly as NNTP has done it for years. First you post a message,  
then you cancel it by sending a new message. The difference is that NNTP  
cancels are afaik not standard, and thus a bit hack-ish. I think most  
cancel messages on NNTP are done through sending a message with the same  
Message-ID to the newsgroupd ctrl.cancel, but I'm not 100% sure.

Either way, the idea of the concept is identical. When you've first sent  
out a message, you need to send out a new message to retract or cancel it.  
In Outlook this works fine before the message is read, but when it is,  
even in that closed environment, there's trouble.

> In other words, I'd suggest that rather than having the logic:
>
> Post => EntryExists
> Post & PostRetraction => !EntryExists
>
> We use:
>
> Post => EntryExists
> Post & PostRetraction => EntryExists & PostRetraction (and that's all!)

Sounds fair. If the user somehow doesn't find out that the entry is  
retracted, maybe it should be possible to query the originating server for  
the entry's status? Such a query can be executed before the entry is  
replied to, for instance.

If we allow for and recommend single-entry documents, the status request  
can simply just be a GET to an entry's 'atom:link[@rel = "about"]/@href'.  
The returned entry can then be an updated version of the one the user is  
looking at, a retracted version, or whatever.

> - it's up to the end-user application to deal with that as it sees
> fit. So generally (web-wide) entries will only expire by get old and
> slipping into obscurity, not through any explicit (un)assertion.

Yep. It will be impossible to control this no matter how we attack it,  
imho.

-- 
Asbjørn Ulsberg    -=|=-     http://virtuelvis.com/quark/
«He's a loathsome offensive brute, yet I can't look away»

---

From: "Bob Wyman" <[email-masked]>
Date: Mon, 13 Sep 2004 17:51:26 -0400

Asbjørn Ulsberg wrote:
> This is exactly as NNTP has done it for years. First you post a
> message,  then you cancel it by sending a new message. The
> difference is that NNTP cancels are afaik not standard, and
> thus a bit hack-ish. I think most cancel messages on NNTP are
> done through sending a message with the same Message-ID to the
> newsgroupd ctrl.cancel, but I'm not 100% sure.
	This method only works as well for NNTP as it does because NNTP is a
"topic-based" system. i.e. what you subscribe to in NNTP is a "topic" or
"newsgroup". Thus, when a cancellation goes out, you'll get a message as
long as you're still subscribed to the group. However, this method does
*not* work in systems that rely on content-based filtering. In content based
systems, the only way you know who to deliver a message to is by looking at
attributes of the message. Thus, for a cancellation message to be delivered,
it would have to contain the same content as the message that it was
canceling. This, for obvious reasons is not something folk are going to want
to do.
	The only way to do cancellations in a content-based system is for
the matching system to remember to whom it has sent messages in the past.
Doing this can be exceptionally expensive and poses a number of privacy
issues.
	Don't assume that what works for a topic-based system like NNTP will
continue to work in a future where I believe we'll have much more
content-based, not topic-based, filtering going on.

		bob wyman

---

From: Asbjørn Ulsberg <[email-masked]>
Date: Tue, 14 Sep 2004 08:11:22 +0200

On Tue, 14 Sep 2004 07:55:18 +0200, Asbjørn Ulsberg  
<[email-masked]> wrote:

> Yes, it does. That's why I thought Eric's proposal was a good one [...]

Bah. That should have been Danny, not Eric. Sorry.

---

From: Asbjørn Ulsberg <[email-masked]>
Date: Tue, 14 Sep 2004 07:55:18 +0200

On Mon, 13 Sep 2004 17:51:26 -0400, Bob Wyman <[email-masked]> wrote:

> "topic-based" system.

Does it really work well for NNTP? That was news to me. ;-) Seriously, I  
think the mechanism is flawed. It isn't even afaik a standard way to do  
it. Plus, many servers and even clients don't respect a cancel, so often,  
it has absolutely no effect trying to cancel a message.

> i.e. what you subscribe to in NNTP is a "topic" or "newsgroup". Thus,
> when a cancellation goes out, you'll get a message as long as you're
> still subscribed to the group.

Isn't this exactly the same as subscribing to an Atom feed (be it that the  
feed can be about a given topic or not)?

> However, this method does *not* work in systems that rely on  
> content-based
> filtering. In content based systems, the only way you know who to deliver
> a message to is by looking at attributes of the message.

What content are you referring to here, exactly? Data? Metadata?  
Meta-metadata?

> Thus, for a cancellation message to be delivered, it would have to
> contain the same content as the message that it was canceling.

Matching the ID and sender's authinfo should be more than enough, no?

> This, for obvious reasons is not something folk are going to want to do.

Uhm, okay. I'm not sure why not.

> The only way to do cancellations in a content-based system is for the
> matching system to remember to whom it has sent messages in the past.

Yes, it does. That's why I thought Eric's proposal was a good one, since  
it basically made it optional to implement cancellation in all links in  
the chain.

> content-based, not topic-based, filtering going on.

I still don't know what the difference between topic- and content-based  
systems are, but I agree that any mechanism trying to do cancellation in a  
distributed network messaging system is bound to fail partially or maybe  
even completely.

---

From: "Bob Wyman" <[email-masked]>
Date: Tue, 14 Sep 2004 12:02:57 -0400

Asbjørn Ulsberg wrote:
> I still don't know what the difference between topic- and 
> content-based systems are,
	Topic-based systems are those in which the unit of selection which
is used to determine if messages should be sent to you is the "topic" over
which or to which a message is published. Thus, if you create a topic-based
subscription to my blog at http://bobwyman.pubsub.com/ you will receive
*all* entries that I publish. Similarly, if you subscribe to an NNTP
newsgroup, such as comp.lang.c, then you would receive all messages that are
published to the comp.lang.c newsgroup.
	Content-based systems are those that use elements of the content of
published messages as the units of selection. Thus, if you subscribed to all
messages that mention "Asbjørn Ulsberg" you would receive all such messages
no matter which "topic", blog, or newsgroup they were published to. 
	Topic-based systems select messages based on the channel to which
they are published. Content-based systems select messages based on the
attributes of the messages themselves -- independent of what channel they
are published to. In a content-based system, "topic" is just another
attribute. Of course, it should be obvious that one can implement a hybrid
system that allows you to create a "content-based subscription" that selects
items from a particular topic. i.e. (All messages published to "atom-syntax"
that mention "Asbjørn Ulsberg").
	The distinction between "topic-based" and "content-based" systems is
of critical importance when designing mechanisms for "entry deletion" -- the
subject you were discussing...
	In a topic-based system, all subscribers to a topic receive *all*
messages sent to the topic -- whether those messages are new messages or
cancellations. Thus, to distribute a "cancel" message, all you have to do is
send it to the topic. Then, unless some people have unsubscribed since they
received the message you're trying to cancel, you can have confidence that
everyone who received the original message will also receive the
cancellation. Of course, if some people have subscribed to the topic since
you sent the message being cancelled, you might deliver the cancellation to
some folk who don't have the original -- but that is not a big problem since
the rate of cancellations per topic is usually fairly low for most
applications.
	In a content-based system, messages are only delivered based on
their content. Thus, to "address" a message to that set of subscribers that
received a previous message, you need to ensure that the content of the
second message closely matches the content of the first. For instance, if
you had a content-based subscription to all mentions of 'Asbjørn Ulsberg',
then the way to get a cancel message to you would be to ensure that the
cancel message contains the phrase 'Asbjørn Ulsberg'. Unfortunately, this
isn't terribly practical in general since you can't really anticipate all of
the attributes of the content that someone might have subscribed to.
Basically, you would have to resend exactly the original message with some
additional data that said "cancel this." Technically, this would generally
work; however, since people are usually trying to remove content when they
do a cancellation, they aren't going to be happy to have to resend the
offending message. In some cases, where the messages might contain libelous
content, there might even be legal problems with re-sending such a message
even if the intent of resending it was to cancel it. I would not, for
instance, want to send a message that said "Asbjørn Ulsberg is a thief!" in
order to cancel a message in which I had said "Asbjørn Ulsberg is a thief!"
	In order to do cancellations in a content-based system, the system
needs to remember to whom it sent all previous messages and it must have a
means of uniquely identifying all messages. (i.e. atom:id...) Then, when the
matching system sees a cancellation, it would forward an "out-of-band"
cancellation message, which identifies the cancelled message by id, to
everyone who received the original. I’m sure you can see the problem here...
If the matching system has a large number of subscribers, or if it processes
a large number of messages, or both, the amount of state that must be
maintained in order to process cancellations can become very burdensome. In
addition, there is the question of privacy. Many people will not be pleased
to know that there is a system somewhere that keeps track of all messages
that were sent to them. Someone might, for instance, find it interesting to
inspect the list of messages sent to you and use the knowledge gained for
purposes of which you don't approve...
	Try to imagine a system like PubSub.com or Google implementing a
cancellation system... Can you imagine what it would take for Google to
remember all the documents you had retrieved via Google (even if only
limited to the Google cache) and then sending you a message whenever one of
them was "cancelled?" It is highly unlikely that such a system could be
implemented at reasonable cost and, if implemented, it is probably something
that we should argue against because of the privacy issues.
	The alternative to the methods above is that content-based systems
would send cancellation messages to ALL subscribers -- not matter what they
had subscribed to. However, while that solves the addressing problems and it
solves the privacy problems, it creates a new problem in that it is likely
that the vast majority of clients that received the cancellation messages
would not have received the original message. Vast quantities of bandwidth
would be wasted as a result and an opening for a denial-of-service attack
would be created... Anyone could, by simply "canceling" a message, ensure
that every user of the system received a message. Thus, you could organize a
"cancellation flood" that crippled the system by generating a large number
of cancellations -- each of which would be multiplied by the number of
subscribers to the entire system. (Imagine every user of Google receiving a
"cancel" message because some teen-ager decided to delete a blog entry about
her boy friend...)
	Please note that although the problems with canceling messages
distributed via content based systems are clear, to a great extent the same
problem exists for topic-based systems. A truly effective cancellation
system would be able to handle cancellations of messages being sent to
people who had cancelled their topic-based subscriptions after the original
message was sent but before the cancellation was sent. Since these people
wouldn't get the cancellation via their outstanding subscriptions, the
topic-based system would have to remember to whom it had sent messages and
then send "out-of-band" messages to those users. Some optimization could be
made by sending one cancellation to the "topic" and thus to all current
subscribers and then doing something else for people who had cancelled
subscriptions after the original was sent... (You would have to remember
when people cancelled their subscriptions and when each message had been
sent.) However, that is still way to complicated to imagine it being
supported very widely.
	Message cancellation is a really tough problem and should not be
discussed casually. It isn't easy and if badly implemented can result in
real problems since people will expect that the system will work better than
it can. Don't falsely raise expectations. People really should learn to
accept that once they have sent a message, they have lost control over it.
	I first dealt with the message cancellation issue almost 25 years
ago when building ALL-IN-1, one of the first commercial email systems. Since
then, I've probably seen hundreds of proposals for how to implement message
cancellation systems and I've seen many, many people speak of how much they
want a useful system to be implemented. However, I don't believe that in all
these years I've seen anyone propose anything which can work in more than a
small percentage of cases. This is not an easy problem. Let's try to focus
on problems that we're more likely to solve...

		bob wyman

---

From: Mark Baker <[email-masked]>
Date: Tue, 14 Sep 2004 13:08:12 -0400

On Tue, Sep 14, 2004 at 12:02:57PM -0400, Bob Wyman wrote:
> People really should learn to

+1.  'nuf said, I think.

Mark.
-- 
Mark Baker.   Ottawa, Ontario, CANADA.        http://www.markbaker.ca

---

From: Asbjørn Ulsberg <[email-masked]>
Date: Wed, 15 Sep 2004 08:27:15 +0200

On Tue, 14 Sep 2004 12:02:57 -0400, Bob Wyman <[email-masked]> wrote:

> is used to determine if messages should be sent to you is the "topic"
> [...]
> published messages as the units of selection.

Okay, I get it. What puzzled me was that it seemed to me that you thought  
Atom and RSS was purely a content-based system, while NNTP was a  
topic-based one. I think they conflate and mix pretty well, depending on  
what type of client you use.

I use Opera for both RSS and NNTP subscription, and while the  
subscriptions themselves are topic-based, I use content-based filtering to  
apply some kind of scoring to them.

> People really should learn to accept that once they have sent a
> message, they have lost control over it.

I totally agree with everything you write, especially this sentence.

That's why I think Danny's proposal is a good one. With his proposal, no  
one will expect the message to be gone from all subscriber's clients, but  
they can hope that the subscriber will be notified one way or another that  
the entry has «expired» or something similar.

---

From: "Bob Wyman" <[email-masked]>
Date: Wed, 15 Sep 2004 02:48:17 -0400

Asbjørn Ulsberg wrote:
> subscriptions themselves are topic-based, I use content-based
> filtering to apply some kind of scoring to them.
	Yes, this business of subscribing to a topic and then having
your client do the filtering is often used to create the appearance of a
content-based system. What is happening is that complexity and
processing requirements are being pushed out to the client at the
expense of network resources. In such a system, you can get away with
reasonably effective "deletions" since even though it "feels"
content-based to the user, it is actually a topic-based system at the
message distribution level. This particular layering and pushing of the
filtering task to clients is often implemented in LAN environments where
network bandwidth is cheap and plentiful. For instance, look at the
publish/subscribe systems based on TIBCO software -- that stuff even
uses broadcast packets! However, this approach just doesn't work at
Internet Scale.

> What puzzled me was that it seemed to me that you thought  
> topic-based one.
	I think you're talking about "apples and oranges." RSS and Atom
are formats. Thus, they are neither content-based nor topic-based even
though things encoded using RSS or Atom could be passed over either type
of system. On the other hand, NNTP is a protocol for implementing
topic-based systems. RSS and Atom are orthogonal to NNTP.

		bob wyman

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Wed, 15 Sep 2004 12:03:38 +0200

>no matter which "topic", blog, or newsgroup they were published to. 

The difference here is whether the result of a query depends on the
publication, not on the "topic" or the "content" of the available items.
You thus have publication-dependent and publication-independent systems.
This should be obvious as you cannot know the topic of an item without
looking at the content, "published by Bob Wyman" is not a "topic" in the
commonly understood sense of the word.

---

From: "Bob Wyman" <[email-masked]>
Date: Wed, 15 Sep 2004 11:23:59 -0400

Bjoern Hoehrmann wrote:
> The difference here is whether the result of a query depends on
> the publication, not on the "topic" or the "content" of the
> available items. ... This should be obvious as you cannot know the
> topic of an item without looking at the content, "published by
> Bob Wyman" is not a "topic" in the commonly understood sense of
> the word.
	Actually, the "commonly understood sense of the word" isn't relevant
in this context since the distinction between "topic-based" and
"content-based" is one of technical jargon. I didn't invent these terms.
They have been long used by implementers and academics that write about
publish/subscribe technology. 
	I believe the origin of the "topic-based" usage was in old
technology pubsub systems like the TIBCO's TIB/Rendevous which did, in fact,
distribute messages over various "channels" depending on the "topic" of the
message. Thus, you would have one "topic" that was "IBM Stock Price Changes"
and another for "New SEC Reports". Clients would then subscribe to the
appropriate "topic" and then filter out what they didn't want. Similarly,
the old Pointcast system implemented what many called a topic in that you
could subscribe to the "US Sports News" topic... (Note: PointCast wasted
massive amounts of bandwidth because of this approach...)

	I provide below a few references to the literature that demonstrate
the use of these terms as technical jargon:

[1] Hermes: A Distributed Event-Based Middleware Architecture
" Publish/subscribe systems can be divided into topic-based and
content-based systems"
http://doi.ieeecomputersociety.org/10.1109/ICDCSW.2002.1030837

[2] Subscription Summaries for Scalability and Efficiency in
Publish/Subscribe Systems
" The first such systems were based on the concepts of group (also known as
channel-based systems) or subject (also known as topic-based systems)."
http://csdl.computer.org/comp/proceedings/icdcsw/2002/1588/00/15880619abs.ht
m

[3] Implementing A Scalable XML Publish/Subscribe System
Using Relational Database Systems
" The earliest publish/subscribe systems are topic-based.
In these systems, subscribers subscribe to a certain topic
(or group, subject etc.) and all messages published on that topic
are delivered to the subscribers. More recent pub/sub systems
support the content-based paradigm. For a content-based pub/sub
system, each subscriber can register a rule in the system. When a
publisher publishes a message to the system, the system matches
the message with all the registered rules and delivers the message
to the corresponding subscribers. Generally speaking, a content-based
pub/sub system is more flexible and more powerful than a
topic-based pub/sub system."
http://www.research.ibm.com/people/j/jussi/papers/IS/PubSub-SIGMOD2004.pdf

[4] Publish/Subscribe: Patterns and Practices
" Both Broadcast-Based Publish/Subscribe implementations and List-Based
Publish/Subscribe implementations can be broadly categorized as topic-based
because they both use predefined subjects as many-to-many channels.
Publish/Subscribe implementations have recently evolved to include a new
form-Content-Based Publish/Subscribe."
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnpag/html/
despublishsubscribe.asp

[5] The Evolution of Publish/Subscribe Communication Systems
"Pub/sub systems can be classified in two main classes: the topic-based
class (e.g. TIB/Rendezvous [1.11]) and the content-based class (e.g. SIENA
[1.9] and Gryphon [1.3]). In a topic-based system, processes exchange
information through a set of predefined subjects (topics) which represent
many-to-many distinct (and fixed) logical channels. Content-based systems
are more flexible as subscriptions are related to specific information
content and, therefore, each combination of information items can actually
be seen as a single dynamic logical channel."
http://www.dis.uniroma1.it/~virgi/papers/BCV_FUDICO02.pdf

[6] Challenges for Middleware Research, Objectweb
"Most pub-sub systems are topic-based, Subscribers subscribe to a specific
topic and receive events published under this topic. Since topics are
statically defined, this amounts to group multicast, for which scalable
algorithms are known. A more recent pub-sub variant is content-based. This
is much more difficult to implement in a scalable way."
http://www.objectweb.org/phorum/download.php/16,12/MW-Challenges.pdf

[7] Content-based Publish-Subscribe Over Structured P2P Networks
" There are two types of publish/subscribe systems: i) topic based and ii)
content based. Topic based systems are much like newsgroups. Users express
their interest by joining a group (characterized by a topic). Then all
messages related to that topic are broadcasted to all users participating to
the specific group. Content-based systems are preferable as they give
users the ability to express their interest by specifying predicates over
the values of a number of well defined attributes. The matching of
publications (events) to subscriptions (interest) is done based on the
content (values of attributes)."
http://students.ceid.upatras.gr/~aikater/publications/DEBS04.pdf

		bob wyman

---

From: "S. Mike Dierken" <[email-masked]>
Date: Wed, 15 Sep 2004 21:11:25 -0700

> commonly understood sense of the word.
A service could provide that content-based subscription/search-results &
expose it via a single 'topic' or URI based resource. That effectively turns
content-based routing into topic based routing. But, I'm sure there are
'issues' with that - hopefully Bob will educate us. (I really appreciate the
detailed & thorough explanations you've been providing Bob - thanks).

---

From: "Bob Wyman" <[email-masked]>
Date: Thu, 16 Sep 2004 01:22:15 -0400

Mike Dieken wrote:
> That effectively turns content-based routing into topic based routing.
> But, I'm sure there are 'issues' with that
	I don't see what "issues" you might be referring to. In many
ways, the stream of results created by a content-based subscription can
be viewed as a "topic". Take a look at the RSS or Atom files that we
provide as samples on our homepage at http://pubsub.com/ . Today, and
for at least a few more weeks, you'll see feeds dedicated to "John
Kerry", "George Bush", and a few other subjects. You can treat these as
"topics". You can subscribe to the "John Kerry" feed and receive any
mention of "John /near Kerry" in over three million RSS or Atom files,
without being concerned with the fact that we used a content-based
matching engine to construct that feed/topic.

	You can view a content-based system as one that allows you to
construct topics in infinite variety. The key difference from
traditional topic-based systems is that "topics" created by
content-based matching are "visible" only to the subscribers -- not the
publishers. In a topic based system, the publisher typically publishes
"to" the topic that is to be subscribed to -- thus, the publisher knows
the context within which messages will be read. This isn't the case in a
content based system.
	Basically, the content-based approach takes one step further the
idea of "anonymity" which is often cited as a fundamental attribute of
publish/subscribe systems. The idea is that since publishers and
subscribers in pubsub system are separated by some sort of matching
engine or intermediate message broker, there is no necessary tie between
publisher and subscriber. Publishers don't need to know, and usually
can't know, who is receiving their messages. In a content based system,
the publishers and subscribers are similarly separated by the broker,
however, the publishers are also typically unaware of what subscriptions
(queries) are being managed by the broker. Thus, in content-based
systems, message recipients are not only anonymous but the context
within which they receive messages (i.e. the subscriptions) is
anonymous. 
	This double anonymity (of both identity and context) is very
close to the root of the problem with doing "deletions" or
"cancellations" in a content based system... Since the publisher has no
idea of either who received their content or in what context it was
received, it is very difficult to figure out to whom cancellation
messages should be sent. If publishers knew either who received the
message which is to be cancelled, or how to construct a message other
than the original which would satisfy all the subscriptions that matched
the message to be cancelled, then cancellation would be much, much
easier and much more useful to discuss.
	Of course, there are some PubSub systems that expose either or
both of recipients identity and context. One example is what you see if
you get Level III Market Data or you look at something like the "Island
Book"[1] of outstanding buy and sell orders for stocks. What you'll see
is all the outstanding "subscriptions" that the Island matching engine
is maintaining. You've got a bunch of people trying to find buyers and a
different bunch looking for the sellers of some stock. A buyer's
subscription to sellers looks like: ("role=seller and price <= $99"). A
matching seller's subscription looks like ("roll=buyer and price >=
$99"). The "book" in this case is a summary of all outstanding
subscriptions. However, these systems still typically go to great
lengths to hide the actual identity of the participants. They let you
see what folk want -- but not who they are. I could provide further
examples (i.e. known subscribers but anonymous contexts) but you should
get the point, I think...

	In summary, it is trivial to construct "topics" by using a
content-based system, however, the characteristics of the topics
constructed in this manner are different then those of traditional
topic-based systems at least in that the publisher cannot see the
subscriptions and thus doesn't know what "topics" they are publishing
to.

		bob wyman

[1] Check out the following URL when the US stock markets are open:
http://data.inetats.com/ds/tools/bookviewer/htmlbook.jsp?STOCK=MSFT

---

From: "S. Mike Dierken" <[email-masked]>
Date: Thu, 16 Sep 2004 20:44:02 -0700

> I don't see what "issues" you might be referring to.
I was thinking that clients don't publish directly to that topic. They
could, but typically don't.

---

From: Danny Ayers <[email-masked]>
Date: Sat, 18 Sep 2004 11:45:45 +0200

> > accept that once they have sent a message, they have lost control over it.

+1. Yep, nicely put.

-- 

http://dannyayers.com