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

[Andrew Clunis]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi dan!

I was hoping I could get a hold of you.

On Mon, Nov 27, 2006 at 10:35:22AM -0500, Dan Williams wrote:
> 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.

That's why I wanted to chat with you.  I want to use whatever subsystem
that Sugar will provide for the message passing, but it was my
understanding that sugar.p2p sucks right now and will be refactored/
replaced.  I would be very interested in hearing about how it will look
in the future.

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

Ooh.  And, if reliable many-to-many communication (whether local or
remote) were completely abstracted, then both the shared object
state library (Garden) and Activities that need more control wouldn't
have to worry about implementation specific details.

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

That said, according to the folks on #olpc the protocol component of
Garden should be usable by people in other languages.  Perhaps it would
make sense for the protocol system itself to be exposed over d-bus, just
the same as the Presence API is.  BTW, is sugar.p2p exposed over d-bus,
or will it be?

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

I'm going to start with Sketch. :)

But there's a lot of architectural issues to get sorted first, as you
said before.
> 
> Dan
>
- --
Many Thanks,
Andrew Clunis 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQFFa6lDALkUMXSNow8RArDlAJ9ny92bOHZTOA4FO4+0EOrJTMM/kQCgoWxM
Oxk+rkmGIy1ccHDaB93aiZE=
=XMpq
-----END PGP SIGNATURE-----