Distributed computing models
A very actual challenge (maybe a holy grail ?) lies in the definition of a computation model appropriate to dynamic systems. This is a fundamental question. As an example there are a lot of P2P protocols but none of them is formally defined with respect to an underlying computing model. Similarly to the work of Lamport on “static” systems, a model has to be defined for dynamic systems. This theoretical research is a necessary condition if one wants to understand the behavior of these systems. As the aim of a theory is to codify knowledge in order it can be transmitted, the definition of a realistic model for dynamic systems is inescapable whatever the aim we have in mind, be it teaching, research or engineering.
Distributed computability
Among the fundamental theoretical results of distributed computing, there is a list of problems (e.g. consensus or non-blocking atomic commit) that have been proved to have no deterministic solution in asynchronous distributed computing systems prone to failures. In order such a problem becomes solvable in an asynchronous distributed system, which system has to be enriched with an appropriate oracle (also called failure detectors). We have been deeply involved in this research and designed optimal consensus algorithms suited to different kind of oracles. This line of research paves the way to rank the distributed computing problems according to the “power” of the additional oracle they need (think “additional oracle” as “additional assumptions”). The ultimate goal would be the statement of a distributed computing hierarchy, according to the minimal assumptions needed to solve distributed computing problems (similarly to the Chomsky’s hierarchy that ranks problems/languages according to the type of automaton they need to be solved).
Distributed computing abstractions
Major advances in sequential computing came from machine-independent data abstractions such as sets, records, etc., and control abstractions such as while, if, etc., and modular constructs such as functions and procedures. Today, no one can envisage not to use these abstractions. In the “static” distributed computing field, some abstractions have been promoted and proved to be useful. Reliable broadcast, consensus, interactive consistency are examples of such abstractions. These abstractions have well-defined specifications. There are both a lot of theoretical results on them (mainly decidability and lower bounds), and numerous implementations. There is no such equivalent for dynamic distributed systems.
