Sorry Gandolph, but I must agree with PAVB on this one.

Not that I am arguing with the great Tom Kyte, however. What he is saying is that committing, in and of itself, has absolutely no impact on performance. This, of course, is perfectly correct. However, in this case, we are not strictly talking about stand-alone performance, but rather multiple threads that are tripping over each other's locks.

Similarly, while Bitmap indexes are notorious for deadlocks (because they lock multiple rows), we can at least say that the example provided certainly had no bitmap indexes. So, let's assume for now that there are, as the poster says, no bitmap indexes.

What we have are multiple processes running concurrently that are trying to insert possibly the same records into the same table. And, most importantly, in a random order.

There are a few ways to alleviate this issue:

1 - Commit every record.
Nothing less will guarantee the elimination of the dealocks. As your example showed, all you need are a few inserts to cause a deadlock. Strictly speaking, all you need are two. Therefore, the only way to eliminate deadlocks by using commits is to commit every record. This has other implications, of course. First of all, doing a commit on every record will make the process somewhat slower. However, even without the deadlocks, you can easily be waiting on locks in many of your concurrent processes. If two processes have thousands of records in their batch and both try to insert record # 4 at the beginning of the batch, whichever one loses will be waiting until the winner finishes inserting the rest of the thousands of records in its batch before it can continue. So, performance without commits may well be much worse than the performance with commits.

2 - Order the INSERTS
The biggest problem here, as shown in your example, is that one process is trying to lock A, then B, while another process is trying to lock B, then A. If you order your inserts before they are performed (various ways to programatically accomplish this), then you could eliminate any possible deadlocks, although you may still experience long waits as described in solution 1.

3 - Insert into a staging table first.
This is an all-around better solution. This table would not have to have a unique index on the key column. - just insert away. Every once in a while, move the records into the real table. This can be done in multiple ways, such as:
a - Have a single process that runs every 5 minutes. It updates all the records that it currrently sees (committed) with some flag. It then does an INSERT INTO SELECT * FROM ST WHERE NOT EXISTS ( SELECT 1 FROM RT where RT.KEY = ST.KEY) followed by deleting all the records from the staging table that it previously flagged
b - Same as above, but have an error table that all the duplicates get moved to - saves the EXISTS()
c - Same as above, but with a MERGE, again saving on the EXISTS
There are varous ways this can be accomplished, but the idea is to remove the waits, the locks, and the deadlock possibility. You can also do direct-path inserts this way, which are must faster.

Anyway, there are some thoughts for you - let me know what you find.