Peleg D. — Distributed Computing: A Locality-Sensitive Approach (Monographs on Discrete Mathematics and Applications) :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Peleg D. — Distributed Computing: A Locality-Sensitive Approach (Monographs on Discrete Mathematics and Applications)

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Distributed Computing: A Locality-Sensitive Approach (Monographs on Discrete Mathematics and Applications)

Автор: Peleg D.

Аннотация:

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.

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1987

Количество страниц: 359

Добавлена в каталог: 27.10.2010

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

      300
$D_{client}$       310
$D_{server}$       117
$S_{opt}$       208
$\hat{\varphi}$       88
$\lambda$       17
$\tilde{\varphi}$       86
$\varphi$       79
${Message}_{init}$       73
${Time}_{init}$       73
${Time}_{pulse}$       73
(s,r)-set      255—259
Acknowledgement      34—35 37
Adversary      8 26
Algorithm, $\mathfrak{k}$ - $\mathscr{Flood}$       271—272
Algorithm, $\mathscr{Asyn}$ _ $\mathscr{Cover}$       135—139 144 147—148 158 244
Algorithm, $\mathscr{Asyn}$ _ $\mathscr{Max}$ _ $\mathscr{Cover}$       253
Algorithm, $\mathscr{Av}$ _ $\mathscr{Str}$ _ $\mathscr{Tree}$       214—217
Algorithm, $\mathscr{Av}$ _ $\mathscr{{Part}_c}$       147 153
Algorithm, $\mathscr{Av}$ _ $\mathscr{{Part}_e}$       153—154 214 217
Algorithm, $\mathscr{Av}$ _ $\mathscr{{Part}_v}$       147—148
Algorithm, $\mathscr{Av}$ _ $\mathscr{{Part}_w}$       217
Algorithm, $\mathscr{Basic}$ _ $\mathscr{Part}$       129—130 133 177 212 233—238
Algorithm, $\mathscr{Controlled}$ -GHS      276—279
Algorithm, $\mathscr{Decomp}$       158—159
Algorithm, $\mathscr{Decomp}$ 2MIS      292—293
Algorithm, $\mathscr{Dist}$ _ $\mathscr{Decomp}$       257—258
Algorithm, $\mathscr{Dist}$ _ $\mathscr{Dijk}$       50—52 113 234 236
Algorithm, $\mathscr{Dist}$ _ $\mathscr{Part}$       233—238
Algorithm, $\mathscr{Dist}$ _ $\mathscr{Prim}$       56—58
Algorithm, $\mathscr{Dist}$ _BF      52—53
Algorithm, $\mathscr{Dist}$ _DFS      54—55 235 236
Algorithm, $\mathscr{Downcast}$       41
Algorithm, $\mathscr{Fast}$ -MST      275—280 286—287
Algorithm, $\mathscr{Flood}$       33—35 49 52 66 77 256 259 262—264
Algorithm, $\mathscr{Flood}$ & $\mathscr{Echo}$       35 39
Algorithm, $\mathscr{Greedy}$ _ $\mathscr{Span}$       197—199 205 238 272
Algorithm, $\mathscr{Greedy}$ _MIS      91
Algorithm, $\mathscr{Inter}$ _ $\mathscr{Label}$       229
Algorithm, $\mathscr{Light}$ _ $\mathscr{Span}$       199—204 263
Algorithm, $\mathscr{Max}$ _ $\mathscr{Cover}$       141—145 160 172 239 244
Algorithm, $\mathscr{Max}$ _ $\mathscr{{Part}_c}$       151—153
Algorithm, $\mathscr{Max}$ _ $\mathscr{{Part}_v}$       149—151 153
Algorithm, $\mathscr{Neig}$ _ $\mathscr{LabeL}$       222
Algorithm, $\mathscr{Ordered}$ _ $\mathscr{Upcast}$       43
Algorithm, $\mathscr{Rand}$ _MIS      97
Algorithm, $\mathscr{Ranked}$ _ $\mathscr{Upcast}$       42
Algorithm, $\mathscr{Reg}$ _ $\mathscr{Match}$       160—161
Algorithm, $\mathscr{Six}2\mathscr{Three}$       83
Algorithm, $\mathscr{Sync}$ _ $\mathscr{Av}$ _ $\mathscr{Cover}$       243—252
Algorithm, $\mathscr{Sync}$ _ $\mathscr{Max}$ _ $\mathscr{Cover}$       243 249—252
Algorithm, $\mathscr{Tcast}$       31—33 35 262 290
Algorithm, $\mathscr{Traveler}$       265—266
Algorithm, $\mathscr{Tree}$ _ $\mathscr{Cover}$       172—173 199 202 227
Algorithm, $\mathscr{Tree}$ _ $\mathscr{Embed}$       167—168
Algorithm, $\mathscr{Tree}$ _ $\mathscr{Label}$       224—226
Algorithm, $\mathscr{Unordered}$ _ $\mathscr{Upcast}$       43
Algorithm, $\mathscr{Unweighted}$ _ $\mathscr{Span}$       177—179
Algorithm, $\mathscr{Weighted}$ _ $\mathscr{Span}$       196—197 199 227
Algorithm, ${MIS}_{DFS}$       92—93 101
Algorithm, ${MIS}_{RANK}$       92—93 101
Algorithm, 6- $\mathscr{Color}$       81—84
Algorithm, event-driven      7
Algorithm, GHS      57—60 66 275—280 287
Algorithm, greedy      47 60—63 91—93 162 197—198
Algorithm, LQ      305—306
Algorithm, PRAM_MIS      101 293
Algorithm, randomized      89 97—102 162 239—243 253 266 272 287
Algorithm, SLT      192—194 205—206 238 263
Arboricity      223—230
Average stretch      10 207—220
BFS      32 49—57 66—68
Blue rule      56—58 66
Breadth-first search tree      32 66—68
Breadth-first search tree, distributed construction      49—53
Broadcast      31—40 261—272
Buffer      16 19 71 109
Buffer, inbound      301
Buffer, outbound      301
Child      18
Chromatic number      80
CLIQUE      183—187
Cluster      9 123—154
Cluster, cardinality-based      161—163
Cluster, cluster-neighborhood      127
Cluster, degree      128
Cluster, graph      127
Cluster, vertex degree      128
Cluster, vertex-neighborhood      127
Cluster, weak      132
Coarsening      131—132 135—155 160 162 171—173 180 199 200 212 239—253
Coloring, edge      88
Coloring, vertex      79—89
Communication cost      25
Complexity bound, existential      25
Complexity bound, global      25
Complexity, message      23 24
Complexity, space      22
Complexity, space, maximum      22
Complexity, space, total      22
Complexity, time      21
Complexity, time, asynchronous      22
Complexity, time, synchronous      22
Configuration      19
Configuration, initial      19
Convergecast      34—40 50 57 75 113 234—235 290
Correct simulation      69—70
Cover      123—129 135—145
Cover, $\rho$ -neighborhood      126 133 135 138 140 143 155 172 239 243 251 253
Cover, distributed, construction      239—253
Cover, distributed, construction, low communication      243—253
Cover, distributed, construction, randomized      239—243
Cover, hierarchy      155—157 163—164
Cover, hierarchy, refinement      155—156 312—314
Cycle radius      274 275
Deg      16
Degree, cover      127
Degree, cover, average      127
Degree, cover, maximum      127
Degree, cover, weighted      144
Degree, graph      167
Degree, graph, maximum      167
Degree, regional matching      160
Degree, tree cover, maximum      171
Depth, tree      17
Depth, tree cover      171
Depth-first search      49 54 229
Depth-first search, tree      54—55 66—68
DFS      49 54 229
Diameter, cluster      125
Diameter, cluster, weak      132
Diameter, ratio      205
Diameter, unweighted      17 274
Dilation, broadcast      261
Dilation, routing      107
Directory      113
Directory, hierarchical      306—309 312—316
Directory, hierarchical, refinement      312—314
Directory, regional      305—316
Distance      16—18
Distance, code      182
Distance, unweighted      16 126 217
Distributed match-making      118
Dominating set      95—96 182 276 277
downcast      41
Edge utilization      266—268 270
Enabling property      72
Event      19
Event, communication      19
Event, computation      19

