Investigating deadlocks can be a bit of a tricky one.
The first thing I would do is get an SQL Administrator to get a Deadlock Graph when it occurs.
From this you can determine the following:
Is the deadlock against the K2 Database or a custom Database
Is it directly against a table or when a Stored Procedure executes.
If against a custom Database, a SQL Developer might need to optimise the Table(s)/Stored Procedure to avoid the deadlocks.
If it is against the K2 Database, I would suggest logging a Support Ticket on the K2 Customer Portal for assistance.
I have seen some issues recently related to Deadlocks. The issues were related to roles that were deleted and set to dynamic within K2.
When navigating to K2 Management or K2 Workspace (Legacy), a role will show here: Workflow Server > Workflows > [Project Name] > Workflow > Roles.
However, when looking for that same role within Management or Workspace under Users > Roles (Management Console > Roles for K2 Workspace), the role does not exist here as it was previously deleted.
Please see this KB article for more information on this issue. http://help.k2.com/support-services/kbt134729
If you think you are having the same issue and you get to the end of the KB article, you may need to submit a support ticket. There is a possibility that support will have to assist you with removing some of the orphaned data related to the role being deleted.