Change sample replica connector to tolerate connecting to faulty replicas

[sergefdrv]

Currently the sample gRPC replica connector has to establish connections to all the required replicas before it can be used by the core/client. Thus it cannot handle the case when a replica is already faulty before the connection is established. That also has an implication, that replicas have to start listening to incoming connections before trying to establish outgoing connection. Changing how the replica connector establishes outgoing connections could also help to overcome this limitation.

[sergefdrv]

@Naoya-Horiguchi Would you be interested in solving this issue at some point? Solving this would also be useful for view change: it would be easier to try and see view change in action.

[nhoriguchi]

@sergefdrv Yes, I am. I'll work on this after finishing the current issue.

[sergefdrv]

@Naoya-Horiguchi When you have questions or an idea how to solve this problem, please feel free to discuss it 🙂

[nhoriguchi]

@sergefdrv, the first thing I thought we need consider is how we determine whether a specific node is Byzantine faulty. Detecting crash faulty node is relatively trivial, but Byzantine fault detection isn't because such faulty nodes can do any types of unpredictable behavior (some "clever" faulty node usually behaves like correct node, and behaves traitorously only in some critial request). There seems to be studies on Byzantine Fault Detection (like [1] and [2], which are publicly available and cited very well), and I think we can learn some from them to discuss/decide the design.

• [1] The Case for Byzantine Fault Detection (https://www.usenix.org/legacy/event/hotdep06/tech/prelim_papers/haeberlen/haeberlen_html/index.html)
• [2] Byzantine fault detectors for solving consensus (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.10.328&rep=rep1&type=pdf)

In my (very) brief check, introducing "Detector module" interacting with state machines as stated in [1] seems clear to me, so I'm thinking of learning this approach more.

If you have some ideas/documents about detection related things, could you share them?

[sergefdrv]

@Naoya-Horiguchi Thanks for looking into this. Fault detection sounds an interesting direction to investigate. This might give a new perspective on the problem. On the other hand, MinBFT protocol is designed to tolerate up to a certain number, f, of faulty replicas, whether crashed or Byzantine. Fault detection might be considered an advanced feature in addition to what MinBFT protocol guarantees.

When I created this issue, I was only considering some connectivity issues. More precisely, the current sample implementation of ReplicaConnector interface requires connections to peer replicas to be established before it can handle invocations to its ReplicaMessageStreamHandler from the core. This means the replicas need to establish connections to all peers before the core can start:

minbft/sample/peer/cmd/run.go

Lines 147 to 154 in 0c4e78b

	dialOpts := []grpc.DialOption{grpc.WithInsecure(), grpc.WithBlock()}
	if err := replicaConnector.ConnectManyReplicas(peerAddrs, dialOpts...); err != nil {
	return fmt.Errorf("Failed to connect to peers: %s", err)
	}
	if err := replica.Start(); err != nil {
	return fmt.Errorf("Failed to start replica: %s", err)
	}

Similarly, the client, using the same interface, has to establish connections to all replicas before it can submit a request:

minbft/sample/peer/cmd/request.go

Lines 93 to 101 in 0c4e78b

	err = rc.ConnectManyReplicas(peerAddrs, grpc.WithInsecure(), grpc.WithBlock())
	if err != nil {
	return nil, fmt.Errorf("Failed to connect to peers: %s", err)
	}
	client, err := client.New(id, cfg.N(), cfg.F(), clientStack{auth, rc})
	if err != nil {
	return nil, fmt.Errorf("Failed to create client instance: %s", err)
	}

However, if some replicas are faulty and cannot or refuse to accept the connection then the replica or client will get stuck trying to connect to it. This is only sample code, but it is obviously not a good example of how to use the core. A user can try to kill some of the replicas or not even start those, trying to test if the system can tolerate this. Current implementation of the sample code will get stuck.

My suggestion would be to consider implementing the grpc.ReplicaConnector in such a way that it can establish connections on demand. If the connection is not yet established, ReplicaMessageStreamHandler would simply wait for it to be ready. This will probably even allow to eliminate minbft.Replica.Start.

What do you think?

[nhoriguchi]

@sergefdrv Sorry for my long silence, and I'm appreciated with your detailed explanation. I think I'm nearly ready to share code change (link). On-demand connection mechanism sounds interesting to me, but is not included in the current version yet.

I think that one thing to clarify is where/when to retry to connect. "On-demand" means "everytime before sending some messages/requests to all replicas", so we could have some connection checker and retrier in HandleMessageStream (which is an actual message sender). But actually I'm not sure about details in how (need more research).

[sergefdrv]

@Naoya-Horiguchi Thanks for working on this. I think your current series could be a good first step to improve the way we handle the connectivity problem. You probably want to avoid ConnectManyReplicas failing fast on the first error from ConnectReplica. https://godoc.org/golang.org/x/sync/errgroup might help achieving this 😉

[nhoriguchi]

... You probably want to avoid ConnectManyReplicas failing fast on the first error from ConnectReplica.

Applied this, thank you 👍

https://godoc.org/golang.org/x/sync/errgroup might help achieving this 😉

I didn't know about this library, so I learned it. Although it seems to me that errgroup doesn't fit to my current solution, it provides basic synchronization functions and will be helpful somewhere in this development, so thanks for noting.

[sergefdrv]

Solved in #65