A pleasant stroll through the land of distributed machines, computation, and universality

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Not only the world is distributed, but more and more applications are distributed. Hence, a fundamental question is the following one: What can be computed in a distributed system? The answer to this question depends on the environment in which evolves the considered distributed system, i.e., on the assumptions the system relies on. This environment is very often left implicit and nearly always not formulated in terms of precise underlying requirements. In the extreme case where the environment is such that there is no synchrony assumption and the computing entities may commit failures, some problems become impossible to solve. Given a distributed computing problem, it is consequently important to know the weakest assumptions (lower bounds) that give the limits beyond which the considered distributed problem cannot be solved. This paper is a short introduction to this kind of issues. It is made up of short sections, each addressing an important point of the theory of distributed computing. Its style is voluntarily informal.

Original languageEnglish
Title of host publicationMachines, Computations, and Universality - 8th International Conference, MCU 2018, Proceedings
EditorsJérôme Durand-Lose, Sergey Verlan
PublisherSpringer-Verlag
Pages34-50
Number of pages17
ISBN (Print)9783319924014
DOIs
Publication statusPublished - 1 Jan 2018
Event8th International Conference on Machines, Computations, and Universality, MCU 2018 - Fontainebleau, France
Duration: 28 Jun 201830 Jun 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10881 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Machines, Computations, and Universality, MCU 2018
CountryFrance
CityFontainebleau
Period28/06/1830/06/18

Keywords

  • Agreement
  • Asynchronous system
  • Atomicity
  • Concurrency
  • Consensus number
  • Consensus object
  • Crash failure
  • Distributed complexity
  • Distributed computability
  • Distributed computing
  • Environment
  • Fault-tolerance
  • Impossibility result
  • Indistinguishability
  • Message adversary
  • Message-passing system
  • Non-blocking
  • Obstruction-freedom
  • Progress condition
  • Read/write system
  • Synchronous system
  • Task
  • Universal construction
  • Wait-freedom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this