Researchers propose solution to 25-year-old computer logic puzzle
Researchers from the Department of Mathematics and Computer Science have developed a recipe for how parallel calculations in computers avoid influencing each other under certain circumstances. This is important for the development of future computer systems, including artificial intelligence.
The everyday life of modern people is largely influenced by technology. In recent years, technology has made it possible to develop computer systems which, due to their ability to operate in parallel tracks, can give us answers to our questions almost before we have formulated them.
Despite the many applications, the underlying methods behind the screen still have some challenges, including in the field of computer networks. For one of these puzzles, researchers from SDU now propose a solution together with their scientific colleagues abroad.
Technological progress in short time
Computer science has been developing at high pace over the past half century. In very few decades, its evolution has moved us from typewriters to computers that initially allowed us to text and perform simple games, but now can recognize voices, faces and even beings in the form of artificial intelligence.
One of the greatest advances in computer science has been the development of systems that can work in parallel. Information that in previous computer systems ran back and forth by the same path can now travel through many different paths at the same time, while still ensuring a result that is consistent with the one-path computation.
This way of sending information in parallel tracks is not only used in supercomputers, but also in our everyday networks like the internet, where you can send a message to your neighbor while your neighbor simultaneously is writing to you or to somebody else. Everybody receives the correct messages, because with parallel tracks, the messages do not affect each other along the way.
Problems in the parallel world
However, the many applications of parallel calculations are not entirely without problems. Problems arise when the information that travel across the network are not independent. The chosen paths through the network, or even the slightest different timing among them, can therefore determine what the result is. This is a problem, because it means that it is possible to run the same calculation twice and get two different results.
It is currently not possible to predict all the possible execution paths for a program, because the number of possible interactions among parallel components in a computer system is very high – much higher than it is possible to work with.
A way to solve this problem is by developing solid principles and methods that can help programmers in tackling this complexity. Associate Professor Fabrizio Montesi from the Department of Mathematics and Computer Science (IMADA) together with his colleagues has developed a new approach to addressing this problem arising from the parallel transport of information.
Inspiration from mathematics gives new method
The proposed solution is by using a method called Classical Processes (CP). The researchers used CP and so-called linear logic to describe the concept of “parallel execution” as a logical statement, i.e. a clearly formulated statement that works for all possible scenarios.
They named their new method HCP, which stands for Hypersequent Classical Processes. It was presented for the first time at the conference "Symposium on Principles of Programming Languages" (POPL 2019) in Lisbon, Portugal. This is the 46th time the conference was held when it took place in January this year. The paper is offered open access by the Proceedings of the ACM in Programming Languages and can be read here.
The paper was made by Associate Professor Fabrizio Montesi from the Department of Mathematics and Computer Science at SDU along with Postdoc Marco Peressotti and their colleague, Wen Kokke from Edinburgh University.