The other side of the moon

/bb|[^b]{2}/
Never stop Grokking

Monday, November 22, 2010

Stream of Collaboration and the Unified InBox

Back in 2003, I'd published a report on the state of computer mediated collaboration at the time. The report did not contain any original research, but was a list of references to other research on the topic. I was also working on ayttm and doing some work on automated project management at the time, which led to my talks on Fallback Messaging and Project Management with Bugzilla, CVS and mailing lists.

The state of technology has changed a lot over the years, and we're getting closer to the Unified Message InBox. The idea has been mulling in my mind for a while, and I've prototyped various implementations as a subset of what I call a stream of collaboration.

Communication

As technologically aware humans, we communicate in a variety of ways. Face-to-face, through the grapevine, handwritten letters and post-it notes, instant messaging, SMS, telephone calls, email, discussion boards, twitter, blogs, smoke signals, morse code using signalling lights, semaphore flags and more. Some of us prefer one form over another, and some of us will completely boycott a particular form of communication purely on principle, some of us won't use a form of communication because simpler methods exist and some of us will use a particular form of communication purely because it isn't the simplest one available. That's what makes each of us uniquely human. It also pushes us into groups and cliques that may or may not intersect. Who among you has a separate group of friends on twitter and facebook even though the two media are not vastly different? Do you also belong to a HAM radio club and a book reading group?

Now some forms of communication are well suited to automated archiving while others might end up being a game of Chinese whispers. Each form of communication also results in a different signal to noise ratio. Depending on the context of the conversation, accuracy and efficiency may or may not be a concern.

Degrees of Communication

Collaboration and Cooperation
Collaboration between a group of people involves communication, often requires archiving of all communications, and a high signal to noise ratio. Discussion lists, IRC logs, wikis, whiteboards, video/audio conferences, project trackers, bug trackers, source control commits, and sometimes email all provide good archiving capabilities. With proper time-stamping of each interaction, the archiving service can interleave events showing the exact chronological order of decisions being made. A Bayesian Filter, similar to the ones used for classifying spam can be used on a per topic basis to hide (but not remove) off-topic sections in an attempt to increase the signal to noise ratio. Once archived, even synchronous communication turns asynchronous [1]. Readers can later comment on sections of a communications log.

While some of the tools mentioned above are aimed at technical collaboration, many of them may also be used effectively for collaboration and support in a non-technical context [2,3] where immediate dissemination of information that can be archived and later used for reference is important.
Social Interaction
A form of communication that is more tolerant of a low signal to noise ratio, and in many cases does not require archival is social interaction. For example, at a party to watch a ball game, conversation may range from the actual events of the game to something completely irrelevant, and they're all socially acceptable in that context. Similarly, the corridor conversations at a conference may only be partially relevant to the subject matter of the conference. How does this translate to a scenario where people are geographically separated and need to communicate electronically rather than face to face?

Social television experiences [4], Co-browsing, LAN parties and digital backchannels [5] are examples where individuals communicate online while simultaneously engaging in a common task at geographically disparate locations. Computer mediated collaboration allows these individuals the ability to come close to the full party experience.
Casual Conversations
With more people moving their lives online [6,10], we're at a point where the volume of casual electronic conversations far exceeds that of technical collaboration. Fallback messaging is a good starting point to tie different forms of communication into a single thread, but it ignores current reality.

For starters, the fallback messaging idea assumes that users would use the same interface to communicate synchronously and asynchronously. In reality people use different methods for each. Asynchronous communication offers the ability, and often creates the necessity of longer messages and a larger amount of time devoted to communicating the message [7]. Should I say "Dear ..." or do I lead in with "Hi"? Should my background be pink or yellow? Do I want hearts, unicorns, birthday cakes or plain white in the background? Do I sign off with "Sincerely", "Regards", "Cheers" or "ttyl"? A different interface for each mode of communication makes it possible to customise the interface for the most common uses of that mode.

