0
$\begingroup$

I've been trying to design such an algo with TLA+ formal prover, that is till I realized that it's a case of "simple-looking problem but with soooo many corner-cases", which screams of "it is probably a known CS problem with papers and algorithms on it". I found it is a case of "leader-election problem", however I can't seem to find anything on the "shared disks" case specifically.

So, given 2 nodes (i.e. computers) that physically share disks. The disks are the only reliable communication channel. Normally the nodes communicate via interconnect LAN, but if it's down the "leadership" (i.e. "who owns the resources") has to be decided via disks.

Now, every "leader election" algo that I see applies to a network, whereas communication via disks has its own peculiarities, specifically:

  1. Stale data: disks can always be written/read to, but the only way to ensure the other node is alive is with timestamps. This is the key point: the other node may die and leave anything on the disk.
  2. No locking: I see some algorithms imply that when multiple nodes try to do same operation, only one will succeed. Well, that's definitely not applicable here: all writes to disks will succeed (well, unless disk is failing but that's irrelevant)
  3. Many channels: dozens of disks are shared and you have to take into account that any disk may get physically removed.

Any known algorithm that allows to chose "leader" and avoid "splitbrain" in these conditions?

$\endgroup$
5
  • $\begingroup$ Not sure why you think shared disks would pose fundamentally different problems from shared coax cable (Ethernet)? $\endgroup$
    – Steve
    Commented Jun 15 at 8:52
  • $\begingroup$ @Steve the point 1. Stale data isn't applicable to network because there either is a TCP channel or there isn't. Data is always the newest. 2. No locking isn't applicable because in network you can come up with some hacks like trying to establish multiple connections to a point and only the first connection wins (offhand Idk how useful that is but it is a thing). 3. Many channels isn't applicable because typically each node is connected by exactly one channel. While you can have multiple nodes, but you don't usually have single node connected with 2 or more channels. $\endgroup$
    – Hi-Angel
    Commented Jun 15 at 9:25
  • $\begingroup$ (1) but you never know whether the TCP channel is up or not. Your information is only as good as the last message (or heartbeat). Same as disk. (2) there is nothing to stop you implementing locking algorithms with disks. (3) any shared medium designed for disconnection, will require a protocol for disconnection. Both disks and Ethernet are hot-pluggable. $\endgroup$
    – Steve
    Commented Jun 15 at 10:18
  • $\begingroup$ For (1): you're probably right. But the thing is: when a message comes through the channel, you know it isn't some stale data. For disks it probably can be worked around by tracking previous message timestamp (I can try, tho I'm not sure there isn't any corner cases as it's typical for such CS problems). (2) you probably can come up with something based off of timestamps, but there will be many corner cases, which is not a thing for network connections. (3) this reply I didn't understand. Network disconnection is the end whereas with disks you switch to another one (\w stale data). $\endgroup$
    – Hi-Angel
    Commented Jun 15 at 10:38
  • $\begingroup$ (1 & 2) implicitly, the TCP protocol does track the previous message, by maintaining a sequence number. If a disk was being used as a shared medium for real-time data exchange, a similar protocol would be used. (3) I'm not quite understanding how you intend to use the disks, but network connections and sessions can be re-established just like disks can be. I think you are proceeding from a faulty understanding that network protocols are incompatible with disk storage. That's not the case. $\endgroup$
    – Steve
    Commented Jun 15 at 12:31

1 Answer 1

0
$\begingroup$

After having analyzed network algorithms, I devised an answer to this problem.

First, the easier question: "what algorithms could possibly fit 2-nodes case?". Wikipedia classifies them based on the network topology: Ring, Mesh, Hypercube and "universal". On the first sight "2 nodes case" do not fit the first 3. But considering 1) any topology may degrade to 2 nodes and 2) to satisfy algorithms we can in theory create a "phantom" node which is actually just a duplicate of another one; I think it's fair to assume every algo is suitable for "2 nodes case".

With that out of the way, applying any algorithm to "shared disks" would turn up the following problem: node α may think node β is up, while β would think α is down. It is unavoidable.¹

To formalize the problem: "shared disks" as a communication medium presents a case where network topology view on both nodes may be different. So both nodes may run "leader election" with different input parameters, and may therefore both conclude that they are the leader, resulting in "splitbrain".

In the "network case" this is similar to a node (dis)appearing. How is it solved there? The solution for that happening while there's leader is trivial. The solution in case "leader election" is running is to just disallow the node from entering the topology till "election" is finished.

This solution could be extrapolated to the "disks case". This requires explicit on-disk state for the case where "leader election" is running. So what node α does while starting up, is it checks the timestamp and state of β. If β's state is "running leader election", this may or may not mean it knows α is up. So α waits a short timeout during which happens one of the following: 1) β concludes itself a leader, or 2) nothing happens besides updating the timestamp, which implies β knows α is running and waits for α's action.

The gist of this solution is to only run "leader election" for the known topology and to make precautions so a node starting up does not interfere into "election".


1: To see why you need to consider that whether a node is up may only be determined by something it wrote on disk. The obvious solution is writing a timestamp. Now, consider case where α is running but β just starting up. α reads β's timestamp and sees it's expired. Right afterwards β updates the timestamp and reads α's timestamp (which is up to date). As result α thinks β is down, while β sees α is up.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.