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

3 Jun

Nick Maxemchuk, Chief Researcher, Institute IMDEA Networks; Professor, Electrical Engineering Department, Columbia University in the City of New York, USA

External Presentation (IN Speaker)

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.


Personal site


This event will be conducted in English


  • Location: Sala 4.1.F03 – Edificio Torres Quevedo, Universidad Carlos III de Madrid, Avda. Universidad, 30, 28911 Leganés – Madrid

  • Organization: IMDEA Networks Institute
  • Time: 04:00 pm
  • Add to Calendar: iCalendar Outlook Google