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

[Dan Williams]

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.

> "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 and the high-level Python
> marshalling library sitting on top of it.
> 
> Requirements:
> 
> 1) It needs to be easy for Python activity developers to write their
>    activities without having to spend significant amounts of time
>    devising an activity-specific network protocol;
> 
> 2) The syntax for using it should be as declarative and intuitive as
>    possible;
> 
> 3) It should also at least be partially available (at least the network
>    syncing component) to developers using a language other than Python; 
> 
> Threat Model:
> 
> Garden earns its name and threat model from the clever "Walled Garden"
> metaphor mentioned in the OLPC Human Interface Guidelines.  The general
> idea is that all participants enjoy equal and nearly absolute trust
> within the context of an activity.  That said, there should be a clear
> boundary between the activity context and the local personal context of
> a user.  Everyone can draw and muck about in the soil, but you don't
> want some other kid coming up and giving you a wet willy (read: explode
> your laptop).
> 
> 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.

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.

> 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.

> High-Level Python Component:
> 
> The language-specific component, at least for Python (requirement #1),
> could be implemented something like this: Every time one laptop makes
> a change to the shared object, the library is instructed to propagate
> the change.  This could be done by requiring the Activity developer to
> explicitly specify the changes they make by calling some special
> method for every change they make.  A more implicit method could
> involve introspection, whereby the library checks each instance
> attribute against older values in memory. Then, the library would
> transmit the modified fields to the multicast group, along with an
> incremented sequence number.  Both methods introduce some non-obvious
> complications.  Lists and Dictionaries would have to be replaced with
> special Garden-specific versions. Whatever method is chosen, it is
> important to keep requirement #2 in mind.
> 
> A thread would probably be necessary to wait for new messages coming in
> from the network, and a Lock for the entire shared object as well.

Possibly not, it can be done fairly easily of the activity is written
correctly; ie if the activity does not block.  The network bits only
need to tie into the activities event loop, or if you use DBus, then
DBus needs to be tied into the event loop.

> Best Practices for an Activity Author:
> 
> - - Never trust any data inside a shared object outside the scope of the
>   Activity (be wary of things like filenames, turing-complete code such
>   as scripts, data that you might pass into code other than your own,
>   etc.);
> 
> - - Make the rest of your Activity code as state-independent as possible,
>   because for several reasons the library may replace the entire state
>   of the shared object(s)
>   (conflict rollbacks, joining a new activity, etc.).

Right; it's really difficult to do shared state in a highly distributed,
low-bandwidth, unreliable transport network model like OLPC :)

It's a good idea to start working on something like this.  And remember
to keep it simple from the start and work out from there, otherwise it
may seem like a mountain to climb.  Furthermore, it might be useful to
identify one or two use-cases to build the model around; pick an
activity or two that you would envision would use this library, and look
at everything the library does with respect to those activities (and the
kids using those activities!) needs and interactions.

Dan

> Other Possible Features:
> 
> - - A "private" mode, whereby setting up a symmetric session
>   key by doing some sort of key negotiation via DH.  This feature, if it
>   exists at all, should be made easy to disable because many jurisdictions
>   in the world take a jaundiced eye to cryptography.
> 
> - - A "proxy" mode to allow someone to bring a friend in who is not on the
>   local network but rather on the public Internet somewhere.
> 
> This is a really hard problem, so I elected to post this brain-dump
> instead of write any code.  There will almost certainly be many differing
> opinions about how to go about doing this.
> 
> Is my take on this utterly hare-brained or does it have some merit? :)
> 
> - -- 
> Regards,
> Andrew Clunis
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.3 (GNU/Linux)
> 
> iD8DBQFFaptzALkUMXSNow8RAkYXAKC+1jkQWuldiWKqeUELAEibkNxudACfd6Ed
> XKygV5x7KrSbeqYfElwSQLQ=
> =7Nbk
> -----END PGP SIGNATURE-----
> _______________________________________________
> Sugar mailing list
> Sugar at laptop.org
> http://mailman.laptop.org/mailman/listinfo/sugar