When two stored procedures get into a deadlock situation, sql server makes a guess and kills the one which is less important.

The resolution is to rerun the stored procedure manually.

The long term fix is not to schedule the stored procedures (it may be one running in two different session) at the same time if it is a batch job.

If frequently used stored procedure, it has to be rewritten so it does not have convoluted logic.