incubator-wave-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Joseph Gentle <jose...@gmail.com>
Subject Re: Delving into OT
Date Wed, 24 Jul 2013 17:49:23 GMT
Great.

I'd like to ask that everyone who attends has a basic understanding of
how wave's current OT algorithm works. There are several videos and
blog posts on the subject. Here's a video of me explaining the same
algorithm in the context of sharejs:
http://www.youtube.com/watch?v=CsfiADbXTPo
... but there's many more resources kicking around.

-J

On Wed, Jul 24, 2013 at 3:48 AM, Bruno Gonzalez (aka stenyak)
<stenyak@gmail.com> wrote:
> I may be able to assist to the hangout too. I've submitted my schedule
> to the doodle, but can't really guarantee I'll be there.
>
> On Tue, Jul 23, 2013 at 6:40 PM, John Blossom - Shore Communications
> Inc. <jblossom@shore.com> wrote:
>> Michael, as long as you, Ari and Joseph can make it, and the scheduling
>> tool said that you can, I think that we'll have the core of the discussion.
>> The objective is not to put on a show as much as it is to get the core OT
>> thinkers driving the discussion. Let the ideas drive the interest.
>>
>> BTW, I shifted it up a half your, I have a telecon that starts at 12.30.
>> Consider this a kickoff event - let's shoot for somewhere south of an
>> hour's worth of very productive conversation and then let's start thinking
>> about how to keep the conversations going at a very productive level on a
>> more regular basis. I am also totally for more impromptu efforts, but for
>> the sake of the community if we can post our conversations for
>> community-wide access, that can help.
>>
>> Best Regards,
>>
>> John Blossom
>> President
>> Shore Communications Inc.
>>
>> where content, technology and people meet. (Salesmark of Shore
>> Communications Inc.)
>>
>> web: shore.com
>> blog: contentblogger.com
>> email: jblossom@shore.com
>> phone: 203.293.8511
>> fax: 203.663.8259
>> twitter: jblossom <https://twitter.com/jblossom>
>> google+: google.com/+JohnBlossom
>> LinkedIn: John Blossom <http://www.linkedin.com/in/johnblossom>
>> facebook: John Blossom
>> skype: jblossom
>>
>>
>>
>> On Tue, Jul 23, 2013 at 12:01 PM, Michael MacFadden <
>> michael.macfadden@gmail.com> wrote:
>>
>>> John,
>>>
>>> Again I don't mean to delay the effort. But looking at the attendee
>>> responses, I only see one person on the list that has agreed to attend that
>>> has really been heavily working OT issues in the last year or so (Joseph).
>>> So I am not sure what the objectives or the outcome of the meeting will be
>>> with such low participation from OT experts.
>>>
>>> By no means do I mean to diminish any one else's capabilities, but if the
>>> intention is to really dig in to OT, then I think we night need additional
>>> participation to be successful.
>>>
>>> ~Michael
>>>
>>> On Jul 23, 2013, at 8:40 AM, "John Blossom - Shore Communications Inc." <
>>> jblossom@shore.com> wrote:
>>>
>>> > I agree wholeheartedly that the entire Apache Wave community should be
>>> > excited about participating, and I assume that everyone on the list is
>>> > seeing this and should want to join in. If we have to reschedule, no
>>> > biggie, we're at square zero and it's more about getting people on board
>>> > and brainstorming. If you've been invited already, then invite others who
>>> > you think should be excited. To that end, here's the link to the event:
>>> >
>>> > https://plus.google.com/u/0/+JohnBlossom/posts/KTB6EkxB99q
>>> >
>>> > If you're an Apache Wave committer and you miss the event, then you'll be
>>> > able to view it via YouTube via a link that I'll post here.
>>> >
>>> > I do want to start accelerating communications more in the community, but
>>> > this is a busy week.
>>> >
>>> >
>>> > Best Regards,
>>> >
>>> > John Blossom
>>> > President
>>> > Shore Communications Inc.
>>> >
>>> > where content, technology and people meet. (Salesmark of Shore
>>> > Communications Inc.)
>>> >
>>> > web: shore.com
>>> > blog: contentblogger.com
>>> > email: jblossom@shore.com
>>> > phone: 203.293.8511
>>> > fax: 203.663.8259
>>> > twitter: jblossom <https://twitter.com/jblossom>
>>> > google+: google.com/+JohnBlossom
>>> > LinkedIn: John Blossom <http://www.linkedin.com/in/johnblossom>
>>> > facebook: John Blossom
>>> > skype: jblossom
>>> >
>>> >
>>> >
>>> > On Tue, Jul 23, 2013 at 10:16 AM, Michael MacFadden <
>>> > michael.macfadden@gmail.com> wrote:
>>> >
>>> >> I don't want to delay this thing, but are there really no other people
>>> who
>>> >> are interested in this?  I think we should really try to reach out
>>> >> personally to some other folks to see if we can attract them in.
>>> >>
>>> >> ~Michael
>>> >>
>>> >> On 7/23/13 7:00 AM, "John Blossom" <jblossom@gmail.com> wrote:
>>> >>
>>> >>> 1200 ET, btw - bad math.
>>> >>>
>>> >>> All the best,
>>> >>>
>>> >>> John Blossom
>>> >>>
>>> >>> email: jblossom@gmail.com
>>> >>> phone: 203.293.8511
>>> >>> google+: https://google.com/+JohnBlossom
>>> >>>
>>> >>>
>>> >>> On Tue, Jul 23, 2013 at 9:53 AM, John Blossom <jblossom@gmail.com>
>>> wrote:
>>> >>>
>>> >>>> OK, the consensus time/date for the hangout seems to be Wednesday,
31
>>> >>>> July, 1600 UTC (1000 EDT). I will create and event later today
in
>>> >>>> Hangouts.
>>> >>>> If you're on the wave-dev list and have a Google login, please
forward
>>> >>>> me
>>> >>>> your email ID/Google+ ID privately and I will add you to the
circle of
>>> >>>> invitees. I Have Joseph's ID already and I believe Ali and Michael
>>> also,
>>> >>>> but if you have a doubt, just send it along. If you don't make
the
>>> >>>> hangout
>>> >>>> itself, I will be sure to share the link here for the common
record.
>>> >>>>
>>> >>>> All the best,
>>> >>>>
>>> >>>> John Blossom
>>> >>>>
>>> >>>> email: jblossom@gmail.com
>>> >>>> phone: 203.293.8511
>>> >>>> google+: https://google.com/+JohnBlossom
>>> >>>>
>>> >>>>
>>> >>>> On Thu, Jul 18, 2013 at 9:06 AM, John Blossom <jblossom@gmail.com>
>>> >>>> wrote:
>>> >>>>
>>> >>>>> Ali,
>>> >>>>>
>>> >>>>> New tool for me, but worth a try. Here's the Doodle link:
>>> >>>>> http://doodle.com/5z7usamgh7kee4gf
>>> >>>>>
>>> >>>>> I am open to other times, but these seem to be the most
logical.
>>> Please
>>> >>>>> remember that UTC at this time of year is one hour less
ahead from
>>> the
>>> >>>>> U.S.
>>> >>>>> time zones due to Daylight Savings Time - e.g., ET is UTC+4
right
>>> now.
>>> >>>>>
>>> >>>>> All the best,
>>> >>>>>
>>> >>>>> John Blossom
>>> >>>>>
>>> >>>>> email: jblossom@gmail.com
>>> >>>>> phone: 203.293.8511
>>> >>>>> google+: https://google.com/+JohnBlossom
>>> >>>>>
>>> >>>>>
>>> >>>>> On Wed, Jul 17, 2013 at 5:57 PM, Ali Lown <ali@lown.me.uk>
wrote:
>>> >>>>>
>>> >>>>>> I agree that another hangout sounds fun.
>>> >>>>>>
>>> >>>>>> John, how about setting up a Doodle for us to mark some
dates on?
>>> >>>>>> (http://doodle.com/)
>>> >>>>>>
>>> >>>>>> Ali
>>> >>>>>>
>>> >>>>>> On 17 July 2013 15:33, John Blossom <jblossom@gmail.com>
wrote:
>>> >>>>>>> Great, Michael, find a date that works for you that
seems to match
>>> >>>>>> with
>>> >>>>>>> others' interests and I will be glad to arrange
for this. We can
>>> >>>>>> have
>>> >>>>>> the
>>> >>>>>>> link available but not make public, if that helps
to encourage
>>> >>>>>> constructive
>>> >>>>>>> participation.
>>> >>>>>>>
>>> >>>>>>> All the best,
>>> >>>>>>>
>>> >>>>>>> John Blossom
>>> >>>>>>>
>>> >>>>>>> email: jblossom@gmail.com
>>> >>>>>>> phone: 203.293.8511
>>> >>>>>>> google+: https://google.com/+JohnBlossom
>>> >>>>>>>
>>> >>>>>>>
>>> >>>>>>> On Wed, Jul 17, 2013 at 10:30 AM, Michael MacFadden
<
>>> >>>>>>> michael.macfadden@gmail.com> wrote:
>>> >>>>>>>
>>> >>>>>>>> I am definitely interested.  I will check my
schedule for next
>>> >>>>>> week.
>>> >>>>>>>>
>>> >>>>>>>> ~Michael
>>> >>>>>>>>
>>> >>>>>>>> On 7/16/13 11:02 AM, "John Blossom" <jblossom@gmail.com>
wrote:
>>> >>>>>>>>
>>> >>>>>>>>> That was my thought, also. ApacheWavers,
please respond with some
>>> >>>>>> avails
>>> >>>>>>>>> calibrated to UT+1 for this week and next
week. Time to get this
>>> >>>>>> party
>>> >>>>>>>>> started! My L,A. project is waiting for
the funder to come
>>> >>>>>> through,
>>> >>>>>> but my
>>> >>>>>>>>> Nkommo project is gaining steam - hopeful
that we'll have some
>>> >>>>>> exciting
>>> >>>>>>>>> announcements fairly soon. Time to change
the world with Wave!!!
>>> >>>>>>>>>
>>> >>>>>>>>> All the best,
>>> >>>>>>>>>
>>> >>>>>>>>> John Blossom
>>> >>>>>>>>>
>>> >>>>>>>>> email: jblossom@gmail.com
>>> >>>>>>>>> phone: 203.293.8511
>>> >>>>>>>>> google+: https://google.com/+JohnBlossom
>>> >>>>>>>>>
>>> >>>>>>>>>
>>> >>>>>>>>> On Tue, Jul 16, 2013 at 1:58 PM, Joseph
Gentle <
>>> josephg@gmail.com
>>> >>>
>>> >>>>>> wrote:
>>> >>>>>>>>>
>>> >>>>>>>>>> I've had a busy few weeks - gearing
up to launch our product at
>>> >>>>>> work.
>>> >>>>>>>>>> We should organize another hangout sometime.
>>> >>>>>>>>>>
>>> >>>>>>>>>> -J
>>> >>>>>>>>>>
>>> >>>>>>>>>> On Sat, Jul 13, 2013 at 7:24 AM, John
Blossom - Shore
>>> >>>>>> Communications
>>> >>>>>>>>>> Inc. <jblossom@shore.com> wrote:
>>> >>>>>>>>>>> Soo...how is this initiative going?
How may I help to move it
>>> >>>>>> forward?
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> Best Regards,
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> John Blossom
>>> >>>>>>>>>>> President
>>> >>>>>>>>>>> Shore Communications Inc.
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> where content, technology and people
meet. (Salesmark of Shore
>>> >>>>>>>>>>> Communications Inc.)
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> web: shore.com
>>> >>>>>>>>>>> blog: contentblogger.com
>>> >>>>>>>>>>> email: jblossom@shore.com
>>> >>>>>>>>>>> phone: 203.293.8511
>>> >>>>>>>>>>> fax: 203.663.8259
>>> >>>>>>>>>>> twitter: jblossom <https://twitter.com/jblossom>
>>> >>>>>>>>>>> google+: google.com/+JohnBlossom
>>> >>>>>>>>>>> LinkedIn: John Blossom
>>> >>>>>> <http://www.linkedin.com/in/johnblossom>
>>> >>>>>>>>>>> facebook: John Blossom
>>> >>>>>>>>>>> skype: jblossom
>>> >>>>>>>>>>>
>>> >>>>>>>>>>>
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> On Mon, Jul 8, 2013 at 9:43 AM,
John Blossom
>>> >>>>>> <jblossom@gmail.com
>>> >>>>>>>
>>> >>>>>>>>>> wrote:
>>> >>>>>>>>>>>
>>> >>>>>>>>>>>> Ingenious, Torben, certainly
adds efficiency. John
>>> >>>>>>>>>>>>
>>> >>>>>>>>>>>> On Mon, Jul 1, 2013 at 4:38
AM, Torben Weis <
>>> >>>>>> torben.weis@gmail.com>
>>> >>>>>>>>>> wrote:
>>> >>>>>>>>>>>>
>>> >>>>>>>>>>>>> 2013/6/25 Joseph Gentle
<josephg@gmail.com>
>>> >>>>>>>>>>>>>
>>> >>>>>>>>>>>>>>
>>> >>>>>>>>>>>>>>>> When peers connect,
they send each other missing ops.
>>> >>>>>> Figuring
>>> >>>>>>>>>> out
>>> >>>>>>>>>>>>>>>> which ops are
missing can be surprisingly tricky - but
>>> >>>>>> we'll
>>> >>>>>>>>>> figure
>>> >>>>>>>>>>>>>>>> that out later.
New ops must be ingested in order, so
>>> >>>>>> we
>>> >>>>>> always
>>> >>>>>>>>>>>>> ingest
>>> >>>>>>>>>>>>>>>> an operation
after ingesting all of its parents.
>>> >>>>>>>>>>>>>>
>>> >>>>>>>>>>>>>> Just use a Merkle Tree
that is at the same time a prefix
>>> >>>>>> tree with
>>> >>>>>>>>>>>>> respect
>>> >>>>>>>>>>>>> to the hashes of the ops
(explanation below).
>>> >>>>>>>>>>>>> The bandwidth usage is O(1)
if both clients are in sync and
>>> >>>>>> O(log
>>> >>>>>>>>>> n) if
>>> >>>>>>>>>>>>> they have one or few different
ops and O(n) in the worst
>>> >>>>>> case,
>>> >>>>>>>>>> where n
>>> >>>>>>>>>> in
>>> >>>>>>>>>>>>> the number of ops.
>>> >>>>>>>>>>>>>
>>> >>>>>>>>>>>>> Constructing the tree is
simple.
>>> >>>>>>>>>>>>> Let the hash function output
20 bytes and let's encode this
>>> >>>>>> in
>>> >>>>>> hex.
>>> >>>>>>>>>> This
>>> >>>>>>>>>>>>> results in a hash-string
of 40 hex-characters for each
>>> >>>>>> operation.
>>> >>>>>>>>>>>>> Each node hashes over the
hashes of its children. Leaf-nodes
>>> >>>>>>>>>> correspond to
>>> >>>>>>>>>>>>> operations and thus use
the hash value of their respective
>>> >>>>>>>>>> operation.
>>> >>>>>>>>>>>>> The tree-invariant is that
all siblings on level x share the
>>> >>>>>> same
>>> >>>>>>>>>> prefix
>>> >>>>>>>>>>>>> of
>>> >>>>>>>>>>>>> x hex-characters.
>>> >>>>>>>>>>>>> The tree is not sent over
the network. Instead, clients
>>> >>>>>> start
>>> >>>>>>>>>> comparing
>>> >>>>>>>>>>>>> the
>>> >>>>>>>>>>>>> hashes at the root.
>>> >>>>>>>>>>>>>
>>> >>>>>>>>>>>>> Two clients compare their
root hash. If it is equal, the
>>> >>>>>> entire
>>> >>>>>>>>>> tree is
>>> >>>>>>>>>>>>> equal and therefore they
are in sync.
>>> >>>>>>>>>>>>> If not, they download all
direct children and repeat the
>>> >>>>>> procedure
>>> >>>>>>>>>> for
>>> >>>>>>>>>>>>> each
>>> >>>>>>>>>>>>> sub-tree rooted by one of
these children.
>>> >>>>>>>>>>>>> For example, if child number
3 has a different hash, but all
>>> >>>>>> others
>>> >>>>>>>>>> share
>>> >>>>>>>>>>>>> the same hash, then we have
learned that there are one or
>>> >>>>>> more
>>> >>>>>> ops
>>> >>>>>>>>>> with a
>>> >>>>>>>>>>>>> hash of 3xxxx... that are
different and need syncing.
>>> >>>>>>>>>>>>>
>>> >>>>>>>>>>>>> Typically we can limit the
depth of the tree to few levels.
>>> >>>>>> 8
>>> >>>>>> levels
>>> >>>>>>>>>>>>> already yield a tree that
could store 16^8 possible ops. So
>>> >>>>>> in
>>> >>>>>> the
>>> >>>>>>>>>> worst
>>> >>>>>>>>>>>>> case two clients need to
wait for 8 round-trips to
>>> >>>>>> determine a
>>> >>>>>>>>>> missing
>>> >>>>>>>>>> op.
>>> >>>>>>>>>>>>>
>>> >>>>>>>>>>>>> In addition, each client
sends a time stamp. So when
>>> >>>>>> syncing we
>>> >>>>>>>>>> report
>>> >>>>>>>>>> the
>>> >>>>>>>>>>>>> last time stamp received
from this client and ask for all
>>> >>>>>> ops
>>> >>>>>> this
>>> >>>>>>>>>> client
>>> >>>>>>>>>>>>> received later. If these
are few, then simply get them (even
>>> >>>>>> if we
>>> >>>>>>>>>> know
>>> >>>>>>>>>>>>> some of the ops already,
because we got them from another
>>> >>>>>> client).
>>> >>>>>>>>>> If
>>> >>>>>>>>>>>>> there
>>> >>>>>>>>>>>>> are too many ops, fall back
to the merkle tree. With a good
>>> >>>>>>>>>> approximation
>>> >>>>>>>>>>>>> of RTT and bandwidth, it
is easy to calculate which
>>> >>>>>> algorithm
>>> >>>>>> is the
>>> >>>>>>>>>> best
>>> >>>>>>>>>>>>> to sync two clients.
>>> >>>>>>>>>>>>>
>>> >>>>>>>>>>>>> Greetings
>>> >>>>>>>>>>>>> Torben
>>> >>
>>> >>
>>> >>
>>>
>
>
>
> --
> Regards/Saludos,
>      Bruno Gonzalez
>
> http://www.stenyak.com | stenyak @ irc://irc.freenode.net

Mime
View raw message