Development of a partially synchronous consensus algorithm for sharded distributed systems in machine-to-machine infrastructure

This article focuses on the development of a consensus algorithm for a sharded distributed system to be used in machine-to-machine infrastructure. The authors analyze the existing advantages and disadvantages of distributed systems and sharding, as well as describe the properties that a consensus algorithm should possess, and consider various analogues. Different communication models in distributed systems are also considered: synchronous, asynchronous, and partially synchronous. The article proposes a consensus algorithm that assumes a partially synchronous message delivery environment and direct message exchange between nodes. The presented algorithm ensures convergence, integrity and consistency of data, as well as fault tolerance and high scalability. The algorithm describes the use of a standard format of unique identifiers to describe nodes, hash functions to describe the state of the consensus round, and message exchange between shards for node coordination. It also uses a pseudorandom permutation function to order operations within a single round, which allows saving on network delays and reducing the time for overall consensus on operations. In conclusion, the results of system performance measurements are shown, and general findings about the operability of the presented algorithm are given.