Deadlock situation, why??

Why is following deadlock situation possible?

As you can see from SHOW INNODB STATUS the update selects two different request-rows by its ID.

LATEST DETECTED DEADLOCK

090402 16:06:16
*** (1) TRANSACTION:
TRANSACTION 0 183582, ACTIVE 2 sec, OS thread id 204 starting index read
mysql tables in use 1, locked 1
LOCK WAIT 7 lock struct(s), heap size 1024, undo log entries 192
MySQL thread id 9, query id 131757 localhost 127.0.0.1 root Updating
UPDATE ERA_CASE.REQUEST SET timestampForLVS:=IF(state=‘confirmed’,IFNULL(timestampForLVS ,‘2009-04-02 16:06:16.33’),timestampForLVS),state:=‘transferred’ WHERE id=257698049538
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 920 n bits 208 index PRIMARY of table era_case/request trx id 0 183582 lock_mode X locks rec but not gap waiting
Record lock, heap no 95 PHYSICAL RECORD: n_fields 16; compact format; info bits 0
0: len 8; hex 8000003c00002e02; asc < . ;; 1: len 6; hex 00000002cd1c; asc Í ;; 2: len 7; hex 00000008ca3de2; asc Ê=â;; 3: len 3; hex 8147bd; asc G½;; 4: len 8; hex 800000340000198a; asc 4 ?;; 5: len 1; hex 01; asc ;; 6: len 2; hex 3420; asc 4 ;; 7: len 3; hex 8fb27a; asc ²z;; 8: SQL NULL; 9: SQL NULL; 10: len 4; hex 86123a57; asc ? :W;; 11: len 0; hex ; asc ;; 12: len 1; hex 0b; asc ;; 13: SQL NULL; 14: len 1; hex 04; asc ;; 15: len 4; hex 49d4c658; asc IÔÆX;;

*** (2) TRANSACTION:
TRANSACTION 0 183580, ACTIVE 2 sec, OS thread id 2620 starting index read, thread declared inside InnoDB 500
mysql tables in use 1, locked 1
5 lock struct(s), heap size 1024, undo log entries 197
MySQL thread id 11, query id 131761 localhost 127.0.0.1 root Updating
UPDATE ERA_CASE.REQUEST SET timestampForLVS:=IF(state=‘confirmed’,IFNULL(timestampForLVS ,‘2009-04-02 16:06:16.33’),timestampForLVS),state:=‘transferred’ WHERE id=257698049537
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 920 n bits 208 index PRIMARY of table era_case/request trx id 0 183580 lock_mode X locks rec but not gap
Record lock, heap no 95 PHYSICAL RECORD: n_fields 16; compact format; info bits 0
0: len 8; hex 8000003c00002e02; asc < . ;; 1: len 6; hex 00000002cd1c; asc Í ;; 2: len 7; hex 00000008ca3de2; asc Ê=â;; 3: len 3; hex 8147bd; asc G½;; 4: len 8; hex 800000340000198a; asc 4 ?;; 5: len 1; hex 01; asc ;; 6: len 2; hex 3420; asc 4 ;; 7: len 3; hex 8fb27a; asc ²z;; 8: SQL NULL; 9: SQL NULL; 10: len 4; hex 86123a57; asc ? :W;; 11: len 0; hex ; asc ;; 12: len 1; hex 0b; asc ;; 13: SQL NULL; 14: len 1; hex 04; asc ;; 15: len 4; hex 49d4c658; asc IÔÆX;;

An UPDATE, or a DELETE generally set record locks on every index record that is scanned in the processing of the SQL statement. It does not matter whether there are WHERE conditions in the statement that would exclude the row. InnoDB does not remember the exact WHERE condition, but only knows which index ranges were scanned. If the locks to be set are exclusive, InnoDB also retrieves the clustered index ( in your case it’s id) record and sets a lock on it.

You might investigate MySQL’s SELECT … FOR UPDATE syntax and use it before your updates.