Search

This article proposes a decentralized collaboration scheme for the motion planning of multiagent systems under coupled linear temporal logic task specifications. In order to alleviate the massive computational complexity in centralized methods, coupled edges are introduced to decouple the product automata, and then the path of each agent is synthesized according to local messages. Furthermore, in order to achieve the real-time message exchange, the tableau and gossip protocol are employed during online communication, resulting in a distributed collaboration scheme. Finally, based on the resultant decoupled product automata, a united agent model is designed to deal with partial node failures, yielding a more robust collaboration scheme. Simulations are conducted to demonstrate the effectiveness and superiority of the proposed methods.

In this work we present a new framework for the analysis and design of randomized gossip algorithms for solving the average consensus problem. We show how classical randomized iterative methods for solving linear systems can be interpreted as gossip algorithms when applied to special systems encoding the underlying network and explain in detail their decentralized nature. Our general framework recovers a comprehensive array of well-known gossip algorithms as special cases, including the pairwise randomized gossip algorithm and path averaging gossip, and allows for the development of provably faster variants. The flexibility of the new approach enables the design of a number of new specific gossip methods. For instance, we propose and analyze novel block and the first provably accelerated randomized gossip protocols, and dual randomized gossip algorithms. From a numerical analysis viewpoint, our work is the first that explores in depth the decentralized nature of randomized iterative methods for linear systems and proposes them as methods for solving the average consensus problem. We evaluate the performance of the proposed gossip protocols by performing extensive experimental testing on typical wireless network topologies., Comment: 44 pages, 12 figures

Mobile Access to the Web of Data is currently a real challenge in developing countries, mainly characterized by limited Internet connectivity and high penetration of mobile devices with the limited resources (such as cache and memory). In this paper, we survey and compare proposed solutions (such as models and architectures) that could contribute to solving this problem of mobile access to the Web of Data with intermittent Internet access. These solutions are discussed in relation to the underlying network architectures and data models considered. We present a conceptual study of peer-to-peer solutions based on gossip protocols dedicated to design the connected overlay networks. In addition, we provide a detailed analysis of client-server and data replication systems generally designed to ensure the local availability of data on the system. We conclude with some recommendations to achieve a connected architecture that provides mobile contributors with local access to the Web of data.

Blockchain is a mainstream technology in which many untrustworthy nodes work together to maintain a distributed ledger with advantages such as decentralization, traceability, and tamper-proof. The network layer communication mechanism in its architecture is the core of the networking method, message propagation, and data verification among blockchain nodes, which is the basis to ensure blockchain’s performance and key features. When blocks are propagated in peer-to-peer (P2P) networks with gossip protocol, the high propagation delay of the protocol itself reduces the propagation speed of the blocks, which is prone to the chain forking phenomenon and causes double payment attacks. To accelerate the propagation speed and reduce the fork probability, this paper proposes a blockchain network propagation mechanism based on proactive network provider participation for P2P (P4P) architecture. This mechanism first obtains the information of network topology and link status in a region based on the internet service provider (ISP), then it calculates the shortest path and link overhead of peer nodes using P4P technology, prioritizes the nodes with good local bandwidth conditions for transmission, realizes the optimization of node connections, improves the quality of service (QoS) and quality of experience (QoE) of blockchain networks, and enables blockchain nodes to exchange blocks and transactions through the secure propagation path. Simulation experiments show that the proposed propagation mechanism outperforms the original propagation mechanism of the blockchain network in terms of system overhead, rate of data success transmission, routing hops, and propagation delay.

We present \textsc{P2PTFHH} (Peer--to--Peer Time--Faded Heavy Hitters) which, to the best of our knowledge, is the first distributed algorithm for mining time--faded heavy hitters on unstructured P2P networks. \textsc{P2PTFHH} is based on the \textsc{FDCMSS} (Forward Decay Count--Min Space-Saving) sequential algorithm, and efficiently exploits an averaging gossip protocol, by merging in each interaction the involved peers' underlying data structures. We formally prove the convergence and correctness properties of our distributed algorithm and show that it is fast and simple to implement. Extensive experimental results confirm that \textsc{P2PTFHH} retains the extreme accuracy and error bound provided by \textsc{FDCMSS} whilst showing excellent scalability. Our contributions are three-fold: (i) we prove that the averaging gossip protocol can be used jointly with our augmented sketch data structure for mining time--faded heavy hitters; (ii) we prove the error bounds on frequency estimation; (iii) we experimentally prove that \textsc{P2PTFHH} is extremely accurate and fast, allowing near real time processing of large datasets., arXiv admin note: text overlap with arXiv:1806.06580

