Local Algorithms: Past, Present, Future

Summary

On 26–27 April 2011, I gave a tutorial on local algorithms at the MITACS Workshop on Wireless Networks and Mobile Computing at Carleton University. The tutorial consisted of two parts:

• Part A: Tuesday, 26 April 2011, 11:00am–12:30pm
• Part B: Wednesday, 27 April 2011, 11:00am–12:30pm

Abstract

A local algorithm is a distributed algorithm that runs in constant time, independently of the size of the network. Being highly scalable and fault-tolerant, such algorithms are ideal in the operation of large-scale distributed systems such as computer networks.

Even though the model of local algorithms is very limited, in recent years we have seen many positive results for non-trivial problems. In this tutorial, I will give an overview of the state-of-the-art in the field of local algorithms. I will present examples of recent advances in the field, and I will explore the current frontiers and fundamental open questions.

Slides

• Presentation slides (PDF).

Outline

Background

• Graphs
  • n = number of nodes.
  • ∆ = maximum degree.
  • Bounded-degree graphs: ∆ = O(1).
• Graph problems
  • Independent set, matching, vertex cover, dominating set, edge dominating set, graph colouring…
  • Standard terminology, e.g.:
    • Maximal matching: you cannot add any new edges.
    • Maximum matching: the largest possible number of edges.
    • 2-approximation of maximum matching: at least OPT/2 edges, where OPT = size of a maximum matching.
    • Minimal vertex cover: you cannot remove any node.
    • Minimum vertex cover: the smallest possible number of nodes.
    • 2-approximation of vertex cover: at most 2 × OPT nodes, where OPT = size of a minimum vertex cover.
• Local outputs
  • Each node produces its own part of output.
  • Graph colouring: each node outputs its own colour.
  • Independent set, vertex cover, dominating set, etc.: each node indicates whether it is part of the solution or not.
  • Matching, etc.: each node indicates whether it is matched and with whom (must be consistent).
• Local algorithms
  • Mapping from constant-radius neighbourhoods to local outputs.
  • Distributed algorithm that runs in constant time, independently of the size of the network.
  • Radius of the local neighbourhood = number of communication rounds = local horizon = r = O(1).
  • Fault-tolerant and robust: local algorithms are also self-stabilising algorithms.

Past

Bad news:

• Many negative results: Linial (1992), Naor–Stockmeyer (1995), Czygrinow–Hańćkowiak–Wawrzyniak (2008), Lenzen–Wattenhofer (2008).
• A key technique: Ramsey's theorem – we applied the hypergraph version of the theorem.

Three traditional escapes:

1. Randomised local algorithms
   • Simple randomised algorithm for finding independent sets. Running time: 1 round.
   • Exercises:
     • What is the expected size of an independent set in a cycle? Can you do better with a different 1-round algorithm? Can you do better with a constant-time algorithm?
     • What about general bounded-degree graphs? Can you design a randomised local algorithm that finds an O(∆)-approximation of maximum independent set in bounded-degree graphs?
2. Local algorithms for geometric graphs
   • Geometric graphs:
     • Civilised graph: length of an edge is at most 1; distance between any pair of nodes is at least s.
     • Unit disk graph: length of an edge is at most 1; distance between any pair of non-adjacent nodes is larger than 1.
     • Quasi unit disk graph: length of an edge is at most 1; distance between any pair of non-adjacent nodes is larger than d.
   • Location-aware algorithms: each node knows its own coordinates.
   • Examples of the divide-and-conquer approach:
     • 3-approximation of graph colouring: colour the tiles, colour the nodes within each tile, combine.
     • More examples: Analysing local algorithms in location-aware quasi unit-disk graphs.
