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 Wed, 17 Jul 2013 14:33:56 GMT
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