Lock Optimization and Deadlock Detection

Design and implement a lock manager for a distributed compute engine that supports high-throughput concurrent transactions while guaranteeing deadlock freedom. Your system must expose two APIs: acquire(lock_id, txn_id, timeout_ms) and release(lock_id, txn_id). All lock requests are exclusive. Internally you must (1) minimize the time any thread spends inside critical sections, (2) guarantee that no deadlock will ever occur, and (3) provide an O(E+V) cycle-detection routine that can be run on demand to prove that the global wait-for graph is acyclic at every moment. You may assume up to 100 000 locks and 100 000 concurrent transactions, 16-core machines, and sub-millisecond RPC latency. Describe the data structures, locking protocol, and deadlock-avoidance algorithm; give pseudocode for acquire/release; and analyze the worst-case time and space complexity of every operation.