Asynchronous Consensus Impossibility
- PDF / 214,120 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 82 Downloads / 200 Views
A
Asynchronous Consensus Impossibility
easy to update all the slack values in O(n) time since all of them change by the same amount (the labels of the vertices in S are going down uniformly). Whenever a node u is moved from S to S one must recompute the slacks of the nodes in T, requiring O(n) time. But a node can be moved from S to S at most n times. Thus each phase can be implemented in O(n2 ) time. Since there are n phases, this gives a running time of O(n3 ). For sparse graphs, there is a way to implement the algorithm in O(n(m + n log n)) time using min cost flows [1], where m is the number of edges. Applications There are numerous applications of biparitite matching, for example, scheduling unit-length jobs with integer release times and deadlines, even with time-dependent penalties. Open Problems Obtaining a linear, or close to linear, time algorithm. Assignment Problem, Figure 1 Sets S and T as maintained by the algorithm
the size of the matching increases by 1). Within each phase the size of the Hungarian tree is increased at most n times. It is clear that in O(n2 ) time one can figure out which edge from S to T is the first to enter the equality subgraph (one simply scans all the edges). This yields an O(n4 ) bound on the total running time. How to implement it in O(n3 ) time is now shown. More Efficient Implementation Define the slack of an edge as follows: slack(x; y) = `(x) + `(y) w(x; y) :
Recommended Reading Several books on combinatorial optimization describe algorithms for weighted bipartite matching (see [2,5]). See also Gabow’s paper [3]. 1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993) 2. Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998) 3. Gabow, H.: Data structures for weighted matching and nearest common ancestors with linking. In: Symp. on Discrete Algorithms, 1990, pp. 434–443 4. Kuhn, H.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2, 83–97 (1955) 5. Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston (1976) 6. Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5, 32–38 (1957)
Then = min slack(x; y) : x2S;y2T
Naively, the calculation of requires O(n2 ) time. For every vertex y 2 T, keep track of the edge with the smallest slack, i. e., slack[y] = min slack(x; y) :
Asynchronous Consensus Impossibility 1985; Fischer, Lynch, Paterson MAURICE HERLIHY Department of Computer Science, Brown University, Providence, RI, USA
x2S
The computation of slack[y] (for all y 2 T) requires O(n2 ) time at the start of a phase. As the phase progresses, it is
Keywords and Synonyms Wait-free consensus; Agreement
Asynchronous Consensus Impossibility
Problem Definition Consider a distributed system consisting of a set of processes that communicate by sending and receiving messages. The network is a multiset of messages, where each message is addressed
Data Loading...
