Distributed Computing Through Combinatorial Topology

Definitions

For us, a distributed system is a collection of sequential computing entities, called processes, that cooperate to solve a problem, called a task. The processes may communicate by message passing, shared memory, or any other mechanism. Each process runs a program that defines how and when it communicates with other processes. Collectively these programs define a distributed algorithm or protocol. (Rajsbaum, Kozlo, and Herlihy 2014, 4)

The essential properties of Distributed Systems:

  • Local views. First, each process has only a local view of the current state of the world. That is, a process is uncertain about the views of the other processes.
  • Evolution of local views. Second, processes communicate with one another. Each communication modifies local views. If they communicate everything they know and the communication is flawless and instantaneous, they end up with identical local views, eliminating uncertainty. The systems we study are interesting precisely because this is usually not the case, either because processes communicate only part of what they know (for efficiency) or communication is imperfect (due to delays or failures).

(Rajsbaum, Kozlo, and Herlihy 2014, 6)

References:

Rajsbaum, Sergio, Dmitry Kozlo, and Maurice Herlihy. 2014. “Distributed Computing through Combinatorial Topology.”