SyncText - A CRDT-Based Collaborative Text Editor

A real-time collaborative text editing system that uses Conflict-Free Replicated Data Types (CRDT) for lock-free synchronization between multiple users.

Project Overview

SyncText allows multiple users (3-5) to edit the same document simultaneously with automatic conflict resolution using the Last-Writer-Wins (LWW) strategy. The system operates entirely lock-free, relying on CRDT properties for consistency.

Features

Part 1: User Creation & Local Editing (30%)

• User registration in shared memory registry
• Automatic file change detection using file monitoring
• Real-time terminal display of document state
• Change tracking with line and column precision
• Support for up to 5 concurrent users

Part 2: Broadcasting via Message Passing (20%)

• POSIX message queues for inter-process communication
• Multi-threaded architecture (main thread + listener thread)
• Automatic broadcasting after every 5 operations
• Real-time update delivery to all active users

Part 3: CRDT-Based Merging (50%)

• Conflict detection based on line and column overlap
• Last-Writer-Wins (LWW) conflict resolution
• Timestamp-based operation ordering
• Automatic document synchronization
• Convergence guarantee across all users

System Requirements

Platform

• Linux (Ubuntu 20.04 or later recommended)
• GCC compiler (version 9.4.0 or later)

Dependencies

• pthread library (POSIX threads)
• rt library (POSIX real-time extensions)
• Standard C libraries

Compilation Instructions

Build the project:

make

This will compile all source files and create the editor executable.

Clean build artifacts:

make clean

Full cleanup (including shared memory and message queues):

make cleanall

Execution Instructions

Running Multiple Users

Open separate terminals for each user and run:

Terminal 1:

./editor user_1

Terminal 2:

./editor user_2

Terminal 3:

./editor user_3

You can also use the Makefile shortcuts:

make run1  # Terminal 1
make run2  # Terminal 2
make run3  # Terminal 3

Editing Workflow

1. Start the editor program with a unique user_id
2. The program creates a local document file: <user_id>_doc.txt
3. Open this file in any text editor (vim, nano, gedit, VS Code, etc.)
4. Make changes and save the file
5. The program automatically detects changes and displays them
6. Changes are broadcast to other users after every 5 operations
7. Conflicts are automatically resolved using CRDT principles

Example Session

# Terminal 1
$ ./editor user_1
Starting SyncText Editor for user_1
========================================

Registered as user_1
Message queue: /queue_user_1
Message queue created: /queue_user_1
Creating initial document: user_1_doc.txt
Active users: user_1

You can now edit user_1_doc.txt in any text editor.
Changes will be detected and synchronized automatically.
Press Ctrl+C to exit.

========================================
Document: user_1_doc.txt
Last updated: 14:05:30
----------------------------------------
Line 0: Hello World
Line 1: This is a collaborative editor
Line 2: Welcome to SyncText
Line 3: Edit this document and see real-time updates
----------------------------------------
Active users: user_1
Monitoring for changes...
========================================

File Structure

.
├── common.h              # Common header with data structures and declarations
├── editor.c              # Main program with monitoring loop and threading
├── user_management.c     # User registration and shared memory management
├── file_monitor.c        # File monitoring and change detection
├── message_queue.c       # Message queue operations and broadcasting
├── crdt_merge.c          # CRDT merge algorithm and conflict resolution
├── utils.c               # Utility functions
├── Makefile              # Build configuration
├── README.md             # This file
└── DESIGNDOC.md          # Design documentation

How to Test

Test 1: Non-Conflicting Edits

1. Start 2-3 users in separate terminals
2. Each user edits different lines in their document
3. Save the files
4. Verify all users see all changes after synchronization

Test 2: Conflicting Edits

1. Start 2 users
2. Both users edit the same line at approximately the same time
3. Save both files
4. Verify that the update with the later timestamp wins
5. Check that both users converge to the same final state

Test 3: Dynamic User Join

1. Start user_1 and user_2
2. Make some edits
3. Start user_3
4. Verify user_3 can see existing users
5. Make edits from all users and verify synchronization

Test 4: Multiple Operations

1. Start multiple users
2. Make 5+ changes rapidly in one user's document
3. Verify broadcasting happens after 5 operations
4. Check that all users receive and merge the updates

Troubleshooting

"Failed to initialize shared memory"

• Run make cleanall to remove stale shared memory segments
• Ensure you have permissions to create shared memory

"Failed to initialize message queue"

• Run make cleanall to remove stale message queues
• Check /dev/mqueue/ for existing queues

Changes not detected

• Ensure you're saving the file after editing
• Check that the file modification time is changing
• Verify the monitoring interval (default: 2 seconds)

Users not seeing each other

• Ensure all users are running on the same machine
• Check that shared memory is properly initialized
• Verify user registration with active user list

Exiting the Program

Press Ctrl+C in any terminal to gracefully shut down that user. The program will:

1. Unregister the user from shared memory
2. Close and remove the message queue
3. Clean up resources

Notes

• The system is completely lock-free, using atomic operations and CRDT properties
• All users must run on the same machine (shared memory limitation)
• Maximum 5 concurrent users supported
• Document files are automatically created with initial content
• Synchronization happens after every 5 operations or periodically
• Timestamps are in milliseconds for precise conflict resolution

Author

Computing Lab (CS69201) Project SyncText - CRDT-Based Collaborative Text Editor