Riddles on Rails
A talk from EMF 2016 by Dan Hagon
On Friday August 5, 2016 at – in Stage B
How might you re-order wagons in trains without lifting them off the tracks or prevent trains from colliding when you cannot see where they are? What does a train travelling through a station indicate about simultaneous events and how do railway junctions lead to problems in ethics? This talk combines several interesting problems in railway operation, within the context of real railway operations, showing surprising applications in computing they inspired.
Shunting yards present logistical problems arising from the marshalling of wagons. The UK's former largest yard near Sheffield was so complex it required a paper tape era computer to operate. However, in computing we find their structure used in diagrams for programming language grammars and a type of parsing algorithm known as the shunting yard algorithm which we'll see in operation.
The computer scientist Edsger Dijkstra devised many railway-themed computing ideas. Dijkstra's algorithm finds the shortest route between stations, a method independently discovered by early rail planners in the UK. Thanks to railway signalling, Dijkstra introduced semaphores into concurrent programming. We'll show how the concept works both for railways and concurrent systems and outline the historical context of rail accidents.
Railways introduced universal time. Einstein's celebrated thought experiment involving a moving train changed how we understood simultaneous events. Distributed systems rely on proper ordering of events. We'll explore these problems plus solutions.
The talk includes the Trolley Problem that first arose in philosophy but is now the subject of its own vibrant meme.