The development of cyber-physical systems is crucial for effective implementation of technologies for smart cities applications. Middleware algorithms have been studied extensively for traditional distributed systems. It is natural to leverage the existing work by extending these traditional algorithms to apply to cyber-physical systems. This paper presents a number of challenges that must be addressed in extending traditional algorithms for cyber-physical systems. First, since traditional algorithms view the underlying networked system as a graph, we present a model for cyber-physical systems that formalizes various aspects of both the cyber-and the physical system in terms of graphs. Second, we identify challenges to be addressed in extending traditional algorithms to CPS for the proposed graph-based models.