Our objective is to guarantee that vehicles that coordinate their operations will operate safely with all of the other vehicles, implemented by all of the other manufacturers, on the roadway.

In 1984 the telephone network was opened to competition. Bell Labs was responsible for guaranteeing that the equipment connected to the network would interoperate with all of the other equipment in the network. We verified the interoperability of a large number of implementations by breaking the problem into two parts. 1) We proved that the protocols that define the interoperation of devices are unlikely to fail. And, 2) we developed a black box testing procedure to guarantee that a particular implementation correctly implemented the protocol. In this way we avoided pairwise testing of a large number of implementations.

We are applying the same strategy to testing the protocols that define the coordination of connected vehicles. However, the implementations are orders of magnitude more complicated than anything in the telephone network, time is a critical component in the interaction between vehicles, and the penalty for being wrong may be measured in the loss of human lives.

We will describe an architecture that divides this complicated problem into more manageable pieces, and use synchronized clocks, made possible by GPS, to significantly reduce the number of possible execution sequences. Synchronized clocks have also resulted in a new class of fail-safe protocols, and have simplified the use of the conformance testing techniques that were used in the telephone network. We use these techniques to verify that our driver assisted protocol merge protocol will not cause an accident for combinations of mechanical failures, communications failures, interference by non-participating drivers, and unexpected obstructions in the roadway.

About Nick Maxemchuk

Nicholas Maxemchuk, a networking pioneer, holds a permanent double appointment as Professor at the world-leading Columbia University of New York City (New York, USA) and Chief Researcher at IMDEA Networks.

He holds a M.Sc. in Electrical Engineering and a Ph.D. in Systems Engineering, both from the University of Pennsylvania (Philadelphia, USA). Before joining Columbia University and IMDEA Networks, Nick Maxemchuk held the position of Technical Leader at AT&T Research Laboratories (1996 – 2001) and, prior to that, was the Head of Distributed Systems Research Department at AT&T Bell Laboratories (1976 – 1996). From 1968 to 1976 he was a member of the technical staff at the RCA David Sarnoff Research Center in Princeton, New Jersey.

Many of his far-sighted contributions to computer-communications networking have been years ahead of their time and have led to the development of groundbreaking new systems. His invention of Dispersity Routing in the 1970s, for example, has recently been applied to ad hoc networks. In 2006, his achievements in the field were recognized by the world’s leading professional association for the advancement of technology, the IEEE, when he was awarded the prestigious 2006 IEEE Koji Kobayashi Computers and Communications Award.

Amongst other awards that he has been given, some of the most noteworthy are the RCA Laboratories Outstanding Achievement Award in 1970, the Bell Laboratories Distinguished Technical Staff Award in 1984, the IEEE’s Leonard G. Abraham Prize Paper Award in 1985 and 1987, and the William R. Bennett Prize Paper Award in 1997.  He was also made a fellow of the IEEE in 1989, and received the 1996 R&D 100 award for his work on document marking

As well as owning 30 patents and publishing three books, Nicholas Maxemchuk has co-authored over 100 publications. His strong reputation as an eminent scientist has earned him many editorial and advisory positions with organizations including the IEEE,ACM, NSF Expert Group and the United Nations. He has published three award winning papers and had two of his publications voted into the Communication Society50th Anniversary Issue. He is a member of the Board of Governors of the Armstrong Foundation and also works as a Consultant on Data Networks in Transportation Networks for The National Academies/Transportation Research Board.

Personal site