Designing distributed, fast and reliable wireless consensus protocols is instrumental in enabling mission-critical decentralized systems, such as robotic networks in the industrial Internet of Things (IIoT), drone swarms in rescue missions, and so forth. However, chasing both low-latency and reliability of consensus protocols is a challenging task. The problem is aggravated under wireless connectivity that may be slower and less reliable, compared to wired connections. To tackle this issue, we investigate fundamental relationships between consensus latency and reliability through the lens of wireless connectivity, and co-design communication and consensus protocols for low-latency and reliable decentralized systems. Specifically, we propose a novel communication-efficient distributed consensus protocol, termed Random Representative Consensus (R2C), and show its effectiveness under gossip and broadcast communication protocols. To this end, we derive a closed-form end-to-end (E2E) latency expression of the R2C that guarantees a target reliability, and compare it with a baseline consensus protocol, referred to as Referendum Consensus (RC). The result shows that the R2C is faster compared to the RC and more reliable compared when co-designed with the broadcast protocol compared to that with the gossip protocol., 30 pages, 8 figures, to appear in IEEE Internet of Things Journal

Distributed Denial-of-Service (DDoS) attacks are one of the major causes of concerns for communication service providers. When an attack is highly sophisticated and no countermeasures are available directly, sharing hardware and defense capabilities become a compelling alternative. Future network and service management can base its operations on equally distributed systems to neutralize highly distributed DDoS attacks. A cooperative defense allows for the combination of detection and mitigation capabilities, the reduction of overhead at a single point, and the blockage of malicious traffic near its source. Main challenges impairing the widespread deployment of existing cooperative defense are: (a) high complexity of operation and coordination, (b) need for trusted and secure communications, (c) lack of incentives for service providers to cooperate, and (d) determination on how operations of these systems are affected by different legislation, regions, and countries. The cooperative Blockchain Signaling System (BloSS) defines an effective and alternative solution for security management, especially cooperative defenses, by exploiting Blockchains (BC) and Software-Defined Networks (SDN) for sharing attack information, an exchange of incentives, and tracking of reputation in a fully distributed and automated fashion. Therefore, BloSS was prototyped and evaluated through a global experiment, without the burden to maintain, design, and develop special registries and gossip protocols.

Learnae is a system aiming to achieve a fully distributed way of neural network training. It follows a “Vires in Numeris” approach, combining the resources of commodity personal computers. It has a full peer-to-peer model of operation; all participating nodes share the exact same privileges and obligations. Another significant feature of Learnae is its high degree of fault tolerance. All training data and metadata are propagated through the network using resilient gossip protocols. This robust approach is essential in environments with unreliable connections and frequently changing set of nodes. It is based on a versatile working scheme and supports different roles, depending on processing power and training data availability of each peer. In this way, it allows an expanded application scope, ranging from powerful workstations to online sensors. To maintain a decentralized architecture, all underlying tech should be fully distributed too. Learnae’s coordinating algorithm is platform agnostic, but for the purpose of this research two novel projects have been used: (1) IPFS, a decentralized filesystem, as a means to distribute data in a permissionless environment and (2) IOTA, a decentralized network targeting the world of low energy “Internet of Things” devices. In our previous work, a first approach was attempted on the feasibility of using distributed ledger technology to collaboratively train a neural network. Now, our research is extended by applying Learnae to a fully deployed computer network and drawing the first experimental results. This article focuses on use cases that require data privacy; thus, there is only exchanging of model weights and not training data.

