Deadlocks são um problema clássico em banco de dados transacionais, mas eles não são perigosos, a menos que eles sejam tão frequentes que você não possa executar certas transações. Normalmente você tem que escrever suas aplicações de forma que elas sempre estejam preparada a reexecutar uma transação se for feito um roll back por causa de deadlocks.
          O InnoDB utiliza bloqueio automático de
          registro. Você pode obter deadlocks mesmo no caso de
          transações que inserem ou deletam uma única linha. Isto
          ococrre porque estas operações não são realmente
          'atômicas': elas automaticamente atribuem travas aos
          (possivelmente muitos) registros se índices da linha
          inserida/deletada.
        
Você pode lidar com deadlocks e reduzí-lo com os seguintes truques:
              Use SHOW INNODB STATUS em versões do
              MySQL posteriores a 3.23.52 e 4.0.3 para determinar a
              causa do último deadlock. Isto pode lhe ajudar a
              sintonizar a sua aplicação a avitar travas.
            
Sempre estar preparado para reexecutar uma transação se ela falhar em um deadlock. Deadlocks não sÃo perigosos. Apenas tente de novo.
Commit sua transações com frequência. Transações pequenas têm menos chaces de colidir.
              Se você estiver utilizando as travas de leitura
              SELECT ... FOR UPDATE ou ...
              LOCK IN SHARE MODE, tente usar um nível de
              isolamente mais baixo READ COMMITTED.
            
Accesse as suas tabelas e linha em uma ordem fixa. Assim as transações formarão filas ordenadas e não entrarão em deadlock.
              Adicione índices bem escolhidos a sua tabela. Então a
              suas consultas precisarão varrer menos registros de
              índice e consequentemente atribuirão menos locks. Use
              EXPLAIN SELECT para fazer o MySQL
              selecione índices apropriados a sua consulta.
            
              Use menos locks: se você pode utilizar um
              SELECT para retornar dados de uma copia
              de banco de dados antiga, não adicione a cláusula
              FOR UPDATE ou LOCK IN SHARE
              MODE. Usar o nível de isolamento READ
              COMMITTED é bom aqui, pois cada leitura
              consistente dentro da mesma transação lê da sua
              própria cópia atual.
            
              Se nada ajudar, serialize suas transações com bloqueio
              de tabela: LOCK TABLES t1 WRITE, t2 READ, ... ;
              [faz algo com tabelas t1 e t2 aqui]; UNLOCK
              TABLES. Bloqueio de tabela faz com que suas
              transações se enfilerem em ordem e deadlocks serão
              evitados. Note que LOCK TABLES inicia
              implictamente uma transação, assim como o comando
              BEGIN, e UNLOCK
              TABLES finaliza implicitamente uma transação
              em um COMMIT.
            
              Outra solução para colocar transações em série é
              criar uma tabela 'semáforo' auxiliar onde exista apenas
              uma única linha. Cada transação atualiza esta linha
              antes de acessar outra tabela. Deste modo todas as
              transações acontecem em série. Note que o algoritmo de
              detecção automático de deadlock do
              InnoDB também funciona pois a trava de
              série é uma trava de registro. Na trava de tabela do
              MySQL nós temos que recorrer ao método do tempo limite
              para resolver um deadlock.
            
This is a translation of the MySQL Reference Manual that can be found at dev.mysql.com. The original Reference Manual is in English, and this translation is not necessarily as up to date as the English version.

