Re: [dispatch] A State Synchronization Working Group

[Michael Toomim <[e-mail]>]

Hi Hesham, great questions!

1. Time Synchronization is very a different problem from State 
Synchronization, and I think Time Sync is out-of-scope for this group.

2. "Consistency" itself is definitely in-scope, because the general goal 
of State Sync is for peers to end up with the same consistent state.

As for "consensus": those issues are in-scope to the degree to which 
they help achieve consistency. Some state sync systems do allow for 
multiple valid states, and thus might deploy a consensus algorithm for 
peers to choose a common outcome together. However, not all algorithms 
or situations require consensus, and the group would not focus on 
consensus in itself.

As for QuePaxa: it is true that traditional leader-based consensus 
algorithms (e.g. PAXOS and RAFT) can be used for state sync, but modern 
CRDTs implement state sync without need for a leader, which eliminates 
the need for a leader election with consensus and the two-phase commit 
cycle.

3. Yes, we have considered the IRTF as well. In fact, Prof. Christian 
Tschudin and I held a conversation with the IRTF chair this last summer 
in SF. The general issue is that we'll produce the best standards 
through a combination of Research and Standardization. Although the IRTF 
does research, it cannot produce standards. The IETF does some forms of 
research, in the process of creating standards, such as running 
experiments and doing performance analyses.

The IRTF chair told us that we need to be either a RG or a WG — we 
cannot straddle the line. So this is a proposal to form a WG that would 
integrate research knowledge into the standardization process. Our 
mandate would not be to invent algorithms per se, but to understand the 
algorithms well enough to define general protocols to support them. On 
the other hand, we recognize that in the process of understanding and 
generalizing algorithms, we often create new ones. This is how Seph 
Gentle created the List CRDTs algorithm mentioned above—he was trying to 
understand the differences between three CRDTs, and in the process, 
invented a new general CRDT that could replicate each of their 
behaviors. This is also why we invented the first history-pruning 
CRDT—we wanted to know what changes to the protocol would be needed to 
enable such a creature. Each algorithmic invention in State 
Synchronization teaches us something about the general shape of 
protocols, and when we try to create general protocols, we often produce 
new algorithms as a side-effect.

The specific idea of /starting/ in the IRTF before moving to a WG is 
interesting, but my understanding is that RGs have a mandate that lasts 
many years before they produce results, and we are already producing 
useful specs such as the Braid-HTTP draft.