Fallback messaging was initially only applied to conversation between two persons, however a lot of casual communication happens between groups with the conversation sometimes forking into side-band conversations between a few (possibly two) members of the group and then merging back in to the parent conversation [7]. Some times the child conversation is made public to the group and some times it isn't. A messaging system must take this into consideration.

Enabling the Stream of Collaboration

Borrowed Ideas
The main idea behind fallback messaging was that service providers, communication protocols and user accounts were an implementation detail and the user should not be concerned with them. Users should only need to think of who they're communicating with, identifying them in any way they find comfortable (for example, using their names, nicknames, an avatar or favourite colour). The service needs to be able to determine based on context and availability, which messaging protocol to use.

Another idea that comes out of the original SMTP specification, is the now obsolete SOML [8] command. The SOML (Send Or MaiL) command would check to see if the recipient of the message was online when the message was sent, and if so, would echo the message to the user's terminal. If the user wasn't online at the time, it would append the message to their mailbox instead. Services like Yahoo! Messenger offer offline messaging capabilities that will hold a message on the server until the user comes online at which point it is delivered to them.

The problem with both these approaches is that they expect the user to create a message appropriate for the underlying service rather than the other way around. An entire email message in the case of SOML or a short text message in the case of Yahoo! Messenger. What we really need is a service that can decide based on what the user does, what kind of message needs to be sent, and how that message should be presented.

Facebook, GMail and Yahoo! Mail all offer a service where instant messaging and mail style messages can be sent from the same page, but with a different interface for each. Additionally, GMail provides the ability to see archived email messages and chat messages in the same context.
Proposed Interface
A messaging system is most useful to the user if it acts as a single point for them to reference and act on all past conversations, and provides an easy gateway to initiating new ones. The read interface must list all past conversations chronologically, with the ability to filter them based on topic and other participants in the conversation. It should be able to show where a conversation forked into separate threads, some of which may have been private, but all of which involved the user, and where these threads merged back into the primary stream.

The interface should include all kinds of communication including email, instant messages, co-browsing sessions, whiteboards, IRC, and anything else. Integrating with a service such as Google Voice, Skype or other VoIP solutions also allows it to tie in telephone conversations. Twitter and facebook notifications would tie in to this timeline as well.

The system should not rely only on message headers and meta-information, but also on message content to determine the topic and participants in a conversation [9]. Some participants, for example, may be involved indirectly, but not be privy to the details of the conversation, however it is useful to the reader to be able to filter messages with these details. Content analysis can also be used to identify messages as common Internet memes and tag them accordingly, possibly providing external links to more detailed information on the topic. Lastly, as has been proposed with fallback messaging, the system needs to aggregate all accounts of a contact across services into a single user defined identifier. It should still be possible for the user to identify which service is being used, but this should be done using colours, icons or similar markers.

Where are we today?

All major electronic communication services already provide some level of API acess to their messaging systems [11,12,13,14,15,16,17]. Services like Tweetdeck provide a single interface to multiple short message services (like twitter, identi.ca and the facebook wall), and Threadsy is supposed to unify your online social experience. Facebook seeks to unify email, IM, texting and Facebook messages through their own messaging service [18] which, like fallback messaging, is supposed to abstract out user accounts so that all you see is your contacts. I haven't seen the new messaging service yet, so I don't know if it also integrates with things like GMail, twitter, Yahoo! and other services that compete with Facebook [19]. If it does, that would be pretty cool. If it doesn't, there's an opportunity to build it. There are still other services that need to be tied in to enable full collaboration, but it doesn't seem too far away.

References

