6.046 distributed algorithms

• Terms
• Synchronous
  • Leader election
  • Maximal independent set
  • Breadth-first spanning tree
  • shortest paths trees
• Asynchronous
  • Breadth-first spanning trees
  • shortest paths trees

One purpose of this blog is to explain distributed algorithms in plain words :) as I find the lecture slides are somewhat mathematical to myself.

Terms¶

1. Distributed algorithms are algorithms that run on networked processors or on multiprocessors that share memory.
2. Two common models are covered in this lecture, asyn/sync distributed computing models
3. Config: Distributed networks are represented by an undirected connected graph G = (V, E). A node represents vertex/process. An edge represents communication channel. Assume no failures.
4. A clique network: all vertices are directly connected to all others.

Synchronous¶

Leader election¶

A leader acts as the coordinator of servers. First try to use algorithms composed of deterministic, indistinguishable processes to choose a leader. The professor give a theorem which proves it will never work. Then we move to algorithms composed of randomness and distinguishable processes (UID, unique identifiers) to break symmetry.

• (symmetry -> asymmetry): deterministic => randomness, indistinguishable processes => UIDs

  

Maximal independent set¶

Breadth-first spanning tree¶

shortest paths trees¶

Asynchronous¶

abstract properties of executions ?

Breadth-first spanning trees¶

shortest paths trees¶