[sugar] "Garden": A (currently hypothetical) Sugar library for sharing state between Activity participants

[Ken Ritchie]

www.jgroups.org (reliable multicast with flexible protocols)
www.opencroquet.org (especially the TeaTime components)

Those two projects came to mind immediately for having already explored 
(and solved) certain subproblems that must be addressed by OLPC. 

Dan already mentioned OpenCroquet. I'd like to add JGroups to the list 
-- there is the potential to harvest from the lessons learned and 
executable models already developed by those projects.

Note that both projects use message-based architectures (IMO, the best 
underlying medium for distributable and scalable architectures), neither 
requires any centralization of control, and both address the question of 
replicated state (data) amongst collaborating parties (views).

See my interjected notes below...
--ken [kritchie]

Dan Williams wrote, replying to Andrew Clunis:
> On Mon, 2006-11-27 at 03:01 -0500, Andrew Clunis wrote:
>   
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Hi all,
>>
>> It seems to me that OLPC development would be much friendlier for
>> students, educators, and wizened geeks alike if Sugar provided a means
>> for an author to mesh-enable their Activities in an elegant,
>> non-obtrusive and declarative way, *without* the need for a traditional
>> client/server topology.  Right now it appears that sugar.p2p only
>> provides a very simple foundation, thus requiring authors to essentially
>> devise their own network protocol.
>>     
>
> Correct.  The OpenCroquet project (loosely affiliated with Squeak and
> built on Squeak) is attempting to do network shared objects as well and
> apparently have many bits of it working fairly well including protocols.
>   
And with the underlying TeaTime models (David Reed) they have addressed 
the usual subproblems of distributed synchronization, and so on. 
"Croquet utilizes TeaTime, a scaleable real-time multi-user architecture 
that is based on the concept of replicated versioned objects coordinated 
by a universal time-base embedded within the communications protocol. 
TeaTime, is the basis for component object-object communication and 
world/object synchronization."  
[http://www.opencroquet.org/about_croquet/index.html]  Hmmm, is it 
"TeaTime in the Garden?" ;-)
>> "Garden", as I have termed the hypothetical system in the interim,
>> could be the answer to this problem.  It would be an amalgam, of sorts,
>> of a network object synchronisation system... 

>> ...[snip]...
>>     
>> Protocol:
>>
>> Changes would be transmitted as "differentials".  Transmitting the
>> entire object for each change would be prohibitively expensive in terms
>> of both network and CPU, and would also make debugging network logs more
>> difficult.
>>
>> The mechanism of the network component could be this: all the laptops
>> in the Activity are joined together in a single multicast group.
>> This will likely be done via the existing facilities in Sugar
>> (sugar.p2p) for many-to-many messaging (reliable multicast, etc.).
>> However, apparently that component of sugar is likely going to
>> rewritten or heavily refactored, so naturally any development will need
>> to follow the changes made there.
>>     
>
> One problem with this is that you can't depend on multicast only.  You
> have to deal with both multicast _and_ unicast.  Because of the nature
> of wireless networks, you may be on a different channel than the person
> sitting next to you.  It's unclear whether or not multicast will
> actually be routed correctly everywhere, and multicast has other
> reliability issues (ie, multicast frames are not retried/acked in the
> 802.11 protocol level, they are just dropped much like UDP).  So over
> multicast, there needs to be some best-effort delivery protocol like the
> MostlyReliablePipe implements.  But the MRP protocol is really bad and
> shouldn't be used.
>
>   
"JGroups is a toolkit for reliable multicast communication. (Note that 
this doesn't necessarily mean IP Multicast, JGroups can also use 
transports such as TCP). It can be used to create groups of processes 
whose members can send messages to each other..." -- " The most powerful 
feature of JGroups is its flexible protocol stack, which allows 
developers to adapt it to exactly match their application requirements 
and network characteristics." -- " JGroups allows developers to create 
reliable multipoint (multicast) applications where /reliability/ is a 
deployment issue, and does not have to be implemented by the application 
developer. This saves application developers significant amounts of 
time, and allows for the application to be deployed in different 
environments, without having to change code."  
[http://www.jgroups.org/javagroupsnew/docs/index.html]

> The team from Collabra working on Telepathy (which we may well
> transition to soon as a backend to the PresenceService) have done some
> looking into Scalable Reliable Multicast, which just might fit the bill
> here.
>
> But the model we've been looking at so far is a combination of
> jabber/XMPP servers and ZeroConf/Rendezvous/Bonjour/etc to get a more
> complete picture of who's around.  That's also necessary for
> scalability.  You'll always know who's in the immediate area using
> Avahi, but when you're in range of a school server, we should be talking
> to the server and merging the server's list of who's around with the
> ZeroConf list of who's around to give a much more complete picture.  If
> you want to talk to a person who's not visible with ZeroConf (ie, they
> are on a different radio channel, network segment, or across the globe),
> you'll need to either use XMPP to the school server, or communicate with
> that person directly.
>
> Anyway, long story for a short point that we can't just rely on
> multicast, because the kid in the desk next to you may not be visible to
> you without a server helping out.
>
> Farther out, we may wish to use a more peer-to-peer model with elected
> supernodes that voluntarily aggregate information about who they can see
> and how to talk to everyone they can see.  JXTA has done some of this
> and was something we looked at a year ago, but ultimate it was just not
> reliable enough at the time.
>
>   
Incidentally, JGroups is the industrial-strength, open-source enabling 
technology for our JBoss Application Server clustering (replicated 
state, session fail over, etc.). JBoss is a division of Red Hat.

