Cyber Physical Systems (CPS) require a multitude of components interacting among themselves and with the users to perform automatic actions, usually under unpredictable or uncertain conditions. Multi-Agent Systems (MAS) have emerged over the years as one of the major technological paradigms regulating interactions and negotiations among autonomous entities running under heterogeneous conditions. As such, MAS have the potential to support CPS in implementing a highly reconfigurable distributed thinking. However, some gaps are still present between MAS’ features and the strict requirements of CPS. The most relevant is the lack of reliability, which is mainly due to specific features characterizing negotiation protocols. This paper presents a systematic literature review of MAS negotiation protocols aiming at providing a comprehensive overview of their strengths and limitations, examining both the assumptions and requirements set during their development. While this work confirms the potential of MAS in regulating the interactions among CPS components, the findings also highlight the absence of real-time compliance in current negotiation protocols. Strongly characterizing CPS, the capability to face strict time constraints could bridge the gap between MAS and CPS.