How the Sync-Edge Order Prevents Deadlocks in BitChat

The sync-edge order prevents deadlocks by enforcing a strict hierarchical synchronization hierarchy where synchronous calls flow only in one direction (main thread → engine → bleQueue) while reverse communication remains strictly asynchronous.

BitChat's Bluetooth Low Energy (BLE) transport layer implements a rigorous concurrency model that eliminates circular waits through a carefully designed sync-edge order. According to the permissionlesstech/bitchat repository, this architecture establishes a unidirectional flow of synchronous operations that makes deadlocks impossible by construction.

The Hierarchical Synchronization Model

The sync-edge order defines three distinct synchronization zones arranged in a strict hierarchy. This structure ensures that any synchronous operation moves strictly downstream, preventing the circular dependencies that cause deadlocks.

Zone	Direction of Synchronous Calls
Main / test threads → Engine	sync
Engine → bleQueue	sync
Engine → noise / identity queues (leaves)	async (reverse direction)

As documented in docs/BLE-ARCHITECTURE-V3.md (lines 68-78), the flow follows this pattern:

main / test threads ──sync──▶ engine ──sync──▶ bleQueue
                                   └──sync──▶ noise / identity queues (leaves)

Core Rules Enforcing Deadlock Freedom

Unidirectional Sync Constraints

No component may issue synchronous calls against the hierarchy. The bleQueue and cryptographic (noise) queues can only reach the engine via async dispatch, never through sync operations. Conversely, the engine never dispatches synchronous work back to the main thread. This unidirectional property ensures that wait-for graphs cannot form cycles.

The onEngine Contract

All code requiring execution on the engine queue must use the onEngine helper as its sole entry point. This function contains debug-time assertions that trap any reverse-direction synchronous calls. The contract is codified in bitchatTests/Services/BLEQueueContractTests.swift (lines 25-27), which asserts that only onEngine may synchronously enter the engine queue. Attempting to bypass this helper violates the architectural invariants and triggers test failures.

Critical Section Discipline

Strict rules govern code executing within critical sections:

• Noise-manager critical sections: When entered from an engine slot, code must not call back into the engine synchronously, as this would cause self-deadlock.
• BLEQueue critical sections: Any values needed from the engine must be passed as arguments rather than fetched via onEngine, eliminating synchronous round-trips that could block the queue.

Implementation Examples

The following patterns demonstrate correct and incorrect usage of the sync-edge order:

// Correct: schedule work on the engine from the main thread
onEngine {
    engine.handle(event: .peerJoined(id))
}

// WRONG – would cause a deadlock if allowed (not permitted by contract)
bleQueue.sync {
    // ❌ cannot call onEngine here; would sync‑wait back to engine
    onEngine { … }
}

// Correct: notify the engine from the noise queue asynchronously
noiseQueue.async {
    engine.notify(event: .circuitBuilt)
}

In the first snippet, onEngine safely moves execution to the serial engine queue from the main thread. The second snippet illustrates a prohibited pattern that the contract tests reject because it creates a synchronous wait from bleQueue back to the engine. The third snippet demonstrates the permitted asynchronous direction from leaf queues back to the engine.

Key Architectural Files

The sync-edge order is implemented across several critical files in the repository:

• docs/BLE-ARCHITECTURE-V3.md – Defines the sync-edge order hierarchy and documents the deadlock prevention rationale
• bitchatTests/Services/BLEQueueContractTests.swift – Enforces the contract that only onEngine may synchronously enter the engine
• BLEService.swift – Implements the onEngine helper and provides the concrete entry point for main-thread → engine synchronization
• NoiseQueue.swift – Demonstrates the leaf queue implementation that can only async-dispatch toward the engine
• BLEQueue.swift – Implements the bleQueue side that must only sync-wait forward to the engine

Summary

• The sync-edge order creates a three-tier hierarchy: main thread → engine → bleQueue
• Synchronous calls flow strictly downward; reverse communication uses asynchronous dispatch only
• The onEngine helper serves as the exclusive entry point for synchronous engine access, guarded by debug assertions
• Critical sections in leaf queues must never synchronously callback to the engine
• The architecture is validated by BLEQueueContractTests.swift, which ensures deadlock freedom by construction

Frequently Asked Questions

What happens if code violates the sync-edge order?

The system includes debug-time checks within the onEngine helper that trap reverse-direction synchronous calls during testing. Additionally, BLEQueueContractTests.swift asserts that only onEngine may synchronously enter the engine, causing test failures if developers attempt to bypass the hierarchy.

Why can't leaf queues like noiseQueue use synchronous calls to the engine?

Allowing leaf queues to sync-wait on the engine would create a potential circular dependency. If the engine were simultaneously waiting on a resource held by the leaf queue (via async callback), both threads would block indefinitely. By restricting leaf-to-engine communication to async only, the architecture guarantees that the engine never blocks on its children.

How does this design impact performance?

The sync-edge order trades occasional redundancy (passing values as arguments rather than fetching them) for guaranteed liveness. The use of async dispatch for reverse communication adds minimal overhead compared to the cost of potential deadlocks, which would freeze the BLE transport entirely.

Where is the sync-edge order documented in the source code?

The primary documentation resides in docs/BLE-ARCHITECTURE-V3.md at lines 68-78, with enforcement mechanisms implemented in bitchatTests/Services/BLEQueueContractTests.swift. The concrete queue implementations in BLEService.swift, NoiseQueue.swift, and BLEQueue.swift embody these rules in their public interfaces.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}