incubator-wave-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From John Blossom <jblos...@gmail.com>
Subject Re: Delving into OT
Date Tue, 23 Jul 2013 14:00:53 GMT
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
>>> >> >> >>>
>>> >> >> >>
>>> >> >> >>
>>> >> >>
>>> >>
>>> >>
>>> >>
>>>
>>
>>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message