Computer scientists have developed an algorithm that improves the speed at which nodes within a multi-agent system converge on consensus without compromising energy consumption, a development with applications from supply-chain management to bitcoin.

Researchers have devised a better network ‘topology’, or how a network is put together, within distributed multi-agent systems to improve the speed at which their nodes converge on agreement regarding a single data value needed during computation.The technique is devised by researchers with the Sharif University of Technology in Tehran.

Paper Information

Mohammad Saeed Sarafraz and Mohammad Saleh Tavazoei, "A Unified Optimization-Based Framework to Adjust Consensus Convergence Rate and Optimize the Network Topology in Uncertain Multi-Agent Systems," IEEE/CAA J. Autom. Sinica, vol. 8, no. 9, pp. 1539-1548, Sept. 2021.

https://www.ieee-jas.net/en/article/doi/10.1109/JAS.2021.1004111

Within computer science, research into multi-agent systems has enjoyed a great deal of attention in recent years, with uses as varied as wireless communications, supply-chain management, bitcoin and even use of swarms of drones by the military. A multi-agent system is defined as a decentralized network of software agents that work together to solve problems. For a range of problems, it can be difficult or even impossible for a single actor or centralized system to solve, but a decentralized system of multiple nodes or agents can. 

One of the major challenges facing the field involves developing strategies for such a distributed network to coordinate agreement amongst the nodes on a single data value that is needed during computation. Such agreement is described as “consensus”. Consensus in the realm of computer science is different from consensus in the human world: it involves converging on a single value by the nodes in the network, much like a group of friends agreeing on which restaurant to go to.

A key difficulty is developing consensus strategies that can still ensure overall reliability in distributed multi-agent systems in the face of faults or failures in one or more of the nodes of the network. The consensus must be fault-tolerant. 

However, unlike the friends choosing which restaurant to eat at, the distributed consensus problem amongst nodes is not easy. In a consensus-seeking process, the agents in a given network try to agree on some quantity by communicating what they know to their neighboring agents. But how do they identify a faulty node? Is another node identifying the faulty node actually the one that is faulty? Making matters worse, the greater the number of nodes, the greater the complexity of achieving consensus. 

To deal with the distributed consensus problem, various algorithmic solutions have been developed such as taking a 2/3rd majority of the nodes as to what they believe to be the correct data value.

These various consensus algorithms may still face challenges with respect to their performance. One might be more robust than another in the case of node failure. Another might be weaker at that but respond better to external malicious attacks. The researchers at Sharif University of Technology were focused on improving the speed at which multi-agent system nodes converge on consensus.

In general, the stronger the connections between the nodes in a network, the more enhanced the convergence rate. However, promoting such communication between these agents imposes additional costs such as energy consumption. In some real-world multi-agent systems, the batteries powering the agents have very low capacity and cannot conveniently be recharged or replaced. As a result, reducing energy consumption to extend the agents’ battery lifetime has emerged as a critical issue in these networks.

“But instead of focusing on the battery for a given network, we thought we could design a better network ‘topology’, or how the network is put together, for a given battery,” says Mohammad Saleh Tavazoei, an electrical engineer and corresponding author for the paper. He is currently a Full Professor with the Department of Electrical Engineering at Sharif University of Technology.

The main advantage of their framework for an optimized network topology is that reduces the communications needed between the agents in the system while allowing a rate for convergence upon consensus that can be adjusted up and down, depending on requirements.

In the future, the researchers hope to extend their work to balancing convergence rate and communication requirements to multi-agent systems that have heterogeneous agents in their architecture.