Lecture notes Distributed Computing

distributed computing system lecture notes and how distributed computing works. how to distributed computing at home | pdf free download
Dr.JamesSmith Profile Pic
Dr.JamesSmith,France,Professional
Published Date:11-07-2017
Your Website URL(Optional)
Comment
  Principles of Distributed Computing Roger Wattenhofer wattenhoferethz.ch Spring 2016iiContents 1 Vertex Coloring 5 1.1 Problem & Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Coloring Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Tree Algorithms 15 2.1 Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Convergecast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 BFS Tree Construction . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 MST Construction . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 Leader Election 23 3.1 Anonymous Leader Election . . . . . . . . . . . . . . . . . . . . . 23 3.2 Asynchronous Ring . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4 Synchronous Ring . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4 Distributed Sorting 33 4.1 Array & Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Sorting Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3 Counting Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5 Shared Memory 47 5.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 Mutual Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3 Store & Collect . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.3.1 Problem De nition . . . . . . . . . . . . . . . . . . . . . . 51 5.3.2 Splitters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.3.3 Binary Splitter Tree . . . . . . . . . . . . . . . . . . . . . 53 5.3.4 Splitter Matrix . . . . . . . . . . . . . . . . . . . . . . . . 55 6 Shared Objects 59 6.1 Centralized Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.2 Arrow and Friends . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.3 Ivy and Friends . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 7 Maximal Independent Set 71 7.1 MIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.2 Original Fast MIS . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.3 Fast MIS v2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 iiiiv CONTENTS 7.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8 Locality Lower Bounds 85 8.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 8.2 Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.3 The Neighborhood Graph . . . . . . . . . . . . . . . . . . . . . . 88 9 Social Networks 93 9.1 Small World Networks . . . . . . . . . . . . . . . . . . . . . . . . 94 9.2 Propagation Studies . . . . . . . . . . . . . . . . . . . . . . . . . 100 10 Synchronization 105 10.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 10.2 Synchronizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 10.3 Synchronizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 10.4 Synchronizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 10.5 Network Partition . . . . . . . . . . . . . . . . . . . . . . . . . . 110 10.6 Clock Synchronization . . . . . . . . . . . . . . . . . . . . . . . . 112 11 Communication Complexity 119 11.1 Diameter & APSP . . . . . . . . . . . . . . . . . . . . . . . . . . 119 11.2 Lower Bound Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 121 11.3 Communication Complexity . . . . . . . . . . . . . . . . . . . . . 124 11.4 Distributed Complexity Theory . . . . . . . . . . . . . . . . . . . 129 12 Wireless Protocols 133 12.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 12.2 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 12.2.1 Non-Uniform Initialization . . . . . . . . . . . . . . . . . 135 12.2.2 Uniform Initialization with CD . . . . . . . . . . . . . . . 135 12.2.3 Uniform Initialization without CD . . . . . . . . . . . . . 137 12.3 Leader Election . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 12.3.1 With High Probability . . . . . . . . . . . . . . . . . . . . 137 12.3.2 Uniform Leader Election . . . . . . . . . . . . . . . . . . . 138 12.3.3 Fast Leader Election with CD . . . . . . . . . . . . . . . . 139 12.3.4 Even Faster Leader Election with CD . . . . . . . . . . . 139 12.3.5 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . 142 12.3.6 Uniform Asynchronous Wakeup without CD . . . . . . . . 142 12.4 Useful Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 13 Stabilization 147 13.1 Self-Stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 13.2 Advanced Stabilization . . . . . . . . . . . . . . . . . . . . . . . . 152 14 Labeling Schemes 157 14.1 Adjacency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 14.2 Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 14.3 Road Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160CONTENTS v 15 Fault-Tolerance & Paxos 165 15.1 Client/Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 15.2 Paxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 16 Consensus 177 16.1 Two Friends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 16.2 Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 16.3 Impossibility of Consensus . . . . . . . . . . . . . . . . . . . . . . 178 16.4 Randomized Consensus . . . . . . . . . . . . . . . . . . . . . . . 183 16.5 Shared Coin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 17 Byzantine Agreement 189 17.1 Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 17.2 How Many Byzantine Nodes? . . . . . . . . . . . . . . . . . . . . 191 17.3 The King Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 193 17.4 Lower Bound on Number of Rounds . . . . . . . . . . . . . . . . 194 17.5 Asynchronous Byzantine Agreement . . . . . . . . . . . . . . . . 195 18 Authenticated Agreement 199 18.1 Agreement with Authentication . . . . . . . . . . . . . . . . . . . 199 18.2 Zyzzyva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 19 Quorum Systems 211 19.1 Load and Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 19.2 Grid Quorum Systems . . . . . . . . . . . . . . . . . . . . . . . . 213 19.3 Fault Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 19.4 Byzantine Quorum Systems . . . . . . . . . . . . . . . . . . . . . 218 20 Eventual Consistency & Bitcoin 223 20.1 Consistency, Availability and Partitions . . . . . . . . . . . . . . 223 20.2 Bitcoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 20.3 Smart Contracts . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 20.4 Weak Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . 233 21 Distributed Storage 237 21.1 Consistent Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . 237 21.2 Hypercubic Networks . . . . . . . . . . . . . . . . . . . . . . . . . 238 21.3 DHT & Churn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 22 Game Theory 251 22.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 22.2 Prisoner's Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . 251 22.3 Sel sh Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 22.4 Braess' Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 22.5 Rock-Paper-Scissors . . . . . . . . . . . . . . . . . . . . . . . . . 256 22.6 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . 257vi CONTENTS 23 Dynamic Networks 261 23.1 Synchronous Edge-Dynamic Networks . . . . . . . . . . . . . . . 261 23.2 Problem De nitions . . . . . . . . . . . . . . . . . . . . . . . . . 262 23.3 Basic Information Dissemination . . . . . . . . . . . . . . . . . . 263 23.4 Small Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 23.4.1 k-Veri cation . . . . . . . . . . . . . . . . . . . . . . . . . 266 23.4.2 k-Committee Election . . . . . . . . . . . . . . . . . . . . 267 23.5 More Stable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 269 24 All-to-All Communication 273 25 Multi-Core Computing 281 25.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 25.1.1 The Current State of Concurrent Programming . . . . . . 281 25.2 Transactional Memory . . . . . . . . . . . . . . . . . . . . . . . . 283 25.3 Contention Management . . . . . . . . . . . . . . . . . . . . . . . 284 26 Dominating Set 293 26.1 Sequential Greedy Algorithm . . . . . . . . . . . . . . . . . . . . 294 26.2 Distributed Greedy Algorithm . . . . . . . . . . . . . . . . . . . . 295 27 Routing 303 27.1 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 27.2 Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 27.3 Routing in the Mesh with Small Queues . . . . . . . . . . . . . . 305 27.4 Hot-Potato Routing . . . . . . . . . . . . . . . . . . . . . . . . . 306 27.5 More Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 28 Routing Strikes Back 311 28.1 Butter y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 28.2 Oblivious Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 312 28.3 Oine Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313Introduction What is Distributed Computing? In the last few decades, we have experienced an unprecedented growth in the area of distributed systems and networks. Distributed computing now encom- passes many of the activities occurring in today's computer and communications world. Indeed, distributed computing appears in quite diverse application areas: The Internet, wireless communication, cloud or parallel computing, multi-core systems, mobile networks, but also an ant colony, a brain, or even the human society can be modeled as distributed systems. These applications have in common that many processors or entities (often called nodes) are active in the system at any moment. The nodes have certain degrees of freedom: they have their own hard- and software. Nevertheless, the nodes may share common resources and information, and, in order to solve a problem that concerns severalor maybe even allnodes, coordination is necessary. Despite these commonalities, a human brain is of course very di erent from a quadcore processor. Due to such di erences, many di erent models and parame- ters are studied in the area of distributed computing. In some systems the nodes operate synchronously, in other systems they operate asynchronously. There are simple homogeneous systems, and heterogeneous systems where di erent types of nodes, potentially with di erent capabilities, objectives etc., need to inter- act. There are di erent communication techniques: nodes may communicate by exchanging messages, or by means of shared memory. Occasionally the commu- nication infrastructure is tailor-made for an application, sometimes one has to work with any given infrastructure. The nodes in a system often work together to solve a global task, occasionally the nodes are autonomous agents that have their own agenda and compete for common resources. Sometimes the nodes can be assumed to work correctly, at times they may exhibit failures. In contrast to a single-node system, distributed systems may still function correctly despite failures as other nodes can take over the work of the failed nodes. There are di erent kinds of failures that can be considered: nodes may just crash, or they might exhibit an arbitrary, erroneous behavior, maybe even to a degree where it cannot be distinguished from malicious (also known as Byzantine) behavior. It is also possible that the nodes follow the rules indeed, however they tweak the parameters to get the most out of the system; in other words, the nodes act sel shly. Apparently, there are many models (and even more combinations of models) that can be studied. We will not discuss them in detail now, but simply de ne 12 CONTENTS them when we use them. Towards the end of the course a general picture should emerge, hopefully Course Overview This course introduces the basic principles of distributed computing, highlight- ing common themes and techniques. In particular, we study some of the funda- mental issues underlying the design of distributed systems:  Communication: Communication does not come for free; often communi- cation cost dominates the cost of local processing or storage. Sometimes we even assume that everything but communication is free.  Coordination: How can you coordinate a distributed system so that it performs some task eciently? How much overhead is inevitable?  Fault-tolerance: A major advantage of a distributed system is that even in the presence of failures the system as a whole may survive.  Locality: Networks keep growing. Luckily, global information is not always needed to solve a task, often it is sucient if nodes talk to their neighbors. In this course, we will address whether a local solution is possible.  Parallelism: How fast can you solve a task if you increase your computa- tional power, e.g., by increasing the number of nodes that can share the workload? How much parallelism is possible for a given problem?  Symmetry breaking: Sometimes some nodes need to be selected to or- chestrate computation or communication. This is achieved by a technique called symmetry breaking.  Synchronization: How can you implement a synchronous algorithm in an asynchronous environment?  Uncertainty: If we need to agree on a single term that ttingly describes this course, it is probably \uncertainty". As the whole system is distrib- uted, the nodes cannot know what other nodes are doing at this exact moment, and the nodes are required to solve the tasks at hand despite the lack of global knowledge. Finally, there are also a few areas that we will not cover in this course, mostly because these topics have become so important that they deserve their own courses. Examples for such topics are distributed programming or secu- rity/cryptography. In summary, in this class we explore essential algorithmic ideas and lower bound techniques, basically the \pearls" of distributed computing and network algorithms. We will cover a fresh topic every week. Have funBIBLIOGRAPHY 3 Chapter Notes Many excellent text books have been written on the subject. The book closest to this course is by David Peleg Pel00, as it shares about half of the material. A main focus of Peleg's book are network partitions, covers, decompositions, and spanners an interesting area that we will only touch in this course. There exist a multitude of other text books that overlap with one or two chapters of this + course, e.g., Lei92, Bar96, Lyn96, Tel01, AW04, HKP 05, CLRS09, Suo12. Another related course is by James Aspnes Asp and one by Jukka Suomela Suo14. Some chapters of this course have been developed in collaboration with (for- mer) Ph.D. students, see chapter notes for details. Many students have helped to improve exercises and script. Thanks go to Philipp Brandes, Raphael Ei- denbenz, Roland Flury, Klaus-Tycho F orster, Stephan Holzer, Barbara Keller, Fabian Kuhn, Christoph Lenzen, Thomas Locher, Remo Meier, Thomas Mosci- broda, Regina O'Dell, Yvonne-Anne Pignolet, Jochen Seidel, Stefan Schmid, Johannes Schneider, Jara Uitto, Pascal von Rickenbach (in alphabetical order). Bibliography Asp James Aspnes. Notes on Theory of Distributed Systems. AW04 Hagit Attiya and Jennifer Welch. Distributed Computing: Funda- mentals, Simulations and Advanced Topics (2nd edition). John Wi- ley Interscience, March 2004. Bar96 Valmir C. Barbosa. An introduction to distributed algorithms. MIT Press, Cambridge, MA, USA, 1996. CLRS09 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cli ord Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. + HKP 05 Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, and Walter Unger. Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault- Tolerance. Texts in Theoretical Computer Science. An EATCS Se- ries. Springer, 2005. Lei92 F. Thomson Leighton. Introduction to parallel algorithms and ar- chitectures: array, trees, hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992. Lyn96 Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Pub- lishers Inc., San Francisco, CA, USA, 1996. Pel00 David Peleg. Distributed Computing: a Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Suo12 Jukka Suomela. Deterministic Distributed Algorithms, 2012. Suo14 Jukka Suomela. Distributed algorithms. Online textbook, 2014.4 CONTENTS Tel01 Gerard Tel. Introduction to Distributed Algorithms. Cambridge Uni- versity Press, New York, NY, USA, 2nd edition, 2001.Chapter 1 Vertex Coloring Vertex coloring is an infamous graph theory problem. It is also a useful toy example to see the style of this course already in the rst lecture. Vertex coloring does have quite a few practical applications, for example in the area of wireless networks where coloring is the foundation of so-called TDMA MAC protocols. Generally speaking, vertex coloring is used as a means to break symmetries, one of the main themes in distributed computing. In this chapter we will not really talk about vertex coloring applications, but treat the problem abstractly. At the end of the class you probably learned the fastest algorithm ever Let us start with some simple de nitions and observations. 1.1 Problem & Model Problem 1.1 (Vertex Coloring). Given an undirected graphG = (V;E), assign a color c to each vertex v2 V such that the following holds: e = (v;w)2 v E) c 6=c . v w Remarks:  Throughout this course, we use the terms vertex and node interchange- ably.  The application often asks us to use few colors In a TDMA MAC pro- tocol, for example, less colors immediately imply higher throughput. However, in distributed computing we are often happy with a solution which is suboptimal. There is a tradeo between the optimality of a solution (ecacy), and the work/time needed to compute the solution (eciency). Assumption 1.3 (Node Identi ers). Each node has a unique identi er, e.g., its IP address. We usually assume that each identi er consists of only logn bits if the system has n nodes. 56 CHAPTER 1. VERTEX COLORING 1 2 3 3 Figure 1.2: 3-colorable graph with a valid coloring. Remarks:  Sometimes we might even assume that the nodes exactly have identi- ers 1;:::;n.  It is easy to see that node identi ers (as de ned in Assumption 1.3) solve the coloring problem 1.1, but usingn colors is not exciting. How many colors are needed is a well-studied problem: De nition 1.4 (Chromatic Number). Given an undirected Graph G = (V;E), the chromatic number (G) is the minimum number of colors to solve Problem 1.1. To get a better understanding of the vertex coloring problem, let us rst look at a simple non-distributed (\centralized") vertex coloring algorithm: Algorithm 1.5 Greedy Sequential 1: while there is an uncolored vertex v do 2: color v with the minimal color (number) that does not con ict with the already colored neighbors 3: end while De nition 1.6 (Degree). The number of neighbors of a vertex v, denoted by (v), is called the degree ofv. The maximum degree vertex in a graph G de nes the graph degree (G) = . Theorem 1.7. Algorithm 1.5 is correct and terminates in n \steps". The algorithm uses at most  + 1 colors. Proof: Since each node has at most  neighbors, there is always at least one color free in the rangef1;:::;  + 1g. Remarks:  In De nition 1.11 we will see what is meant by \step".  Sometimes (G)  + 1. De nition 1.8 (Synchronous Distributed Algorithm). In a synchronous dis- tributed algorithm, nodes operate in synchronous rounds. In each round, each node executes the following steps: 1. Send messages to neighbors in graph (of reasonable size).1.1. PROBLEM & MODEL 7 2. Receive messages (that were sent by neighbors in step 1 of the same round). 3. Do some local computation (of reasonable complexity). Remarks:  Any other step ordering is ne.  What does \reasonable" mean in this context? We are somewhat exible here, and di erent model variants exist. Generally, we will deal with algorithms that only do very simple computations (a com- parison, an addition, etc.). Exponential-time computation is usually considered cheating in this context. Similarly, sending a message with a node ID, or a value is considered okay, whereas sending really long messages is shy. We will have more exact de nitions later, when we need them.  We can build a distributed version of Algorithm 1.5: Algorithm 1.9 Reduce 1: Assume that initially all nodes have IDs 2: Each node v executes the following code: 3: node v sends its ID to all neighbors 4: node v receives IDs of neighbors 5: while node v has an uncolored neighbor with higher ID do 6: node v sends \undecided" to all neighbors 7: node v receives new decisions from neighbors 8: end while 9: node v chooses the smallest admissible free color 10: node v informs all its neighbors about its choice 1 3 1 3 100 2 5 5 Figure 1.10: Vertex 100 receives the lowest possible color. De nition 1.11 (Time Complexity). For synchronous algorithms (as de ned in 1.8) the time complexity is the number of rounds until the algorithm terminates. The algorithm terminates when the last node terminates. Theorem 1.12. Algorithm 1.9 is correct and has time complexity n. The al- gorithm uses at most  + 1 colors. Proof. Nodes choose colors that are di erent from their neighbors, and no two neighbors choose concurrently. In each round at least one node chooses a color, so we are done after at most n rounds.8 CHAPTER 1. VERTEX COLORING Remarks:  In the worst case, this algorithm is still not better than sequential.  Moreover, it seems dicult to come up with a fast algorithm.  Maybe it's better to rst study a simple special case, a tree, and then go from there. 1.2 Coloring Trees Lemma 1.13. (Tree) 2 Proof. Call some node the root of the tree. If the distance of a node to the root is odd (even), color it 1 (0). An odd node has only even neighbors and vice versa. Remarks:  If we assume that each node knows its parent (root has no parent) and children in a tree, this constructive proof gives a very simple algorithm: Algorithm 1.14 Slow Tree Coloring 1: Color the root 0, root sends 0 to its children 2: Each node v concurrently executes the following code: 3: if node v receives a message c (from parent) then p 4: node v chooses color c = 1c v p 5: node v sends c to its children (all neighbors except parent) v 6: end if Theorem 1.15. Algorithm 1.14 is correct. If each node knows its parent and its children, the time complexity is the tree height which is bounded by the diameter of the tree. Remarks:  How can we determine a root in a tree if it is not already given? We will gure that out later.  The time complexity of the algorithm is the height of the tree.  Nice trees, e.g., balanced binary trees, have logarithmic height, that is we have a logarithmic time complexity.  However, if the tree has a degenerated topology, the time complexity may again be up to n, the number of nodes.  This algorithm is not very exciting. Can we do better than logarith- mic?1.2. COLORING TREES 9 Here is the idea of the algorithm: We start with color labels that have logn bits. In each round we compute a new label with exponentially smaller size than the previous label, still guaranteeing to have a valid vertex coloring The algorithm  terminates in log n time. Log-Star? That's the number of logarithms (to the base 2) you need to take to get down to 2. Formally: De nition 1.16 (Log-Star).    8x 2 : log x := 1 8x 2 : log x := 1 + log (logx) Remarks:  Log-star is an amazingly slowly growing function. Log-star of all the 80 atoms in the observable universe (estimated to be 10 ) is 5. So log- star increases indeed very slowly There are functions which grow even more slowly, such as the inverse Ackermann function, however, the inverse Ackermann function of all the atoms is already 4. Algorithm 1.17 \6-Color" 1: Assume that initially the nodes have IDs of size logn bits 2: The root assigns itself the label 0 3: Each other node v executes the following code 4: send own color c to all children v 5: repeat 6: receive color c from parent p 7: interpret c and c as bit-strings v p 8: let i be the index of the smallest bit where c and c di er v p th 9: the new label is i (as bitstring) followed by the i bit of c v 10: send c to all children v 11: until c 2f0;:::; 5g for all nodes w w Example: Algorithm 1.17 executed on the following part of a tree: Grand-parent 0010110000 10010 . . . Parent 1010010000 01010 111 Child 0110010000 10001 001  Theorem 1.18. Algorithm 1.17 terminates in log n +k time, where k is a constant independent of n. Proof. We need to show that parent p and child c always have di erent colors. Initially, this is true, since all nodes start out with their unique ID. In a round, let i be the smallest index where child c has a di erent bit from parent p. If parent p di ers in a di erent index bit j =6 i from its own parent, parent and child will compute di erent colors in that round. On the other hand, if j = i, the symmetry is broken by p having a di erent bit at index i. Regarding runtime, note that the size of the largest color shrinks dramat- ically in each round, apart from the symmetry-breaking bit, exactly as a log- arithmic function. With some (tedious and boring) machinery, one can show10 CHAPTER 1. VERTEX COLORING  that indeed every node will have a color in the rangef0;:::; 5g in log n +k rounds. Remarks:  Let us have a closer look at the end game of the algorithm. Colors 11 (in binary notation, i.e., 6 or 7 in decimal notation) will not be chosen, because the node will then do another round. This gives a total of 6 colors (i.e., colors 0,. . . , 5).  What about that last line of the loop? How do the nodes know that all nodes now have a color in the rangef0;:::; 5g? The answer to this question is surprisingly complex. One may hardwire the number of rounds into the until statement, such that all nodes execute the loop for exactly the same number of rounds. However, in order to do so, all nodes need to know n, the number of nodes, which is ugly. There are (non-trivial) solutions where nodes do not need to know n, see exercises.  Can one reduce the number of colors? Note that Algorithm 1.9 does not work (since the degree of a node can be much higher than 6) For fewer colors we need to have siblings monochromatic Algorithm 1.19 Shift Down 1: Each other node v concurrently executes the following code: 2: Recolor v with the color of parent 3: Root chooses a new (di erent) color fromf0; 1; 2g Lemma 1.20. Algorithm 1.19 preserves coloring legality; also siblings are monochro- matic. Now Algorithm 1.9 can be used to reduce the number of used colors from 6 to 3. Algorithm 1.21 Six-2-Three 1: Each node v concurrently executes the following code: 2: for x = 5; 4; 3 do 3: Perform subroutine Shift down (Algorithm 1.19) 4: if c =x then v 5: choose the smallest admissible new color c 2f0; 1; 2g v 6: end if 7: end for Theorem 1.23. Algorithms 1.17 and 1.21 color a tree with three colors in time  O(log n).1.2. COLORING TREES 11 Figure 1.22: Possible execution of Algorithm 1.21. Remarks:  The termO() used in Theorem 1.18 is called \big O" and is often used in distributed computing. Roughly speaking,O(f) means \in the order of f, ignoring constant factors and smaller additive terms." More formally, for two functions f and g, it holds that f 2 O(g) if there are constants x and c so thatjf(x)j cjg(x)j for all x x . 0 0 For an elaborate discussion on the big O notation we refer to other introductory math or computer science classes, or Wikipedia.  A fast tree-coloring with only 2 colors is more than exponentially more expensive than coloring with 3 colors. In a tree degenerated to a list, nodes far away need to gure out whether they are an even or odd number of hops away from each other in order to get a 2-coloring. To do that one has to send a message to these nodes. This costs time linear in the number of nodes.  The idea of this algorithm can be generalized, e.g., to a ring topology. Also a general graph with constant degree  can be colored with   + 1 colors inO(log n) time. The idea is as follows: In each step, a node compares its label to each of its neighbors, constructing a12 CHAPTER 1. VERTEX COLORING logarithmic di erence-tag as in Algorithm 1.17. Then the new label is the concatenation of all the di erence-tags. For constant degree ,  this gives a 3-label inO(log n) steps. Algorithm 1.9 then reduces 3 the number of colors to +1 in 2 (this is still a constant for constant ) steps.  Unfortunately, coloring a general graph is not yet possible with this technique. We will see another technique for that in Chapter 7. With this technique it is possible to color a general graph with  + 1 colors inO(logn) time.  A lower bound shows that many of these log-star algorithms are asymptotically (up to constant factors) optimal. We will see that later. Chapter Notes The basic technique of the log-star algorithm is by Cole and Vishkin CV86. A  1 tight bound of log n was proven recently RS15. The technique can be gen- 2 eralized and extended, e.g., to a ring topology or to graphs with constant degree GP87, GPS88, KMW05. Using it as a subroutine, one can solve many problems in log-star time. For instance, one can color so-called growth bounded graphs (a model which includes many natural graph classes, for instance unit disk graphs)  asymptotically optimally inO(log n) time SW08. Actually, Schneider et al. show that many classic combinatorial problems beyond coloring can be solved in log-star time in growth bounded and other restricted graphs.  In a later chapter we learn a (log n) lower bound for coloring and related problems Lin92. Linial's paper also contains a number of other results on coloring, e.g., that any algorithm for coloring d-regular trees of radius r that p run in time at most 2r=3 require at least ( d) colors. For general graphs, later we will learn fast coloring algorithms that use a maximal independent sets as a base. Since coloring exhibits a trade-o between ecacy and eciency, many di erent results for general graphs exist, e.g., PS96, KSOS06, BE09, Kuh09, SW10, BE11b, KP11, BE11a, BEPS12, PS13, CPS14, BEK14. Some parts of this chapter are also discussed in Chapter 7 of Pel00, e.g., the proof of Theorem 1.18. Bibliography BE09 Leonid Barenboim and Michael Elkin. Distributed (delta+1)-coloring in linear (in delta) time. In 41st ACM Symposium On Theory of Computing (STOC), 2009. BE11a Leonid Barenboim and Michael Elkin. Combinatorial Algorithms for Distributed Graph Coloring. In 25th International Symposium on DIStributed Computing, 2011. BE11b Leonid Barenboim and Michael Elkin. Deterministic Distributed Ver- tex Coloring in Polylogarithmic Time. J. ACM, 58(5):23, 2011.BIBLIOGRAPHY 13 BEK14 Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (delta+1)-coloring in linear (in delta) time. SIAM J. Comput., 43(1):7295, 2014. BEPS12 Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schnei- der. The locality of distributed symmetry breaking. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 321330, 2012. CPS14 Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algo- rithms for the lov asz local lemma and graph coloring. In ACM Sym- posium on Principles of Distributed Computing, pages 134143, 2014. CV86 R. Cole and U. Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algo- rithms. In 18th annual ACM Symposium on Theory of Computing (STOC), 1986. GP87 Andrew V. Goldberg and Serge A. Plotkin. Parallel (+1)-coloring of constant-degree graphs. Inf. Process. Lett., 25(4):241245, June 1987. GPS88 Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon. Parallel Symmetry-Breaking in Sparse Graphs. SIAM J. Discrete Math., 1(4):434446, 1988. KMW05 Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. On the Locality of Bounded Growth. In 24th ACM Symposium on the Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA, July 2005. KP11 Kishore Kothapalli and Sriram V. Pemmaraju. Distributed graph coloring in a few rounds. In 30th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2011. KSOS06 Kishore Kothapalli, Christian Scheideler, Melih Onus, and Christian p Schindelhauer. Distributed coloring in O( logn) Bit Rounds. In 20th international conference on Parallel and Distributed Processing (IPDPS), 2006. Kuh09 Fabian Kuhn. Weak graph colorings: distributed algorithms and applications. In 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2009. Lin92 N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1)(1):193201, February 1992. Pel00 David Peleg. Distributed Computing: a Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. PS96 Alessandro Panconesi and Aravind Srinivasan. On the Complexity of Distributed Network Decomposition. J. Algorithms, 20(2):356374, 1996.14 CHAPTER 1. VERTEX COLORING PS13 Seth Pettie and Hsin-Hao Su. Fast distributed coloring algorithms for triangle-free graphs. In Automata, Languages, and Programming - 40th International Colloquium, ICALP, pages 681693, 2013. RS15 Joel Rybicki and Jukka Suomela. Exact bounds for distributed graph colouring. In Structural Information and Communication Complex- ity - 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, Post-Proceedings, pages 4660, 2015. SW08 Johannes Schneider and Roger Wattenhofer. A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs. In 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, August 2008. SW10 Johannes Schneider and Roger Wattenhofer. A New Technique For Distributed Symmetry Breaking. In 29th Symposium on Principles of Distributed Computing (PODC), Zurich, Switzerland, July 2010.

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.