Preface	9
	Contents	11
	1 Introduction	14
	1.1 Motivation and Aims	14
	1.2 Organization of the Book	15
	Part I The Telegraph and Telephone Modes	18
	2 Fundamentals	20
	2.1 Introduction	20
	2.2 Graphs	20
	2.3 Combinatorics	33
	2.4 Communication Tasks and Algorithms	38
	2.5 General Properties of the Complexity of Communication Algorithms	46
	2.6 Fundamental Interconnection Networks	54
	3 Broadcasting	64
	3.1 Introduction	64
	3.2 Basic Facts and Techniques	65
	3.3 Upper Bounds for Common Networks	72
	3.4 Lower Bounds for Bounded-Degree Graphs	79
	3.5 Overview on Broadcasting in Concrete Networks	91
	3.6 Approximation Algorithms	92
	3.6.1 General Observations	93
	3.6.2 Two Approximation Algorithms	95
	3.6.3 Bibliographical Remarks	103
	4 Gossiping	106
	4.1 Introduction	106
	4.2 General Observations	107
	4.3 Gossiping in Graphs with Small Bisection Width	113
	4.4 Gossiping in Hypercube-like Networks of Constant Degree	136
	4.5 Gossiping in Complete Graphs	139
	4.6 Overview	147
	5 Systolic Communication	150
	5.1 Introduction	150
	5.2 Definitions	152
	5.3 Systolic Broadcast	156
	5.4 General Observations for Systolic Gossip	158
	5.5 Special Systolic Modes	160
	5.6 Systolic Gossip in Concrete Networks	161
	5.6.1 Systolic Gossip on a Path	162
	5.6.2 Systolic Gossip on a Cycle	174
	5.6.3 Systolic Gossip on Complete Trees	175
	5.6.4 Systolic Gossip on Grids	185
	5.6.5 Systolic Gossip on Butterfly and CCC Networks	188
	5.7 Bibliographical Remarks	193
	6 Fault-Tolerance	196
	6.1 Introduction	196
	6.1.1 Fault Distribution	197
	6.1.2 Fault Classi.cation	198
	6.1.3 Flexibility of Broadcasting Algorithms	199
	6.2 Preliminary Results	199
	6.3 The Bounded-Fault Model	203
	6.3.1 Permanent Link Faults	203
	6.3.2 Permanent Node Faults	206
	6.3.3 Transmission Faults	214
	6.4 The Probabilistic Fault Model	224
	6.4.1 Crash Faults	224
	6.4.2 Byzantine Faults	229
	Part II Distributed Networks	240
	7 Broadcast on Distributed Networks	242
	7.1 Broadcasting on General Networks	242
	7.1.1 Distributed Depth-First Search	242
	7.1.2 Distributed Breadth-First Search	248
	7.1.3 Basic Lower Bound on Message Complexity of Broadcast	253
	7.2 Broadcast on Tori	259
	7.2.1 Upper Bound	259
	7.2.2 Lower Bound	263
	7.2.3 The Growth of the Core Graph	266
	7.3 Broadcast on Hypercubes	270
	7.3.1 Preliminaries	270
	7.3.2 Partial Broadcasting and Orientation	272
	7.3.3 Bit-Efficient Partial Broadcasting Algorithm	274
	7.3.4 Applications – Optimal Computable Masks for Special	276
	7.3.5 The Broadcasting Algorithm	278
	7.3.6 Bit-Optimal Broadcasting in Time	279
	8 Leader Election in Asynchronous Distributed Networks	280
	8.1 Distributed Point-to-Point Network Model	280
	8.2 Leader Election on Distributed Networks	284
	8.3 Leader Election on Unidirectional Rings with Optimal Average Performance	284
	8.4 Leader Election on Unidirectional Rings – Worst Case Analysis	289
	8.5 Leader Election on Bidirectional Rings – Worst Case Analysis	296
	8.5.1 Election Algorithm Due to van Leeuwen and Tan	298
	8.5.2 Correctness and Message Complexity Analysis	300
	8.6 Leader Election on Complete Networks	303
	8.6.1 O(N logN) Algorithm	303
	8.6.2 .(N logN) Lower Bound	307
	8.7 Leader Election on Hypercubes	310
	8.7.1 Preliminary Notions	310
	8.7.2 Leader Election	311
	8.7.3 Warrior Phase	311
	8.7.4 King Phase	313
	8.8 Leader Election on Synchronous Rings	328
	9 Fault-Tolerant Broadcast in Distributed Networks	330
	9.1 Consensus Problem	330
	9.1.1 Fault-Tolerant Broadcast with Unsigned Messages	332
	9.1.2 Fault-Tolerant Broadcast with Signed Messages	336
	9.2 Broadcasting in Synchronous Networks with Dynamic Faults	339
	9.2.1 Broadcast in Hypercubes with Dynamic Faults	343
	9.2.2 Broadcast in Tori with Dynamic Faults	346
	9.2.3 Broadcast in Star Graphs with Dynamic Faults	350
	References	354
	Index	370
	More eBooks at www.ciando.com	0