1. Terry Jones. 2010. Dancing out of time: Thoughts on asynchronous communication. In O'Reilly Radar, October 26 2010. http://radar.oreilly.com/2010/10/dancing-out-of-time-thoughts-o.html
2. Leysia Palen and Sarah Vieweg. 2008. The emergence of online widescale interaction in unexpected events: assistance, alliance & retreat. In Proceedings of the 2008 ACM conference on Computer supported cooperative work (CSCW '08). ACM, New York, NY, USA, 117-126.
3. Sutton, J., Palen, L., & Shklovski, I. 2008. Back-Channels on the Front Lines: Emerging Use of Social Media in the 2007 Southern California Wildfires. In Proceedings of the Conference on Information Systems for Crisis Response and Management (ISCRAM).
4. Crysta Metcalf, Gunnar Harboe, Joe Tullio, Noel Massey, Guy Romano, Elaine M. Huang, and Frank Bentley. 2008. Examining presence and lightweight messaging in a social television experience. ACM Trans. Multimedia Comput. Commun. Appl. 4, 4, Article 27 (November 2008), 16 pages.
5. Joseph F. McCarthy, danah boyd, Elizabeth F. Churchill, William G. Griswold, Elizabeth Lawley, and Melora Zaner. 2004. Digital backchannels in shared physical spaces: attention, intention and contention. In Proceedings of the 2004 ACM conference on Computer supported cooperative work (CSCW '04). ACM, New York, NY, USA, 550-553.
6. Donna L. Hoffman, Thomas P. Novak, and Alladi Venkatesh. 2004. Has the Internet become indispensable?. Commun. ACM 47, 7 (July 2004), 37-42. http://cacm.acm.org/magazines/2004/7/6471-has-the-internet-become-indispensable
7. Rebecca E. Grinter and Leysia Palen. 2002. Instant messaging in teen life. In Proceedings of the 2002 ACM conference on Computer supported cooperative work (CSCW '02). ACM, New York, NY, USA, 21-30.
8. Jonathan Postel. 1982. RFC 821: Simple Mail Transfer Protocol. IETF Network Working Group RFC Draft. http://www.ietf.org/rfc/rfc0821.txt, (August 1982).
9. Dong Zhang; Gatica-Perez, D.; Roy, D.; Bengio, S.; "Modeling Interactions from Email Communication," Multimedia and Expo, 2006 IEEE International Conference on , vol., no., pp.2037-2040, 9-12 July 2006
10. Rana Tassabehji and Maria Vakola. 2005. Business email: the killer impact. Commun. ACM 48, 11 (November 2005), 64-70. http://cacm.acm.org/magazines/2005/11/6081-business-email
11. Yahoo! Mail API. http://developer.yahoo.com/mail/
12. Yahoo! Messenger SDK. http://developer.yahoo.com/messenger/
18. MG Siegler. 2010. Facebook's Modern Messaging System: Seamless, History and a Social Inbox. Techcrunch, Nov 15 2010. http://techcrunch.com/2010/11/15/facebook-messaging/
19. Alexia Tsotsis. 2010. Between Gmail, Twitter and now Facebook There is no Universal Inbox Yet. Techcrunch, Nov 22 2010. http://techcrunch.com/2010/11/21/facebook-messages-is-people/

Sunday, November 21, 2010

Counterfeit coins solution

This is a solution to the Weighing piles of coins problem listed on Microsoft Research. It was fun solving it, and the basic idea of the solution could be applied to many other kinds of elimination problems.

Here's my algorithm. If you don't understand it, well, spend some time figuring it out.
Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 4 4 4 3 3 3 2 2 2 1 1 1 0 => 30 coins
// This is the first weighing

expected weight = 30X
actual weight = W

X1 = W div 30
D1 = W mod 30    // D1 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4

if D1 == 0 then
weigh all 52 coins (W)    // this is the second weighing
X = W div 52
D = (W mod 52) / 4
pile = 13
else if D1 <= 5 then
possible piles = 1-12
else if D1 >= 25 then
X1 = X1 + 1,
D1 = 30 - D1
possible piles = 1-12
else if 5 < D1 < 10 then
possible piles = 1-9
else if 10 <= D1 <= 20
X11 = X1 + 1,
D11 = 30 - D1
possible piles = 1-6
end if

if 0 < D1 < 10 then

Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 3 4 1 2 4 0 1 3 2 3 4 4 => 32 coins
// This is the second weighing

expected weight = 32X
actual weight = W

X2 = W div 32
D2 = W mod 32    // D2 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4

if 12 <= D2 <= 20 and X1 != X2 then
X2 = X2 + 1
D2 = 32 - D2
end if

X = X2

if      D2 == D1*0 then
pile = 7
D = D1/2
else if D2 == D1*1 then
pile = 3
D = D1/4
else if D2 == D1*2 then
pile = 10
D = D1
else if D2 == D1*3 then
pile = 11
D = D1
else if D2 == D1*4 then
pile = 12
D = D1
else if D2 == D1*1/2 then
pile = 8
D = D1/2
else if D2 == D1*3/2 then
pile = 9
D = D1/2
else if D2 == D1*1/3 then
pile = 4
D = D1/3
else if D2 == D1*2/3 then
pile = 5
D = D1/3
else if D2 == D1*4/3 then
pile = 6
D = D1/3
else if D2 == D1*1/4 then
pile = 1
D = D1/4
else if D2 == D1*3/4 then
pile = 2
D = D1/4
end if
else

Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 2 3 0 1 2 4 4 4 4 4 4 4 => 37 coins
// This is the second weighing

expected weight = 37X
actual weight = W

X2 = W div 37
D2 = W mod 37    // D2 <= 15 since |D| <= 5 and counterfeit coins in pile <= 3

X = X2

if X11 == X2 then
D1 = D11
end if

if      D2 == D1*1/4 then
pile = 1
D = D1/4
else if D2 == D1*2/4 then
pile = 2
D = D1/4
else if D2 == D1*3/4 then
pile = 3
D = D1/4
else if D2 == D1*0/3 then
pile = 4
D = D1/3
else if D2 == D1*1/3 then
pile = 5
D = D1/3
else if D2 == D1*2/3 then
pile = 6
D = D1/3
end if
end if


Thursday, November 04, 2010

Submitting cross-domain SOAP requests from the browser without XForms

Web service calls from a web page to a back end service can easily be made using XHR as long as the service runs on the same domain that the page is served from. For cross-domain requests, however, we have a problem. Typical methods of doing cross-domain requests require script nodes, a server side proxy, a flash based transport, or submitting a hidden form to an iframe target.

While the server side proxy and flash based transport both add an external dependency the script node can only make a GET request, and the hidden form approach can only send URL encoded key/value pairs... that's until we try a bit of trickery.
<form id="soap" method="POST" action="[SOAP entry point URL]" enctype="text/plain">
<textarea name="<?xml version">
"1.0" encoding="UTF-8"?>
[SOAP message here]
</textarea>
</form>

<script>
document.getElementById("soap").submit();
</script>


And that's it. The key elements are highlighted. In particular, you set the form's enctype attribute to text/plain. This makes sure that none of the data is URL encoded. Then a clever trick that works well with XML documents. Set the text field's name to <?xml version, ie, the starting text of an XML document. Omit the = sign and set the value to everything else.

When the form is submitted, the browser sends form fields as key=value, one on each line (that's how text/plain works). In this case, it sends the following:
<?xml version="1.0" encoding="UTF-8"?>
[SOAP message here]

Which essentially submits the SOAP payload to the web service.

Caveats

Naturally, all browsers don't work alike. For this particular example, all Webkit based browsers are broken. They don't handle an enctype of text/plain correctly. Chrome, Safari and Konqueror all set the Content-type header to text/plain, but the actual submitted data is URL encoded. This is consistent with research done by Gregory Fleischer and Bug #20795 filed on WebKit. Firefox (as far as Netscape 4 IIRC, probably earlier), IE (6 and above) and Opera handle it correctly.

C-Surfing on SOAP

There are security concerns with this approach as well, and in my opinion they are bigger than any benefit this might bring. An attacker can use this method to CSRF your SOAP based web services. Given this, it's a good idea to make sure that all your web service calls also have some kind of nonce or token that can only be generated if the request originated from your site.