Exploring Link Reversal Algorithms in Distributed Systems
Link reversal algorithms are a distributed algorithm design technique used in various problem-solving scenarios like routing, leader election, mutual exclusion, and more. By modeling problems as directed graphs and strategically reversing links based on local knowledge, these algorithms efficiently tackle complex distributed system challenges.
Uploaded on Oct 02, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Link Reversal Algorithms Jennifer L. Welch DISC 2014 Tutorial
What is Link Reversal? Distributed algorithm design technique Used in solutions for a variety of problems routing, leader election, mutual exclusion, scheduling, resource allocation, Model problem as a directed graph and reverse the direction of links appropriately Use local knowledge to decide which links to reverse 1
Outline 1. Routing in a Graph: Correctness 2. Routing in a Graph: Complexity 3. Routing and Leader Election in a Distributed System 4. Mutual Exclusion in a Distributed System 5. Scheduling in a Graph 6. Resource Allocation in a Distributed System 2
Section 1 ROUTING IN A GRAPH: CORRECTNESS 3
Routing [Gafni & Bertsekas 1981] Undirected connected graph represents communication topology of a system D 1 2 3 Unique destination node 4 5 6 4
Routing [Gafni & Bertsekas 1981] Assign virtual directions to the graph edges (links) s.t. D if nodes forward messages over the links, they reach the destination 3 1 2 Directed version of the graph (orientation) must 4 5 6 be acyclic have destination as only sink Thus every node has path to destination. 5
Mending Routes What happens if some edges go away? Might need to change the virtual directions on some remaining edges (reverse some links) More generally, starting with an arbitrary directed graph, each vertex should decide independently which of its incident links to reverse 6
Mending Routes Example D 3 1 2 4 5 6 7
Sinks A vertex with no outgoing links is a sink. The property of being a sink can be detected locally. A sink can then reverse some incident links Basis of several algorithms sink 8
Full Reversal Routing Algorithm Input: directed graph G with destination vertex D Let S(G) be set of sinks in G other than D while S(G) is nonempty do reverse every link incident on a vertex in S(G) G now refers to resulting directed graph 9
Full Reversal (FR) Routing Example D D D 3 2 3 1 1 2 1 3 2 5 4 4 6 4 5 5 6 6 D D D 3 2 1 3 1 2 2 3 1 4 5 6 4 4 5 6 5 6 10
Why Does FR Terminate? Suppose it does not. Let W be vertices that take infinitely many steps X (stop) D nonempty by assumption Let X be vertices that take finitely many steps x nonempty since it includes D Consider neighboring vertices w in W, x in X w exist since graph is connected W (don t stop) Consider first step by w after last step by x: link is w x and stays that way forever. Then w cannot take any more steps, contradiction. 11
Why is FR Correct? Assume input graph is acyclic. Acyclicity is preserved at each iteration: Any new cycle introduced must include a vertex that just took a step, but such a vertex is now a source (has no incoming links) When FR terminates, no vertex, except possibly D, is a sink. A DAG must have at least one sink: if no sink, then a cycle can be constructed Thus output graph is acyclic and D is the unique sink. 12
Pair Algorithm easy to argue Can implement FR by having each vertex v keep an ordered pair (c,v), the height (or vertex label) of vertex v c is an integer counter that can be incremented v is the id of vertex v View link between v and u as being directed from vertex with larger height to vertex with smaller height (compare pairs lexicographically) If v is a sink then v sets c to be 1 larger than maximum counter of all v s neighbors 13
Pair Algorithm Example (1,0) 0 3 1 2 (0,1) (2,1) (0,2) (2,3) 14
Pair Algorithm Example (1,0) 0 3 1 2 (0,1) (2,1) (0,2) (3,2) (2,3) 15
Pair Algorithm Example (1,0) 0 3 1 2 (0,1) (2,1) (0,2) (3,2) (2,3) 16
Partial Reversal Routing Algorithm Try to avoid repeated reversals of the same link. Vertices keep track of which incident links have been reversed recently. Link (u,v) is reversed by v iff the link has not been reversed by u since the last iteration in which v took a step. 17
Partial Reversal (PR) Routing Example D D D 3 2 3 1 1 2 1 3 2 5 4 4 6 4 5 5 6 6 D D D 3 2 1 3 1 2 2 3 1 4 5 6 4 4 5 6 5 6 18
Why is PR Correct? Termination can be proved similarly as for FR: difference is that it might take two steps by w after last step by x until link is w x . X (stop) D x w W (don t stop) 19
Why is PR Correct? Preservation of acyclicity is more involved, deferred to later. Alternate geometric proof due to Radeva and Lynch 2011 20
Triple Algorithm not so easy to argue Can implement PR by having each vertex v keep an ordered triple (a,b,v), the height (or vertex label) of vertex v a and b are integer counters v is the id of vertex v View link between v and u as being directed from vertex with larger height to vertex with smaller height (compare triples lexicographically) If v is a sink then v sets a to be 1 greater than smallest a of all its neighbors sets b to be 1 less than smallest b of all its neighbors with new value of a (if none, then leave b alone) 21
Triple Algorithm Example (0,1,0) 0 3 1 2 (0,0,1) (1,0,1) (0,0,2) (0,2,3) 22
Triple Algorithm Example (0,1,0) 0 3 1 2 (0,0,1) (1,0,1) (0,0,2) (1,-1,2) (0,2,3) 23
Triple Algorithm Example (0,1,0) 0 3 1 2 (0,0,1) (1,0,1) (0,0,2) (1,-1,2) (0,2,3) 24
General Vertex Label Algorithm Generalization of Pair and Triple algorithms Assign a label to each vertex s.t. labels are from a totally ordered, countably infinite set new label for a sink depends only on old labels for the sink and its neighbors sequence of labels taken on by a vertex increases without bound 25
Correctness of General Vertex Label Algorithm Termination: Similar to the arguments for LR and PR. X (stop) D Difference is that it might take several steps by w after last step by x until link is w x. x However it will happen because w s label increases without bound and eventually is larger than x s final label. w W (don t stop) 26
Correctness of General Vertex Label Algorithm Acyclicity is preserved because labels are from a totally ordered set 27
Relationship Between Algorithms FR PR ? Pair Algorithm Triple Algorithm General Vertex Label Algorithm 28
Binary Link Labels Routing [Charron-Bost et al. 2013] Alternate way to implement and generalize FR and PR Instead of unbounded vertex labels, apply binary link labels to input DAG link directions are independent of labels (in contrast to algorithms using vertex labels) Algorithm for a sink: if at least one incident link is labeled 0, then reverse all incident links labeled 0 and flip labels on all incident links if no incident link is labeled 0, then reverse all incident links but change no labels 29
Binary Link Labels Example 0 1 0 3 1 2 1 0 30
Binary Link Labels Example 0 1 0 3 1 2 1 0 31
Binary Link Labels Example 0 1 0 3 1 2 0 1 32
Why is BLL Correct? Termination can be proved very similarly to termination for PR. X (stop) D x Takes 1 or 2 steps until link is w x. w W (don t stop) 33
Why is BLL Correct? What about acyclicity preservation? Depends on initial labeling: 3 3 1 1 0 0 1 0 2 1 2 1 0 0 0 0 34
Conditions on Initial Labeling All labels are the same all 1 s => Full Reversal all 0 s => Partial Reversal Every vertex has all incoming links labeled the same ( uniform labeling) Both of the above are special cases of a more general condition that is necessary and sufficient for preserving acyclicity 35
Relationship Between Algorithms Revisited Binary Link Label Algorithm FR PR ? Pair Algorithm Triple Algorithm General Vertex Label Algorithm 36
Section 2 ROUTING IN A GRAPH: COMPLEXITY 37
What About Complexity? Busch et al. (2003,2005) initiated study of the performance of link reversal routing Work complexity of a vertex: number of steps taken by the vertex Global work complexity: sum of work complexity of all vertices 38
Worst-Case Work Complexity Bounds [Busch et al.] bad vertex: has no (directed) path to dest. Pair algorithm (Full Reversal): for every input, global work complexity is O(n2), where n is number of initial bad vertices for every n, there exists an input with n bad vertices with global work complexity (n2) Triple algorithm (~Partial Reversal): same as Pair algorithm (if appropriately initialized) 39
Exact Work Complexity Bounds A more fine-grained question: Given any input graph and any vertex in that graph, exactly how many steps does that vertex take? Busch et al. answered this question for FR. Charron-Bost et al. answered this question for BLL (as long as labeling satisfies Acyclicity Condition): includes FR and PR. 40
Definitions Let C = <v1, v2, , vk> be a chain in the labeled input DAG (series of vertices s.t. either (vi,vi+1) or (vi+1,vi) is a link). r: number of links that are labeled 1 and rightway ((vi,vi+1) is a link, i.e., directed away from D) s: number of occurrences of vertices s.t. the two adjacent links are incoming and labeled 0 Res: 1 if last link in X is labeled 0 and rightway, else 0 41
Example of Definitions 1 0 1 1 2 3 8 0 0 D 4 1 1 1 0 7 6 5 For chain <D,7,6,5>: r = 1, s = 0, Res = 1 For chain <D,1,2,3,4,5>: r = 2, s = 1, Res = 0 42
Grouping the Vertices D is set of all vertices with an incoming link labeled 0 and either an incoming link labeled 1 or an outgoing link S is all other vertices (all incoming links, if any, labeled 1 or a sink with all links labeled 0) 0 groupS S groupD 1 0 1 D 1 0 0 1 0 0 1 43
BLL Work Complexity Theorem: The work complexity of vertex v is min{r(C) + s(C) + Res(C) : C is a chain from D to v} if v is in S min{2r(C) + 2s(C) + Res(C) : C is a chain from D to v} if v is in D Proof is by showing how different combinations of r, s, and Res are either invariant or increase by certain amounts throughout execution until a chain becomes a path from v to D. 44
Work Complexity for FR Recall: The work complexity of vertex v is min{r(C) + s(C) + Res(C) : C is a chain from D to v} if v is in S min{2r(C) + 2s(C) + Res(C) : C is a chain from D to v} if v is in D For FR (all labels are 1), all vertices are in S, s(C) = 0, and Res(C) = 0. Thus formula becomes minimum, over all chains from D to v, of number of links in the chain that are directed away from D Worst-case graph for global work complexity: D 1 2 n vertex i has work complexity i global work complexity then is (n2) 45
Work Complexity for PR For PR (all labels are 0 initially), work complexity of vertex v is min, over all D-to-v chains, of s + Res if v is a sink or a source initially min, over all D-to-v chains, of 2s + Res if v is neither a sink nor a source initially Worst-case graph for global work complexity: D 1 2 3 n work complexity of vertex i is (i) global work complexity is (n2) 46
Comparing FR and PR Looking at worst-case global work complexity shows no difference both are quadratic in number of bad vertices Can use game theory to show some meaningful differences (Charron-Bost et al. 2013) Consider class of uniform labelings: for each vertex, all incoming links have the same binary label A vertex s choice of initial label for its incoming links can be viewed as its strategy in a game 0 1 1 0 v Should v play or ? v 1 0 47
Comparing FR and PR with Game Theory Compare FR and PR among all uniform labelings (every vertex initially has all its incoming links with same label) Global work complexity of FR can be larger than optimal (w.r.t. all uniform labelings) by a factor of (n) Global work complexity of PR is never more than twice the optimal Thus PR is a safer bet than than FR w.r.t. global work complexity 48
Time Complexity Time complexity is number of iterations in greedy execution (all sinks take step in each iteration) Busch et al. (2003, 2005) observed that time complexity cannot exceed global work complexity Thus O(n2) iterations for both pair (FR) and triple (~PR) algorithms Busch et al. also showed graphs on which pair (FR) and triple (~PR) algorithms require (n2) iterations 49
