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, 16 Jul 2013 18:02:07 GMT
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