{"type":"excalidraw","version":2,"source":"https://AwesomeSystemDesign.dev","elements":[{"angle":0,"strokeColor":"#6577aa","backgroundColor":"#eef1fc","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-1"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-1"}],"updated":0,"link":null,"locked":false,"id":"shape-0","type":"rectangle","seed":41,"x":16,"y":16,"width":288,"height":68,"customData":{"revealStep":1}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-1"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-1","type":"text","seed":114,"x":36,"y":35.7,"width":248,"height":28.6,"fontSize":22,"fontFamily":1,"text":"Char | ID | Visible?","originalText":"Char | ID | Visible?","textAlign":"left","verticalAlign":"middle","containerId":"shape-0","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":1}},{"angle":0,"strokeColor":"#6577aa","backgroundColor":"#eef1fc","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-2"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-3"}],"updated":0,"link":null,"locked":false,"id":"shape-2","type":"rectangle","seed":187,"x":16,"y":128,"width":288,"height":121.8,"customData":{"revealStep":2}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-2"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-3","type":"text","seed":260,"x":36,"y":146,"width":248,"height":85.8,"fontSize":22,"fontFamily":1,"text":"'A' | (1,A) | true\n'B' | (2,A) | true\n'C' | (3,A) | true","originalText":"'A' | (1,A) | true\n'B' | (2,A) | true\n'C' | (3,A) | true","textAlign":"left","verticalAlign":"middle","containerId":"shape-2","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":2}},{"angle":0,"strokeColor":"#a68a53","backgroundColor":"#fff7e6","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-3"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-5"}],"updated":0,"link":null,"locked":false,"id":"shape-4","type":"rectangle","seed":333,"x":16,"y":293.8,"width":288,"height":2438.4,"customData":{"revealStep":3}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-3"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-5","type":"text","seed":406,"x":36,"y":311.8,"width":248,"height":2402.4,"fontSize":22,"fontFamily":1,"text":"CRDTs for\nCollaborative Editing\n\nCore idea: Design the\ndata structure so\nthat concurrent\noperations ALWAYS\ncommute — no\ntransformation\nneeded.\n\nInstead of\nposition-based\noperations (Insert\nat pos 3),\nassign each\ncharacter a globally\nunique, ordered ID.\n\nSequence CRDT (e.g.,\nRGA, LSEQ, Yjs\nYATA):\n\nDocument: \"ABC\"\n\nInternal\nrepresentation:\n\nID format:\n(lamport_timestamp,\nuser_id)\nIDs are globally\nunique and totally\nordered.\n\nInsert 'X' between A\nand B:\n→ Create ID between\n(1,A) and (2,A)\n→ New ID: (1.5,B) or\nuse fractional\nindexing / tree-based\nIDs\n\nDelete 'B':\n→ Mark (2,A) as\ntombstone\n(visible=false)\n→ Never remove from\nstructure\n\nYjs (most popular\nCRDT library):\n\nUses YATA (Yet\nAnother\nTransformation\nApproach) algorithm:\n\nEach item has:\n- id: {client_id,\nclock}\n- left: reference to\nleft neighbor\n- right: reference to\nright neighbor\n- content: the\nactual character(s)\n- deleted: boolean\n(tombstone)\n\nConcurrent inserts\nat same position:\n→ Deterministic\nordering by client_id\n→ No transformation\nneeded!\n\nMerging: Just\nintegrate all items\ninto\nthe linked list\nfollowing YATA rules.\nAlways converges.","originalText":"CRDTs for\nCollaborative Editing\n\nCore idea: Design the\ndata structure so\nthat concurrent\noperations ALWAYS\ncommute — no\ntransformation\nneeded.\n\nInstead of\nposition-based\noperations (Insert\nat pos 3),\nassign each\ncharacter a globally\nunique, ordered ID.\n\nSequence CRDT (e.g.,\nRGA, LSEQ, Yjs\nYATA):\n\nDocument: \"ABC\"\n\nInternal\nrepresentation:\n\nID format:\n(lamport_timestamp,\nuser_id)\nIDs are globally\nunique and totally\nordered.\n\nInsert 'X' between A\nand B:\n→ Create ID between\n(1,A) and (2,A)\n→ New ID: (1.5,B) or\nuse fractional\nindexing / tree-based\nIDs\n\nDelete 'B':\n→ Mark (2,A) as\ntombstone\n(visible=false)\n→ Never remove from\nstructure\n\nYjs (most popular\nCRDT library):\n\nUses YATA (Yet\nAnother\nTransformation\nApproach) algorithm:\n\nEach item has:\n- id: {client_id,\nclock}\n- left: reference to\nleft neighbor\n- right: reference to\nright neighbor\n- content: the\nactual character(s)\n- deleted: boolean\n(tombstone)\n\nConcurrent inserts\nat same position:\n→ Deterministic\nordering by client_id\n→ No transformation\nneeded!\n\nMerging: Just\nintegrate all items\ninto\nthe linked list\nfollowing YATA rules.\nAlways converges.","textAlign":"left","verticalAlign":"middle","containerId":"shape-4","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":3}}],"appState":{"viewBackgroundColor":"#fbfbf8","gridSize":null},"files":{}}