Is there some algorithm for R/W lock graphs?

Question

Suppose we have resources A,B,C and their dependencies not cyclic:

B->A
C->A

Means B strongly depends on A and C strongly depends on A. For example: B,C is precomputed resources from A. So if A updates, B,C should be updated too. But if B updated - nothing changes except B.

And for the problem: Considering the fact that each node of graph can be accessed for Read or Write or Read/Upgrade to Write in multi-threaded manner, how one supposed to manage locks in such graph? Is there generalization of this problem?

Update

Sorry for not clear question. Here is also one very important thing: If for example A changes and will force B,C to be updated it means that the moment B and their dependencies updates - it will free write lock.

Answer 1

Your question is a blend of transaction - locking - concurrency - conflict resolution. Therefore models used in relational databases might serve your purpose.

There are many methods defined for concurrency control.

In your case some might apply depending of how optimistic or pessimistic your algorithm needs to be, how many reads or writes, and what is the amount of data per-transaction.

I can think of the two methods that can help in your case:

1. Strict Two-Phase Locking (SSPL or S2PL)

A transaction begins, A, B, C locks are being obtained and are kept until the end of the transaction. Because multiple locks are kept until the end of the transaction, while acquiring the locks a deadlock condition might be encountered. Locks can change during the transaction time.

This approach is serializable, meaning that all events come in order and no other party can make any changes while the transaction holds.

This approach is pessimistic and locks might hold for a good amount of time, thus resources and time will be spent.

2. Multiversion

Instead of placing locks on A, B, C, maintain version numbers and create a snapshot of each. All changes will be done to snapshots. At the end, all snapshots will replace the previous versions. If any version of A, B and C has changed then an error condition occurs and changes are discarded.

This approach does not place read or write locks meaning that will be fast. But in case of conflicts, if any version has changed in the interim, then data will be discarded.

This is optimistic but might spend much more resources in favor of speed.

Transaction log

In database systems there is also the concept of "transaction log". This means that any transaction being it completed or pending will be present in the "transaction log". So every operation done in any of the above methods is first done to the transaction log. Operations from the log will be materialized at the right moment in the main store. In case of failures the log is analyzed, completed transactions are materialized to the main store and the pending ones are just discarded.

This is used also in "log shipping" in order to ship the log to other servers for the purpose of replication.

Known Implementations

There are multiple in-memory databases that might prevent some hassle with implementing your own solution.

H2 provides also serializable isolation level that can match your use case.

go-memdb provides multiversion concurrency. This one uses an immutable radix tree algorithm, therefore you can look also into this one for details if you are searching to build your own solution.

Many more are defined here.