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
allowed applies approach arbitrary assume basic bits broadcast Chapter claim cluster coarsening collection coloring communication computation connecting Consider consists construction contains controller cost cover defined definition denote described discussed distance distributed algorithm edges efficient elements example execution Exercise exists fact Figure fragment function given graph G hence identifiers initial input integer iteration labels layer least Lemma locality lower bound measures memory message complexity namely neighbors Note operation optimal original parameter partial particular partition path performed phase possible presented problem Proc Procedure processor Proof properties protocol prove pulse radius received representations requires resource resulting root round routing scheme satisfies selected sends single spanner spanning tree Specifically step stored stretch structure subgraph Suppose synchronous Theorem tree unit unweighted update vertex vertices weight weighted graph