execution      20
Execution, externally similar      268
Execution, legal      20
Execution, similar      70
External radius      274
flooding      33—34 39—40 49 52 66 77 256 259 262—264 271—272
Free bit      116
Function globally-sensitive      36
Function semigroup      36 38 113 114 117 119
girth      166
Graph      16—18
Graph, cartesian product      181
Graph, center      17
Graph, chordal      183—189 222 303
Graph, complete      23 205 209 272 286
Graph, grid      75 112 124 143 163 172 174 181 188 209 220 224 230 272 303
Graph, hypercube      112 180—183 187 188 224 230 292 315
Graph, line      87—88
Graph, planar      75 102 133 154 158 181 188 198 220 223 230 303
Graph, ring      52 53 75 85—89 93—94 102 108 112 181 209 224 230 272 303
Graph, split      183
Graph, universal      223—224 229—230
Graph, unweighted      16
Greedoid      61
Hamming code      182
Header, function      104
Header, initial      104
Header, initial function      104
Home-cluster      252
Home-tree      171
ID-assignment      15
Identifier      15
Independent maximum      91
Independent set      91
Independent set, matroid      60
Independent set, maximal      79 91—102
Independent set, maximal, decomposition based      292—294
Independent set, maximal, lexicographically first      91—92 101
Individual messages problem      28
Intercluster edges      127
ITR      228—230 295—304
J-usable server      309—310 314
Job scheduling      315
k-of- $\mathfrak{m}$ problem, largest      65
k-of- $\mathfrak{m}$ problem, smallest      44—45 65
k-server problem      219 317
Kernel      135
Key      62
Label, adjacency      222
Label, approximate-distance      227
Label, distance      224
Label, interval      229 295
Label, routing      103
Labeling scheme, adjacency      221—224
Labeling scheme, approximate-distance      227—228
Labeling scheme, distance      224—227
Labeling scheme, interval      228—230
Layer      18—19
Leader election      79
Local query      113—115 305—306
Local query, centralized      115
Local query, full updates      115
Local query, update-free      114
Mailing problem      280—287
Matching, global      118
Matching, regional      159—164 180 188 252 305—308 312 316
Matroid      61
Matroid, minimally dependent set      62
Matroid, optimization      60—68
Matroid, pipeline algorithm      62—68
Matroid, rank      61
Minimum total distance tree      169
Minimum-weight outgoing edge      56—60
Minimum-weight spanning tree      55—60 191—206 218—219 238 263
Minimum-weight spanning tree, distributed construction      55—68 273—287
Minimum-weight spanning tree, fragment      56—60 274—287
Minimum-weight spanning tree, fragment forest      59 276—279
MIS      79 91—102
Mobile tracking      315
Model, $\mathcal{ASYNC}$       27—29 69 77 289
Model, $\mathcal{CONGEST}$       27 243 275—276 280
Model, $\mathcal{CONGEST}$ asynchronous      49 57
Model, $\mathcal{CONGEST}$ synchronous      28 41 58 60 287
Model, $\mathcal{LOCAL}$       27—29 77 79 85 91 97 239 255 274—276 292
Model, anonymous      4 27 56 67 93 94 102 239 264
Model, asynchronous      6—7 69—77
Model, clean network      20 31 49 56 264
Model, comparison      267
Model, distributed      15—29
Model, known topology      264—272
Model, message-passing      2 15—16
Model, point-to-point      3 15—16
Model, PRAM      2
Model, shared memory      2
Model, synchronous      5 7 69—77
MST      49 55—60 191—206 218—219 238 262—263
Multigraph      15
name server      109 119 315
Neighbor update problem      74
Neighborhood      17—18
Neighborhood, code      182
Neighborhood, size-based      161—163
Neighborhood, unweighted      126 217
Network decomposition      157—159 163—164 180 253 292—294
Network decomposition, colored      257
Network decomposition, distributed construction      255—259
network design      317
Nondeterminism      6
Nonspannability      179 182 187 189
Operation $\mathscr{Find}$       116—119 306—314
Operation $\mathscr{Query}$       113—117 305—306
Operation $\mathscr{Update}$       114—115 117—119 307—316
Overlap, tree cover      171
Palette reduction      80—81
Partition      123—130 147—154
Partition, (s,r)      255
Partition, distributed construction      233—238
Partition, partial      138—145
Partition, separated      131 140—145
Pipeline      38—45 62—68 216 235—237
Pivot      155—162 312—316
Pivot, subordinate      155
Pivot, supervisor      156
Port      3 16
Port, function      104
Procedure $\mathscr{Cluster}$       244—251
Procedure $\mathscr{Cluster}$ _ $\mathscr{Cons}$       234 236—238 245
Procedure $\mathscr{Color}$ 2MIS      93
Procedure $\mathscr{Converge}$       34—40 50 57 75 113 234—235 290
Procedure $\mathscr{Dist}$ _ $\mathscr{Calc}$       224—226
Procedure $\mathscr{Dist}$ _ $\mathscr{Estimate}$       227—228
Procedure $\mathscr{First}$ _ $\mathscr{Free}$       80—84 258
Procedure $\mathscr{Graph}$ _ $\mathscr{Label}$       227
Procedure $\mathscr{Join}$       92
Procedure $\mathscr{Light}$ _TC      199—203
Procedure $\mathscr{Next}$ _ $\mathscr{Ctr}$       234—238
Procedure $\mathscr{Part}$       138—143 145 158
Procedure $\mathscr{Pipeline}$       63—68 276—279
Procedure $\mathscr{Pipeline}$ MST      66—68
Procedure $\mathscr{Rand}$ _ $\mathscr{Part}$       239—243
Procedure $\mathscr{RecurseColor}$       84—85 258
Procedure $\mathscr{Reduce}$       80—81 84 93
Procedure $\mathscr{Rep}$ _ $\mathscr{Edge}$       234—238
Procedure $\mathscr{Sep}$ _ $\mathscr{Part}$       140—141 143 158 159 239
Procedure $\mathscr{Sep}$ _ $\mathscr{Rule}$ _ $\mathscr{Part}$       255—256
Procedure $\mathscr{Shift}$ _ $\mathscr{Down}$       82—83
Procedure $\mathscr{Small}$ _ $\mathscr{Dom}$ _ $\mathscr{Set}$       95—96 276—278
Procedure $\mathscr{Sub}$ _ $\mathscr{Tree}$ _ $\mathscr{Label}$       224
Procedure $\mathscr{Sync}$ _ $\mathscr{Part}$       244—252
Procedure $\mathscr{Tour}$ _MST      192—199

1 2

О проекте