incubator-wave-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael MacFadden <michael.macfad...@gmail.com>
Subject Re: Delving into OT
Date Wed, 17 Jul 2013 14:30:04 GMT
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
View raw message