Part 6: Large-Scale Decentralised Systems; International audience; Gossip protocols form the basis of many smart collective adaptive systems. They are a class of fully decentralised, simple but robust protocols for the distribution of information throughout large scale networks with hundreds or thousands of nodes. Mean field analysis methods have made it possible to approximate and analyse performance aspects of such large scale protocols in an efficient way that is independent of the number of nodes in the network. Taking the gossip shuffle protocol as a benchmark, we evaluate a recently developed refined mean field approach. We illustrate the gain in accuracy this can provide for the analysis of medium size models analysing two key performance measures: replication and coverage. We also show that refined mean field analysis requires special attention to correctly capture the coordination aspects of the gossip shuffle protocol.

[Resumen]: En la última década, la evolución del Machine Learning ha sido muy próspera, necesitando los modelos más fructíferos ser nutridos por grandes volúmenes de datos. A menudo, la obtención y gestión de estos datos es complicada, siendo generalmente escasos y sujetos a medidas de privacidad. El Federated Learning implica un cambio de paradigma en el entrenamiento de modelos de Machine Learning. Este nuevo enfoque permite realizar el proceso de aprendizaje sobre datos distribuidos entre una gran cantidad de clientes. A pesar de que esta novedosa técnica trae consigo numerosas ventajas, una de sus grandes limitaciones es la necesidad de un servidor que orqueste todo el proceso de aprendizaje, suponiendo un único punto de falla. Así mismo, se necesitará disponer de una gran infraestructura para hacer escalables estos sistemas. Para tratar de solventar estas desventajas, surgirán nuevas aproximaciones denominadas Decentralized Federated Learning, siendo una de las soluciones más prometedoras el uso de redes peer-to-peer. Ante la inexistencia de alguna librería de soporte al Decentralized Federated Learning, en este proyecto, se propone el desarrollo de una librería de propósito general que permita el Federated Learning sobre redes peer-to-peer, empleando el protocolo Gossip. El uso del protocolo Gossip garantizará la tolerancia a fallos en la red peer-to-peer, creando un ecosistema descentralizado, escalable y robusto. La librería busca dar soporte a toda clase de dispositivos, haciendo especial hincapié en su facilidad de uso y ampliación futura. Además de permitir el despliegue, ésta, posibilita la ejecución de simulaciones, haciendo posible la realización de pruebas en entornos controlados. Para el desarrollo, se ha hecho uso de la metodología ágil SCRUM. Las iteraciones centrales se han destinado a la implementación del sistema, mientras que la inicial y final se han dedicado a la preparación del proyecto y realización de pruebas respectivamente. En las diversas pruebas realizadas, se han empleado los datasets de MNIST y FEMNIST, obteniendo resultados realmente similares a ejecuciones equivalentes con entrenamientos clásicos. [Abstract]: In the last decade, the evolution of Machine Learning has been really thriving. The most productive models need to be fed by a large volume of data. Obtaining and managing these data is often complicated, as they are generally scarce and subject to privacy measures. Federated Learning implies a paradigm shift in the training of Machine Learning models. This new approach allows us to carry out the learning process on data which are distributed among a large number of clients. In spite of the fact that this new technique has numerous advantages, one of its great limitations is the need for a server that orchestrates the entire learning process, assuming a single point of failure. Moreover, a large infrastructure will be necessary to make these systems scalable .In order to solve these disadvantages, new approaches called Decentralized Federated Learning will emerge, and one of the most promising solutions will be the use of peer-to-peer networks. Given the lack of any library to support Decentralized Federated Learning, this project proposes the development of a general purpose library that allows Federated Learning over peer-to-peer networks, using the Gossip protocol. The use of the Gossip protocol will guarantee fault tolerance in the network, creating a decentralized, scalable and robust ecosystem. The library will seek to support all kinds of devices, with special emphasis on ease of use and future expansion. In addition to allowing deployment, it will enable the execution of simulations, making it possible to perform tests in controlled environments. The agile SCRUM methodology has been used for this development. The central iterations have been used to the implementation of the system, while the initial and final iterations have been respectively dedicated to project preparation and testing. The MNIST and FEMNIST datasets have been used in the different tests carried out, obtaining results that are really similar to equivalent executions with classic training. Traballo fin de grao (UDC.FIC). Enxeñaría Informática. Curso 2021/2022

