Local Algorithms: Past, Present, Future
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
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.
- n = number of nodes.
- ∆ = maximum degree.
- Bounded-degree graphs: ∆ = O(1).
- Graph problems
- Independent set,
edge dominating set,
- 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.
Three traditional escapes:
- Randomised local algorithms
- Simple randomised algorithm for finding independent sets. Running time: 1 round.
- 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?
- 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:
- Almost local algorithms
- Colour reduction technique:
- 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).
Problems that do not require symmetry-breaking in cycles:
- Linear programming (LPs)
- 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).
- 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.
- Edge dominating sets
- 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!
- Nondeterministic models
- Case study: locally checkable proofs
- 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.
|11110101000011||→||(8, 1)||=||10001||→||(0, 1)||=||1||→||(0, 1)||=||1|
|110001000011||→||(8, 0)||=||10000||→||(0, 0)||=||0||→||(0, 0)||=||0|
|1110101000011||→||(11, 1)||=||10111||→||(2, 1)||=||101||→||(1, 0)||=||10|
|1010101000011||→||(1, 1)||=||11||→||(1, 1)||=||11||→||(1, 1)||=||11|
|11010100000101||→||(8, 1)||=||10001||→||(4, 1)||=||1001||→||(0, 1)||=||1|
|10000000101||→||(0, 1)||=||1||→||(3, 0)||=||110||→||(0, 0)||=||0|
|11010000100100||→||(12, 1)||=||11001||→||(0, 1)||=||1||→||(1, 0)||=||10|
|10010000100100||→||(11, 0)||=||10110||→||(1, 1)||=||11||→||(0, 1)||=||1|
|110000100100||→||(0, 0)||=||0||→||(0, 0)||=||0||→||(0, 0)||=||0|
|11110101100011||→||(8, 1)||=||10001||→||(0, 1)||=||1||→||(0, 1)||=||1|
|10010001100011||→||(8, 0)||=||10000||→||(0, 0)||=||0|