Using a KVS transaction processing mechanism, four lock states are managed. When a local transaction refers to and updates a map entry, the local transaction is graded up to a global transaction. Start processing as the global transaction is first performed to determine a transaction ID. A committed value, a value being updated, and a transaction ID being updated are then inserted into all map entries for which LX locks are being acquired at present. Another local transaction is then started for all map entries for which S locks are being acquired at present to acquire S locks. Next, the original local transaction is committed. As a result, the LX locks acquired are graded up to GX locks. After the termination of the global transaction as the waiting target, acquisition of S locks (GX locks) is tried as a global transaction.