Why have we not been able to develop a unified complexity theory of distributed computing?

Question

The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed computation that are simply not compatible with each other. The sheer explosion of varying temporal properties (asynchrony, synchrony, partial synchrony), various communication primitives (message passing vs. shared memory, broadcast vs. unicast), multiple fault models (fail stop, crash recover, send omission, byzantine, and so on) has left us with an intractable number of system models, frameworks, and methodologies, that comparing relative solvability results and lower bounds across these models and frameworks has become arduous, intractable, and at times, impossible.

My question is very simply, why is that so? What is so fundamentally different about distributed computing (from its sequential counterpart) that we haven't been able to collate the research into a unified theory of distributed computing? With sequential computing, Turing Machines, Recursive Functions, and Lambda Calculus all truned out to be equivalent. Was this just a stroke of luck, or did we really do a good job in encapsulating sequential computing in a manner that is yet to be accomplished with distributed computing?

In other words, is distributed computing inherently unyielding to an elegant theory (and if so, how and why?), or are we simply not smart enough to discover such a theory?

The only reference I could find that addresses this issue is: "Appraising two decades of distributed computing theory research" by Fischer and Merritt DOI: 10.1007/s00446-003-0096-6

Any references or expositions would be really helpful.

Answer 1

My take is that the abstractly-motivated Turing machine model of computation was a good approximation of technology until very recently, whereas models of distributed computing, from the get-go, have been motivated by the real world, which is always messier than abstractions.

From, say, 1940-1995, the size of problem instances, the relative "unimportance" of parallelism and concurrency, and the macro-scale of computing devices, all "conspired" to keep Turing machines an excellent approximation of real-world computers. However, once you start dealing with massive datasets, ubiquitous need for concurrency, biology through the algorithmic lens, etc., it is much less clear if there is an "intuitive" model of computation. Perhaps problems hard in one model are not hard -- strictly less computationally complex -- in another. So I believe that mainstream computational complexity is finally catching up (!) with distributed computing, by starting to consider multiple models of computation and data structures, motivated by real-world considerations.

Answer 2

I will answer this from the perspective of classical graph problems (or input/output problems): we have a network, each node gets something as input and each node must produce something as output. I guess this is closest to the world of traditional computational complexity.

I am certainly biased, but I think that in this setting, there is a simple and fairly commonly used model of distributed computing: synchronous distributed algorithms, with the definition that running time = number of synchronous rounds. In Peleg's terminology, this is the LOCAL model.

This model is nice as it has very few "moving parts", no parameters, etc. Nevertheless, it is very concrete: it makes sense to say that the running time of an algorithm is exactly 15 in this model. And you can prove unconditional, information-theoretic lower bounds: from this perspective, the distributed complexity of many graph problems (e.g., graph colouring) is fairly well-understood.

This model also provides a unified approach to many aspects of distributed computing:

• Message-passing vs. shared memory, broadcast vs. unicast: Irrelevant in this model.
• Your real-world system is asynchronous? No problem, just plug in the $\alpha$-synchroniser. The time complexity (with suitable definitions) is essentially unaffected.
• You'd like to have an algorithm for dynamic networks, or you'd like to recover from failures? Well, if your synchronous algorithm is deterministic, then you can use it to construct a self-stabilising algorithm. Again, the time complexity is essentially unaffected.

---

Now all this is fine as long as you study problems that are "truly distributed" in the sense that the running time of your algorithm is smaller than the diameter of the graph, i.e., no node needs to have full information on the structure of the graph. However, there are also many problems that are inherently global: the fastest algorithm in this model has running time that is linear in the diameter of the graph. In the study of those problems, the above model no longer makes any sense, and then we need to resort to something else. Typically, one starts to pay attention to the total number of messages or bits communicated in the network. That's one reason why we get several different models.

---

Then of course we have the issue that the distributed computing community is actually two different communities, with surprisingly few things in common. If you lump together all models from two communities, it will certainly look a bit confusing... My answer above is related to only one half of the community; I trust others will fill in regarding the other half.

Answer 3

One romantic idea to capture various models of distributed computing has been through algebraic topology. The core idea is to construct simplicial complexes by letting points be process states, each labeled with a process id. This is a primer on the topic. The closest answer to your question has probably been touched upon by Eli gafni in his paper- Distributed computing- A glimmer of a theory. In his paper, he shows simulations how beginning with async shared memory for two-three processors(for fail stop and Byzantine)-he shows how can apply this to the message passing model. Crucial to understanding his simulations is the notion of viewing a distributed computing topologically

Answer 4

I think the situation looks quite different if viewed in context: starting from the early works and impossibility results on Byzantine agreement (PSL80 LSP82 FLP85), it was clear soon that fundamental problems in distributed computing can only be solved at all with strict synchrony assumptions and a high degree of redundancy. As these unconditional theoretical resource lower bounds were considered infeasible for any practical purposes, research focused on developing more refined models that allowed evermore fine-grained trade-offs of assumptions (on timing guarantees or failure modes for example) vs. guarantees (i.e. number of simultaneous faults of what kinds on what type of components tolerated, e.g. processors, links) in order to give the system designers the tools to find the right trade-off for the system at hand.