Any consensus replication agorithm that works with high latency

Operating Systems & Open Source
,
1

I am working on a project to make a distributed network controller for OpenWRT.~~ I already have a design that has a master that serves as a the point communication~~ and truth but I am curious about algorithms that would work with a network that is spread out. It would need to not be to chatty and be aware of topology. Here is what I am thinking:

  • Each node should know which other nodes are closest. Data should flow from the closest nodes to the rest of the network. Each device will report its status to the closest nodes. It will relay data it receives to its neighbors.

  • Each node should be able to reach any other node

  • There could be a process of adapting by using random numbers. What I mean is that a node could periodically pick several random nodes out of a list of devices and then test latency, If the latency is smaller than the current list of close peers it will swap them.

  • The network should have a way to be quickly recovered by a admin

That’s all the thoughts I had. What I am looking for is existing research or projects that have algorithms I could use. I know things like Raft exist but Raft still has a master and is not suited for devices far apart. I know software like IPFS and I2P exist and that they are capable of organizing lots of devices on the internet in a decentralized way.

Anyone know of a consensus algorithm that will work in bad conditions and that can stay mostly reliable even if large portions of the network are down?

Update:

I don’t think I actually need consensus here. All I need is a way to calculate the number of hosts that need to receive and broadcast a change for the change to make it to 100% of the network. I now have a math problem.

Update 2: I am working on building a gossip protocol

1 Like
2

https://www.bittorrent.org/beps/bep_0003.html

3

Instead of attempting to figure out a communication protocol, and multi master file replication technique, how about instead search for the end result. From what I understand you eventually want the same data on all of the nodes. You need:

a cluster file system

If any node gets an update, it will replicate those changes to the other nodes as they become available.

4

Clustered filesystems are unsuitable as I want each node to work by itself in the case of a major failure. Also I would need something that is designed to work on a large number of nodes that are spread out and underpowered. (ie not high performance computing)

5

by work, do you mean in read write where the changes will get merged with a data set, or in read only mode?

MongoDB has some of those modes, but requires quorum of 51% or more of members in order to perform writes.

There are also log based file systems with data sets that can be merged when reconnected. ie zfs. With data sets on zfs each data set, not just the the pool has it’s own independent log that can be unique to that data set. You can also have a base snapshot then clone that to another dataset or pool without duplicating source pool or dataset. One way this is useful is to have a disk image of a VM with an OS etc installed. Clone the dataset, boot the machine and run it. Later update the OS etc, kill the first VM, clone off of the new dataset snapshot, boot the vm and run it.

zfs with clone each remote device gets it’s own independent file system that can be synced with rsync, without taking a penalty in resource usage by the master copy. The dataset that is cloned can be a block device that contains an ext3, ext4 or exfat file system, it doesn’t have to be zfs.