CPS: Breakthrough: Safe Protocols in Cyber-Physical Systems (CPS)
Lead PI:
Nicholas Maxemchuk
The objective of this research is to prove that cyber-physical systems are safe before they are deployed. The approaches the research investigates are extensions of approaches used to test communications protocols. The problems with cyber-physical systems are that 1) they are much more complicated than communications protocols, 2) time is a more critical component of these systems, and 3) in a competitive environment there are likely to be many implementations that must interoperate. The complexity of communications protocols is reduced by using a layered architecture. Each layer provides a well defined service to the next layer. This research is developing multi-dimensional architectures that reflect the different ways that the cyber-physical system interacts with the physical world. The techniques are evaluated on a driver-assisted merge protocol. An architecture for the merge protocol has four dimensions organized as stacks for communications, external sensors, vehicle monitoring and control, and timing. This architecture will also be useful during standardization. Timing increases verification complexity by increasing the number of potential execution paths. The research conducted in this project explores how to reduce the number of paths by synchronizing clocks and using simultaneous operations. This approach is reasonable because of the timing accuracy now available with GPS. A two step verification process is used that creates an unambiguous model of the cyber-physical system, first proving that the model is safe, then checking that each implementation conforms to the model. This reduces the number and cost of tests for a three-party merge protocol. Specifically, assuming there are N implementation versions for different manufacturers and models, this approach reduces the number of necessary interaction tests, which would be cubic in N, to a single model verification and N conformance tests.
Nicholas Maxemchuk

Nicholas F. Maxemchuk



·      Ph.D. Doctor of Philosophy, Systems Engineering, University of Pennsylvania, May 1975.

·      M.S. Moore School of Electrical Engineering, University of Pennsylvania, May 1970.

·      B.S. Bachelor of Electrical Engineering, The City College of New York, June 1968. (Graduated Magna Cum Laude).


Academic Experience

·      2001 - Present  Full Professor  Columbia University

·      2008 - Present  Chief Researsher        IMDEA Networks, Madrid

·      University of Melbourne, Visiting Academic Oct. 99.

·      Opponent: KTH Sweden, June 1997.

·      Department Visiting Committee, Comp. Sci., University of Texas at Austin 1989-92.


Non-Academic Experience

·      2009-2012    Consultant      NYC MTA

·      2008    Chief Scientist Telcordia

·      2007-2010       Consultant      Bell Labs, Murray Hill, NJ

·      Technical Advisory Board -  start-upEnrichnet 2000-2002

·      1996 - 2001     Technology Leader       AT&T Research Labs

·      Technical Advisory Board start-up - BrightLink Networks 1998->2001

·      1984 - 1996     Department Head AT&T Bell Laboratories

·      1976 - 1984     MTS     Bell Labs

·      1968 - 1976     MTS     RCA David Sarnoff Res. Cntr.


Current Membership in Professional Organizations

·      IEEE, Eta Kappa Nu and Tau Beta Pi


Honors and Awards

·      2006 IEEE Koji Kobayashi Award for Computer and Communications

·      1997 William R. Bennett Prize Paper Award for S. Low, N. F. Maxemchuk, S. Paul, "Anonymous Credit Cards and Its Collusion Analysis," IEEE Trans. on Networking, dec. 1996, vol. 4, no.6, pp 809-816

·      1996 R&D 100 Award for "Document Copying Deterrent System"

·      1989 Elected Fellow of the IEEE

·      1988 Leonard G. Abraham Prize Paper Award, for N. F. Maxemchuk, "Routing in the Manhattan Street Network," IEEE Trans. on Commun., May 1987, vol. COM-35, no. 5, pp. 503-512., also s elected for IEEE ComSoc 50th anniv. iss.

·      Selected for IEEE ComSoc 50th anniv. iss., and included in the DQDB standard, E. L. Hahne, A. K. Choudhury, N. F. Maxemchuk, "DQDB Networks With and Without Bandwidth Balancing," IEEE Trans. on Commun., Vol. 40, No. 7, July 1992, pp 1192-1204

Performance Period: 10/01/2013 - 09/30/2016
Institution: Columbia University
Sponsor: National Science Foundation
Award Number: 1329593