Concurrent multiple negotiation (CMN) provides a mechanism for an agent to simultaneously conduct more than one negotiation. There may exist different interdependency relationships among these negotiations and these interdependency relationships can impact the outcomes of these negotiations. The outcomes of these concurrent negotiations contribute together for the agent to achieve an overall negotiation goal. Handling a CMN while considering interdependency relationships among multiple negotiations is a challenging research problem. This paper: 1) comprehensively highlights research problems of negotiations at concurrent negotiation level; 2) provides a graph-based CMN model with consideration of the interdependency relationships; and 3) proposes a colored Petri net-based negotiation protocol for conducting CMNs. With the proposed protocol, a CMN can be efficiently and concurrently processed and negotiation agreements can be efficiently achieved. Experimental results indicate the effectiveness and efficiency of the proposed protocol in terms of the negotiation success rate, the negotiation time and the negotiation outcome.