Home > What's New? > Events > 2013 > Synchronized Protocols: From Safe Cyber-­Physical Systems to the Next ARPA-­Net

Synchronized Protocols: From Safe Cyber-­Physical Systems to the Next ARPA-­Net

Nick Maxemchuk, Chief Researcher, Institute IMDEA Networks; Professor, Electrical Engineering Department, Columbia University in the City of New York, USA
3 June 2013 -
4:00pm to 6:00pm

Room 4.1.F03 - Building Torres Quevedo, University Carlos III of Madrid, Avda. Universidad, 30, 28911 Leganés – Madrid

We are entering an era where accurately synchronized clocks are economical and are becoming commonplace. Commercial GPS units synchronize clocks within 10’s of micro-­‐seconds. Chip sets that implement the IEEE 1588 standard are synchronizing clocks within a fraction of a nano-­‐second to improve the probability of collisions in particle colliders.

The advances in clock technologies can change the way we think about distributed systems and the protocols that control their interactions. We can construct networks of devices that interact over unreliable communications channels, but follow the same sequence of operations and simultaneously execute the operations. This simplifies the way we verify the protocols and test their implementation. We can test the protocol execution sequences using techniques developed for finite state machines, such probabilistic verification, rather than techniques developed for systems with multiple, independent timers, such as timed automata. We have developed a shared memory strategy that coordinates deadlines, and allows us to use protocol conformance testing procedures, such as the Rural Chinese Postman Algorithm, on time-­‐based systems. 

We will demonstrate the use of synchronized protocols in collaborative driving systems. In particular, we will describe a lock protocol that has characteristics that have not been obtained in systems that use timers. These characteristics are necessary to guarantee the safe operation of an automated merge protocol that we are testing.

Cyber-­‐physical systems interact with the physical world in several ways. We have developed a multi-­‐dimensional architecture that reflects these interactions and creates multiple stacks, similar to those used for communications. In an automated driving system, the dimensions include the communications channel, sensors that measure the position of a vehicle relative to other vehicles, sensors that monitor the operation of the vehicle, and devices that provide accurate clocks.

The architecture allows us to decompose the total system into smaller pieces that can be implemented and tested separately. Based on this architecture we have specified a protocol that assists drivers who are merging between cars in a lane on a highway. We have verified that the protocol will not cause an accident for combinations of rare events, including; loss of communications, failures or inaccuracies of sensors, mechanical failures in the automobile, aggressive drivers who are not participating in the system, and obstacles on the roadways.

We are currently investigating the use of synchronized protocols to coordinate traffic signals and create multiple, intersecting green waves that are modified to reflect the current traffic flows. The objective is to eventually coordinate the traffic signals and vehicles. The same techniques can be applied to a next generation ARPA-­‐Net, to increase traffic flows and better service time-­‐critical traffic.

I refer to the network as the next generation ARPA-­‐net, rather than the next generation Internet because the ARPA-­‐net introduced a disruptive technology that changed capacity allocation from fixed, bandwidth allocation to an on-­‐demand model by using storage. The Internet is just the services that the new technology enabled. Synchronized nodes and an increased use of processing for scheduling may be the next disruptive technology. It can provide on-­‐demand communications with less dependency on storage and less delay.

Short Bio: 

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).

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,ACMNSF Expert Group and the United Nations. He has published three award winning papers and had two of his publications voted into the Communication Society 50th 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.


Institute IMDEA Networks

More Info: 

This event will be conducted in English