"We use JGroups as the underlying framework for implementing the 
clustering features of the JBoss J2EE Application server 
<http://www.jboss.org>. JGroups gave us the opportunity to concentrate 
our efforts on the clustering features of JBoss instead of the very 
complex aspects of reliable group communication protocols. Through a 
very flexible and esthetic API we were able to built our clustering 
features without making strong assumption about the underlying protocols 
and network scheme (LAN, WAN, ...) that the end-users would face. As 
JGroups is an LGPL Open Source Project (which JBoss, as an open source 
project, requires), we were able to quickly find some minor bugs and 
implement new features that fitted our needs."
[http://www.jgroups.org/javagroupsnew/docs/success.html]
>> In order to manage the inevitable conflict race condition, at
>> negotiation time the participants could assign themselves a random
>> "rank" value.  In the event that a laptop receives a second changeset
>> with a sequence number equal to the one it received last, it would elect
>> to drop or use the changeset if the difference between ranks of both is
>> negative.  If it does decide to keep the newly received changeset, then
>> it will have to drop current object from the prior version (including
>> any local changes that may have occurred) and replace it with the new one.
>> This method has the added benefit of removing the need for a timeout,
>> replacing it with a limited number of copies of the object in
>> memory.  However, the extra memory use could prove expensive.
>>
>> Unfortunately, none of this takes the "island case" into account.  If
>> the group is split in two, then it would continue as two separate
>> groups with no rejoin capability (actually, that is debatable because
>> the Activity would still be listed in Avahi with the same ID. do I
>> have that right?).
>>     
>
> Yes; it would still be the same activity id.
>
>   
>> The above system is of course only one method of many to tackle these
>> problems.  Perhaps a preexisting system like "Fleet" will provide a
>> good basis for designing the protocol instead (suggested by Ivan K.).
>>
>> The entire network component could be exposed over d-bus for Activities
>> written in languages other than Python to take advantage of, since all
>> it does is provide a generic interface for ensuring a piece of data
>> in memory is kept synchronised with a group of other machines over the
>> network.  This would make the system meet requirement #3.
>>     
>
> Right; there's already going to be the identity & auth service, which
> likely will be over dbus, that activities may use to verify the
> authenticity of incoming signed messages, and to sign outgoing messages.
> This service may not be that different from an API and object model
> standpoint.
>
> However, if you're thinking of a _library_ that activities can use, then
> DBus really isn't the answer, since that would require that the Garden
> bits be a service, and therefore a daemon running all the time.  If it's
> really just a library providing an API that activity authors can plug
> into, then it would need to have bindings for the various languages that
> people will likely develop in.
>   
"The API of JGroups is very simple (similar to a UDP socket) and is 
always the same, regardless of how the underlying protocol stack is 
composed." [http://www.jgroups.org/javagroupsnew/docs/api.html]

...remainder of original thread omitted...

--ken