The Goal: an Error-Free Network

Distributed computing issues are becoming increasingly more critical, as we advance towards a more computerized existence. Dr. Ran Gelles (36) focuses on combining coding theories with distributed computing, and studies computation performance on communication networks with communication errors. “Today, issues of failed communication arise when a few computers need to communicate with each other, for instance, when performing calculations on clouds, which are essentially a distributed network.

Almost every large company providing services to a large number of users worldwide (e.g. Google, Facebook, etc.), operates a distributed network of computers and servers. In the future, similar issues may occur. Take, for instance, the case of autonomous cars, when each independent car must communicate with the other cars on the road, so they can merge into traffic and avoid accidents,” explain Gelles. “But if the communication network distorts the information transferred between the computers – the entire computation process becomes meaningless. The field in which fail-safe computations are developed is called Coding for Interactive Protocols.

Gelles’ academic career began when he became an undergrad Computer Engineering student in the Technion, as part of the IDF’s academic reserves program for high school students, deferring their army service in order to first pursue an academic degree. After graduating and completing his army service (in the same field), Gelles completed an MSc in Computer Sciences in the Technion, followed by a PhD at UCLA and a Post Doc at Princeton. He joined Bar-Ilan’s Faculty of Engineering last year. “I chose BIU’s Faculty of Engineering because it’s a young, lively faculty, with a lot academic and scientific advancement potential. I am delighted I chose Bar-Ilan,” he says. As part of his academic route he studied cryptography, cyber security and quantum cryptography. These days he focuses on coding for interactive protocols, and tries to deepen our knowledge of different outlines of multiparty interactive coding protocols. “A common outline in distributed networks is that each computer sees only itself and its immediate neighbors, but not other computers in its network. One of the most basic algorithms in distributed networks, one that’s been around since the 1970s, creates a “tree” of communication channels. Using this tree structure, each computer “knows” how to communicate with other computers in the network, even if it can’t see them. Like leaves on a tree, that can “see” the branch they grow on, the branches see the tree they grow on, and so forth. But when the network is faulty, even the most basic tree construction may fail, causing, in turn, issues of failed routing of information or even loss of information for applications that assume an underlying tree structure. It is extremely difficult to fix this construction in a setting of distributed computing, since none of the elements within the network can view the entire board, or supervise the construction of the tree.”

The obvious solution to this problem is to feed the computers with the entire network structure, and then each of them can view the whole network, and independently construct the routing tree. “It’s a relatively easy solution, but an expensive one. It requires endless network communication resources, and considering the fact that networks can contain hundreds of millions of intersections, such as the internet, no computer in the world can ascertain this whole network,” explains Gelles. “Our solution resolves these issues without having to teach any computer the structure of the entire network, and without transmitting a huge amount of data between computers. The solution is distributed, and although no one computer views the whole network, each computer learns only the information required for its role in constructing the tree.”

The solution was developed by Dr. Gelles in collaboration with Dr. Keren Censor-Hillel of the Technion and Dr. Bernhard Haeupler of Carnegie Mellon University. “Our solution for the tree construction overcoming corrupted communication basically circumvents the problem by sending void messages. That is, we establish the tree simply by sending and receiving messages, according to the order in which they were received, and the sender’s identity. This way, even if a certain message contains erroneous information, it’s inconsequential, since we ignore the message contents anyway. The only relevant data is that a message was sent and received at the right time and place. Once our tree is completed, we use it with coding techniques based on the assumption that the network is constructed as a tree, in order to complete any possible distributed computation in a fail-safe fashion, and at relatively low communication costs.”

Coding for interactive protocols is a relatively new discipline – only four or five years old – and still relatively theoretical. “I believe that in the future this field will help develop improved, noise-resilient communication systems, and render the computations made on communication networks such as the internet, more stable and effective,” says Gelles. “Coding techniques developed in this field also affect other disciplines, and have led to the development of other noise-resilient systems, such as fail-safe electronic circuits, or data security systems.”

A comprehensive article written by Dr. Gelles about the fundamental principles of this domain, as well as the developments made in the field in the past few years, has recently been accepted to the Foundations and Trends in Theoretical Computer Science Journal.