Distributed Operating Systems

# The distributed OS promise, and the one part of it that cannot be kept.

def resolve(name, directory):
    # LOCATION TRANSPARENCY: the name carries no host. The lookup does.
    return directory[name]

def migrate(proc, target):
    # MIGRATION TRANSPARENCY: freeze, ship the state, rebind the handles.
    proc["node"] = target
    return proc

def remote_read(node, reachable, node_known_dead):
    # FAILURE TRANSPARENCY: this is the one that does not work.
    if reachable:
        return "completed"
    if node_known_dead:
        return "failed"
    # A timeout cannot distinguish these three cases:
    #   1. the node crashed before doing the work
    #   2. it did the work and the REPLY was lost
    #   3. it is merely slow and will answer later
    return "unknown"

DIRECTORY = {"/data/readings": "B"}
proc = {"pid": 41, "node": "A"}

print("resolved:", resolve("/data/readings", DIRECTORY), "(no host in the name)")
print("migrated to:", migrate(proc, "B")["node"], "(same pid", str(proc["pid"]) + ")")
for reachable, dead, label in [(True, False, "healthy"), (False, True, "confirmed dead"),
                               (False, False, "silent")]:
    print("%-15s -> %s" % (label, remote_read("B", reachable, dead)))
print("a local call has two outcomes; a remote call has three")

// The distinction the abstraction cannot hide.
#include <iostream>
#include <chrono>
#include <optional>
struct Handle {
    int node;
};
// A LOCAL call: cannot fail halfway. It returns, or the whole process dies.
int local_read(Handle h, char* buf, std::size_t n);
// A REMOTE call: three outcomes, and a timeout tells you only that you
// are in one of the last two -- never which.
enum class Outcome {
    Completed, Failed, Unknown
};
std::optional<int> rpc_wait(int node, std::chrono::milliseconds);
bool node_confirmed_dead(int node);
Outcome remote_read(Handle h, char*, std::size_t,
std::chrono::milliseconds timeout) {
    if (rpc_wait(h.node, timeout)) return Outcome::Completed;
    if (node_confirmed_dead(h.node)) return Outcome::Failed;
    return Outcome::Unknown; // slow? crashed? reply lost? unknowable.
}
// Waldo et al., "A Note on Distributed Computing" (1994): making a remote
// call look identical to a local one is a leaky abstraction, because the
// failure modes are not the same set. Unknown has no local equivalent.
int main() {
    std::cout << "a local call has 2 outcomes; a remote call has 3\n"
    << "the third is why failure transparency cannot be delivered\n";
}

// Modern systems achieve the goal by making failure EXPLICIT, which is
// the opposite of what a classical distributed OS attempted.
interface ClusterStore {
    // Location transparency: kept. No host in the key.
    byte[] get(String key) throws Unavailable, Timeout;
    //                            ^^^^^^^^^^^^^^^^^^^^
    // Failure transparency: deliberately abandoned. The caller is
    // REQUIRED to handle partial failure -- it is in the signature.
}
class Caller {
    byte[] read(ClusterStore s, String k) {
        try {
            return s.get(k);
        }
        catch (Timeout t) {
            // The application decides: retry, fall back, degrade, fail.
            // A distributed OS tried to make this decision invisibly,
            // and there is no correct invisible answer.
            return fallback(k);
        }
    }
}