Non-negotiating Distributed Computing

A recent trend in distributed computing aims at designing models as simple as possible for capturing the inherently limited computing and communication capabilities of insects, cells, or tiny technological artefacts, yet powerful enough for solving non trivial tasks. This paper is contributing further in this field, by introducing a new model of distributed computing, that we call non-negotiating. In the non-negotiating model, a process decides a priori what it is going to communicate to the other processes, before the computation starts. Thus, the information a process sends does not depend on what the process hears from others during an execution. We consider non-negotiating distributed computing in the read/write shared memory model in which processes are asynchronous and subject to crash failures. We show that non-negotiating distributed computing is universal, in the sense that it is capable of solving any colorless task solvable by an unrestricted full-information algorithm in which processes can remember all their history, and send it to the other processes at any point in time. To prove this universality result, we present a non-negotiating algorithm for solving multidimensional approximate agreement, with arbitrary precision  \(\epsilon >0\) .