Distributed Computing: A Locality-Sensitive ApproachThis volume presents the locality-sensitive approach to distributed network algorithms-the utilization of locality to simplify control structures and algorithms and reduce their costs. The author begins with an introductory exposition of distributed network algorithms focusing on topics that illustrate the role of locality in distributed algorithmic techniques. He then introduces locality-preserving network representations and describes sequential and distributed techniques for their construction. Finally, the applicability of the locality-sensitive approach is demonstrated through several applications. Distributed Computing: A Locality-Sensitive Approach is the only book that gives a thorough exposition of network spanners and other locality-preserving network representations such as sparse covers and partitions. The book is useful for computer scientists interested in distributed computing, electrical engineers interested in network architectures and protocols, and for discrete mathematicians and graph theorists. |
Contents
DT05_ch1 | 1 |
DT05_ch2 | 15 |
DT05_ch3 | 31 |
DT05_ch4 | 41 |
DT05_ch5 | 49 |
DT05_ch6 | 69 |
DT05_ch7 | 79 |
DT05_ch8 | 91 |
DT05_ch16 | 177 |
DT05_ch17 | 191 |
DT05_ch18 | 207 |
DT05_ch19 | 221 |
DT05_ch20 | 233 |
DT05_ch21 | 239 |
DT05_ch22 | 255 |
DT05_ch23 | 261 |
DT05_ch9 | 103 |
DT05_ch10 | 113 |
DT05_ch11 | 123 |
DT05_ch12 | 135 |
DT05_ch13 | 147 |
DT05_ch14 | 155 |
DT05_ch15 | 165 |
DT05_ch24 | 273 |
DT05_ch25 | 289 |
DT05_ch26 | 295 |
DT05_ch27 | 305 |
DT05_ch28 | 317 |
DT05_backmatter | 319 |
Other editions - View all
Common terms and phrases
ACM Symp applies arbitrary asynchronous model average stretch Bellman-Ford algorithm BFS tree bits buffer Chapter chordal graphs cluster coarsening collection coloring communication complete graph Consider convergecast Corollary cost defined definition denote Depth(T described deterministic Diam(G discussed dist(u distance distributed algorithm Distributed Computing efficient execution exists Figure fragment given global graph G greedy algorithm hence hypercube identifiers induced subgraph input integer intercluster edges iteration layer Lemma logn lower bound matroid maximal independent set maximum memory requirements message complexity n-vertex graph neighborhoods neighbors network G Note number of edges O(log optimal output p-regional matching parameter partial partition Peleg phase planar graphs polylogarithmic problem Proc Procedure processor Proof properties protocol prove pulse queries radius representations resource unit resulting root routing scheme Section shortest path spanner spanning tree sparse stored structure subgraph synchronizer topology trade-off tree cover unweighted upcast update vertex vertices weighted graph