On 10/25/23 3:58 PM, Hesham ElBakoury wrote:
> Hi Mike,
> Will this new WG look into the following issues:
>
> Time synchronization protocols. There are protocols that are newer 
> than PTP which may need to be considered. E.G.  HUYGENS from stanford 
> [https://www.usenix.org/system/files/conference/nsdi18/nsdi18-geng.pdf]
>
> Consistency protocols. This is an on going area of research. On Oct 23 
> 2023 EFPL researchers published the QuePaxa algorithm which is an 
> asynchronous consensus protocol that is on par with leader-based 
> protocols [https://dl.acm.org/doi/10.1145/3600006.3613150]
>
> State replication protocols for things such as high speed packet 
> processing [https://arxiv.org/pdf/2309.14647]
>
> Do you think we can start with IRTF before we go to IETF for 
> standardization?
>
> Thanks
> Hesham
>
> On Wed, Oct 25, 2023, 3:05 PM Michael Toomim <[e-mail]> wrote:
>
>     I would like to dispatch the idea of forming a general State
>     Synchronization Working Group, to coordinate duplicate efforts in
>     defining various state synchronization protocols across existing
>     IETF working groups.
>
>     Many networking protocols implement some form of state
>     synchronization.  At the application layer, SCIM, SIP, COAP, ALTO,
>     NETCONF, JMAP, CalDAV, and IPP all define state synchronization
>     protocols over HTTP.  Many non-IETF protocols also implement
>     sync-over-HTTP for specific uses, such as WebSub (to synchronize
>     blogs), ActivityPub (to synchronize social feeds), and Matrix (to
>     synchronize chat).  Outside of HTTP, we do state synchronization
>     in DNS, IMAP, LDAP, NFS, RSYNC, and Git.  Dropping to the
>     lower-level OSI layers, we have protocols to synchronize IP
>     routing tables, network reachability, and header compression
>     dictionaries like ROHC, OSPFv2, IS-IS, and BGP.  State
>     synchronization also comes up in distributed systems and
>     databases, with algorithms such as OT and CRDT, and each system
>     defines its own distinct protocol.
>
>     We design these as separate protocols because the *general*
>     version of the State Synchronization Problem has seemed too
>     challenging to tackle. However, the last decade of research has
>     brought breakthroughs in general state synchronization algorithms
>     that allow (a) multiple editors, (b) editing arbitrary data types,
>     (c) over a distributed network, (d) of arbitrary network topology,
>     (e) experiencing arbitrary network partitions and delays, (f) with
>     arbitrary merge resolution semantics—all with reasonable (and
>     improving) performance.  These general algorithms bring up the
>     possibility of designing general *protocols* for state sync.
>
>     If IETF working groups could rely on general standards for state
>     sync, they could eliminate redundant consensus and specification
>     work, as well as implementation work, because implementers could
>     re-use common libraries and algorithms instead of writing their
>     own algorithms. Furthermore, general libraries could afford
>     investment in advanced sync features such as peer-to-peer
>     networking, offline modes, delta-compression, merge resolution,
>     consistency guarantees, and fast-replay; which applications might
>     not implement on their own, but now could benefit from for free. 
>     This would improve networking robustness across the board. 
>     Finally, interoperability would improve.  Network sysadmins, for
>     example, could inspect and debug the state and history of their
>     routers, emails, web applications, email, and file systems with
>     intercompatible tools over a general protocol.
>
>     This new working group would integrate research with practice by
>     working in symbiosis with existing IETF Working Groups.  Our new
>     group would gather experts and researchers in state
>     synchronization and interface with individual Working Groups.  It
>     would learn the needs of individual working groups, and produce
>     general knowledge, protocols, and libraries in return.
>
>     We have had initial success with this model in the informal
>     Braid.org group, which was roughly modeled on an IETF Working
>     Group, and has produced the Braid-HTTP internet draft that is
>     coming up for discussion in HTTPbis.  The Braid group has met
>     every two weeks for 2.5 years on zoom, with average attendance of
>     4 or 5 people, and has produced a number of research results in
>     generalizing performant state synchronization:
>
>       - Diamond-Types <https://github.com/josephg/diamond-types>:
>     World's fastest P2P text editing CRDT
>       - List-CRDTs <https://github.com/josephg/reference-crdts>: First
>     text editing CRDT with general pluggable merge semantics (video
>     presentation
>     <https://braid.org/video/https://invisiblecollege.s3-us-west-1.amazonaws.com/braid-meeting-10.mp4#305>)
>       - Antimatter: World's first history-pruning P2P text editing
>     CRDT (draft <https://braid.org/antimatter>) (implementation
>     <https://www.npmjs.com/package/@braid.org/antimatter>)
>       - Sync9 <https://braid.org/sync9>: First true replace text CRDT
>       - Portals <https://braid.org/meeting-62/portals>: Generalized
>     patch semantics for moves, replaces, splices
>       - Time Machines <https://braid.org/drafts/time-machines>:
>     Generalization of OT & CRDT theory
>       - Braid-HTTP
>     <https://datatracker.ietf.org/doc/html/draft-toomim-httpbis-braid-http>:
>     Synchronization for HTTP
>
>     We could imagine formalizing the Braid group into this State
>     Synchronization group. It would look more broadly at
>     synchronization than any individual application, and would produce
>     specs that could be offered to other groups for standardization,
>     similar to how the QUIC group seeded HTTP/3.
>
>     I am very curious what the IETF thinks about this idea for a
>     working group, and would be very grateful to hear thoughts and
>     opinions from everyone.  Thank you very much!
>
>     Michael
>
>     [1] Relevant Braid-HTTP draft:
>     https://datatracker.ietf.org/doc/html/draft-toomim-httpbis-braid-http
>
>     _______________________________________________
>     dispatch mailing list
>     [e-mail]
>     https://www.ietf.org/mailman/listinfo/dispatch
>