Gossip-based consensus protocols have been recently proposed to confront the challenges faced by state machine replication in large geographically distributed systems. It is unclear, however, to which extent consensus and gossip communication fit together. On the one hand, gossip communication has been shown to scale to large settings and efficiently handle participant failures and message losses. On the other hand, gossip may slow down consensus. Moreover, gossip's inherent redundancy may be unnecessary since consensus naturally accounts for participant failures and message losses. This paper investigates the suitability of gossip as a communication building block for consensus. We answer three questions: How much overhead does classic gossip introduce in consensus? Can we design consensus-friendly gossip protocols? Would more efficient gossip protocols still maintain the same reliability properties of classic gossip?

A source node forwards fresh status updates as a point process to a network of observer nodes. Within the network of observers, these updates are forwarded as point processes from node to node. Each node wishes its knowledge of the source to be as timely as possible. In this network, timeliness at each node is measured by an age of information metric: how old is the timestamp of the freshest received update. This work extends a method for evaluating the average age at each node in the network when nodes forward updates using a memoryless gossip protocol. This method is then demonstrated by age analysis for a simple network.

Flying Ad Hoc networks, (FANETs) in recent years, have actively been used in monitoring landscape, military and mapping terrains. However, with the advent of the emerging concept of smart cities and new business applications, these flying devices and drones have found a new use case in the medical and governance sector. But these networks suffer from the major problem of centralization. Although centralization does provide reliability and efficiency but also poses the threat of a single point of failure. Meanwhile, blockchain widely known for its decentralization is heavily researched and can be utilized in this case to offer a solution to the problem of centralization of FANETs. Therefore, in this paper, we propose a decentralized architecture of flying ad hoc nodes based on blockchain and using Practical byzantine fault tolerance (PBFT) for consensus among nodes. By employing PBFT, the architecture is not only computationally efficient and fast. In addition, we have used a gossip protocol for passing messages among nodes. Lastly, we have simulated the working of our model and the experimental results show that the proposed method works with nearly constant throughput and latency while increasing the network size and approximately constant message overhead with increase transaction for given network size.

During the most up-to-date decade, we've seen an upheaval in network among PCs, and a future change in perspective from concentrated to exceptionally disseminated frameworks. Tattle and tree-based conglomeration calculations are two famous answers for circulated averaging in remote systems. The final uses just neighborhood message trades and requires no steering structures while the final requires accumulating a spreading over tree. We give conditions under which this course of action of action is ensured to mix to an agreement arrangement, where all hubs have an identical restricting qualities, on any firmly associated coordinated diagram. Tattle conventions will in most cases be utilized in settings where in actuality the scale and the dynamism of the fundamental correspondence organize make the choice of customary correspondence conventions very strange. In this educational article, we initially present a gathering of tattle conventions for data dissemination, and we offer an expository model to examine their execution in relation to speed and nature of the dispersion. We at that time present three samples of tattle based conventions that tackle likely the absolute most different issues, in particular participation the board, accumulation and overlay topology development.

The increasing penetration of renewable energy sources is impacting the operation of the distribution grid. Whilst they are currently placing a burden on the distribution grid, it is generally agreed that these sources could also be used for active grid control, thereby contributing to a stable and secure grid. Smart photovoltaic inverters can contribute to active grid control, by expanding their features with added functions. In this paper, we develop a novel grid voltage support algorithm for smart photovoltaic inverters, based on distributed optimization and peer-to-peer communication. The Jacobi-Proximal Alternating Direction Method of Multipliers is applied in this paper to locally optimize reactive power compensation and active power curtailment of each inverter participating in the voltage control. We propose the use of a push-sum gossip protocol to enable peer-to-peer data interchange between inverters. We also use strategies to improve the robustness of the proposed algorithm: an acceleration strategy, a feedback strategy and an anti-windup strategy. A case study is presented, demonstrating the fast convergence of the algorithm and its ability to solve the voltage problems.

Next-generation Internet architectures are being designed and deployed to overcome limitations of today's Internet. One such architecture with an increasing production deployment is SCION [23], which also includes a transition mechanism to support an incremental deployment and coexistence with the legacy IP-based Internet: the SCION-IP gateway. This mechanism---and similar mechanisms in other next-generation architectures---requires a distributed system to translate between old (IP) and new (SCION) addresses at an Internet scale and must connect the different public-key infrastructures to enable secure operation. In this paper, we describe such a system for the SCION architecture. A gossip protocol distributes mappings between legacy IP and SCION addresses throughout the SCION network, and SCION's control-plane PKI and the Resource Public Key Infrastructure (RPKI) protect the authenticity of the individual mappings. We provide a prototype implementation and demonstrate that it scales to today's Internet with approximately one million IP prefixes.

