A Look at Basics of Distributed Computing

This tutorial presents concepts and basics of distributed computing which are important (at least from the author's point of view!), and should be known and mastered by Master students, researchers, and engineers. Those include: (a) a characterization of distributed computing (which is too much often confused with parallel computing); (b) the notion of a synchronous system and its associated notions of a local algorithm and message adversaries; (c) the notion of an asynchronous shared memory system and its associated notions of universality and progress conditions; and (d) the notion of an asynchronous messagepassing system with its associated broadcast and agreement abstractions, its impossibility results, and approaches to circumvent them. Hence, the tutorial can be seen as a guided tour to key elements that constitute basics of distributed computing.