3. Almost local algorithms
   • Colour reduction technique:
     • Cole–Vishkin (1986), Goldberg–Plotkin–Shannon (1988)
     • From k colours to O(log k) colours in one round – see the example below.
     • Iterate: from k colours to O(1) colours in O(log* k) rounds.
     • This is for paths and cycles, but similar techniques can be used as a subroutine in more general algorithms that can be applied in any bounded-degree graph. For example, Goldberg–Plotkin–Shannon (1988) and Panconesi–Rizzi (2001) show how to reduce the number of colours from k colours to ∆ + 1 colours in O(∆² + log* k) rounds.
     • Examples of recent work: Kuhn (2009) and Barenboim–Elkin (2009) show how to find a (∆ + 1)-colouring in O(∆ + log* n) rounds.
   • Once we have broken symmetry by finding a colouring with few colours, we can solve many other problems easily:
     • Maximal independent set: We can simulate the centralised (non-distributed) greedy algorithm, which processes nodes in an arbitrary order, one by one, and adds each node to the independent set if possible (if its neighbours have not been added previously). In the distributed algorithm, we can process all nodes of colour 0 simultaneously in parallel; then all nodes of colour 1, etc.
     • Maximal matching: Similar – find an edge colouring and process all edges of colour i in parallel, for each i.
     • Dominating sets: We can simulate the centralised greedy approximation algorithm – see, e.g., Friedman–Kogan (2011).

Present

Problems that do not require symmetry-breaking in cycles:

1. Linear programming (LPs)
   • Local approximation schemes for packing and covering LPs: Kuhn–Moscibroda–Wattenhofer (2006).
   • Other examples: local approximation algorithms for max-min and min-max LPs.
2. Vertex covers
   • The best known local algorithm: 2-approximation in O(∆) rounds.
   • A simpler local algorithms: 3-approximation in O(∆) rounds – this is what we cover in the presentation.
     • Formally, the “virtual graph” that we constructed is known as the bipartite double cover of the original graph.
     • If we could find a maximal matching in the original graph, we could simply take all matched nodes and we would have a 2-approximation of minimum vertex cover. Unfortunately, a local algorithm cannot find a maximal matching in the original graph (again, consider the case of a cycle).
     • However, we can find a maximal matching in the virtual graph. This is possible because the virtual graph is 2-coloured; we can exploit the colours to break symmetry (black nodes and white nodes have different roles in the proposal-algorithm).
   • Exercise:
     • Prove that the 3-approximation algorithm is correct: it produces a vertex cover, and the output is at most 3 times as large as a minimum-size vertex cover.
     • Hints: It may be helpful to compare it with the centralised 2-approximation algorithm that finds a maximal matching and outputs all matched nodes. It is easier to first prove that the approximation factor is at most 4, and then try to find a worst-case input.
3. Edge dominating sets
   • Local algorithm: (4 − 2/∆)-approximation.

Future

New directions:

1. Local algorithms for symmetry-breaking problems
   • In some cases, it is possible to break symmetry with a local algorithm!
   • Case study: scheduling problems
     • More formally, this is a generalisation of fractional graph colouring.
     • Fractional graph colouring requires symmetry-breaking in a cycle – just like the usual graph colouring problem. Adjacent nodes must output different schedules.
     • However, the lower-bound results do not apply!
     • Key observation: non-constant-size output is possible – and we can exploit it.
   • Take-home message: We do not yet understand the full potential of local algorithms!
2. Nondeterministic models
   • Case study: locally checkable proofs
     • Focus: decision problems – for example, recognising graph properties.
     • How to prove that we have a yes-instance?
     • Local verifier: the proof must be locally checkable.
     • Proof complexity: how many bits per node is required?
     • Closely related work: Korman–Kutten–Peleg (2005), Korman–Kutten (2006), Korman–Kutten (2007), Fraigniaud–Korman–Peleg (2011), …
   • Take-home message: We can use the concept of local algorithms to analyse global problems!

Colour Reduction Example

In this example, the graph is a path. Each row represents a node and each column represents a time step. In each time step, the new colour of a node v is a function of the old colour of v and the old colour of v's predecessor (below v in the illustration).

Here the initial colouring consisted of 16-bit unique identifiers. That is, we had a colour space with 65536 possible colours (numbered 0, 1, …, 65535). After one round, we have 2 log 65536 = 2 × 16 = 32 colours, and after two rounds we have only 2 log 32 = 2 × 5 = 10 colours left.

In decimal:

In binary:

Further Reading

• Survey of local algorithms (manuscript, 2011).
• Course on deterministic distributed algorithms (2010).
• If you have any questions, you can email me or you can try the new Q&A web site cstheory.stackexchange.com.