A source node updates its status as a point process and also forwards its updates to a network of observer nodes. Within the network of observers, these updates are forwarded as point processes from node to node. Each node wishes its knowledge of the source to be as timely as possible. In this network, timeliness is measured by a discrete form of age of information: each status change at the source is referred to as a version and the age at a node is how many versions out of date is its most recent update from the source. This work introduces a method for evaluating the average version age at each node in the network when nodes forward updates using a memoryless gossip protocol. This method is then demonstrated by version age analysis for a collection of simple networks. For gossip on a complete graph with symmetric updating rates, it is shown that each node has average age that grows as the logarithm of the network size., Submitted to ISIT 2021

Distributed clustering algorithms have proven to be effective in dramatically reducing execution time. However, distributed environments are characterized by a high rate of failure. Nodes can easily become unreachable. Furthermore, it is not guaranteed that messages are delivered to their destination. As a result, fault tolerance mechanisms are of paramount importance to achieve resiliency and guarantee continuous progress. In this paper, a fault-tolerant distributed k-means algorithm is proposed on a grid of commodity machines. Machines in such an environment are connected in a peer-to-peer fashion and managed by a gossip protocol with the actor model used as the concurrency model. The fact that no synchronization is needed makes it a good fit for parallel processing. Using the passive replication technique for the leader node and the active replication technique for the workers, the system exhibited robustness against failures. The results showed that the distributed k-means algorithm with no fault-tolerant mechanisms achieved up to a 34% improvement over the Hadoop-based k-means algorithm, while the robust one achieved up to a 12% improvement. The experiments also showed that the overhead, using such techniques, was negligible. Moreover, the results indicated that losing up to 10% of the messages had no real impact on the overall performance.

Recently, with the vigorous development of Decentralized Finance (DeFi) on Ethereum blockchain, the economic value and user scale of Ethereum keep growing. However, the low transaction processing capability of Ethereum prevents its further development. One factor that limits the transaction processing capability is the bandwidth required to synchronize the blocks over the nodes in the Ethereum network. This work proposes a new block synchronization protocol, referred to as LightBlock, which is dedicated to reducing the bandwidth used by the Ethereum network to disseminate messages. The LightBlock protocol is of great significance to the improvement of TPS. Since Ethereum's block synchronization protocol is a kind of gossip protocol, the redundant message propagation is its inherent shortcoming. In the LightBlock protocol, we use transaction Hash to replace the transaction of the original block to form a LightBlock structure. The propagation of LightBlock structure requires a much smaller bandwidth resource than the propagation of the original block has. Moreover, in order to reduce the communication overhead of the new protocol, each node needs to predict the missing transactions of its neighbor nodes before propagating the LightBlock strcuture. Therefore, we set up three models to measure the similarity of the current Ethereum node transaction pool and other parameters. Through analysis, the size of LightBlock is reduced by an average of 83.55% compared to the size of the current block; after adding the function of predicting missing transactions, the probability of not increasing the number of additional communications increases from 0.2 to 0.398.

Blockchain protocols’ primary security goal is consensus: one version of the global ledger that everyone in the network agrees on. Their proofs of security depend on assumptions on how well their peer-to-peer (P2P) overlay networks operate. Yet, surprisingly, little is understood about what factors influence the P2P network properties. In this work, we extensively study the Ethereum P2P network’s connectivity and its block propagation mechanism. We gather data on the Ethereum network by running the official Ethereum client, geth, modified to run as a “super peer” with many neighbors. We run this client in North America for over seven months, as well as shorter runs with multiple vantages around the world. Our results expose an incredible amount of churn, and a surprisingly small number of peers who are actually useful (that is, who propagate new blocks). We also find that a node’s location has a significant impact on when it hears about blocks, and that the precise behavior of this has changed over time (e.g., nodes in the US have become less likely to hear about new blocks first). Finally, we find prune blocks propagate faster than uncles.