简介
This book constitutes the refereed proceedings of the 23nd International Symposium on Distributed Computing, DISC 2009, held in Elche, Spain, in September 2009. The 33 revised full papers, selected from 121 submissions, are presented together with 15 brief announcements of ongoing works; all of them were carefully reviewed and selected for inclusion in the book. The papers address all aspects of distributed computing, and were organized in topical sections on Michel Raynal and Shmuel Zaks 60th birthday symposium, award nominees, transactional memory, shared memory, distributed and local graph algorithms, modeling issues, game theory, failure detectors, from theory to practice, graph algorithms and routing, consensus and byzantine agreement and radio networks.
目录
Title Page 1
Preface 4
Organization 6
Table of Contents 9
Michel Raynal and Shmuel Zaks 60th Birthday Symposium 9
The 2009 Edsger W. Dijkstra Prize in Distributed Computing 14
Computing, Observing, Controlling, Checkpointing: Symbiosis Is Even Better Than Agreement! 16
References 17
What Agreement Problems Owe Michel 18
Shmuel Zaks - The Early Years: A Combinatorialist in Distributed Computing 19
Shmuel Zaks - The Mathematician, Computer Scientist and Personality 20
References 20
Award Nominees (Session 2B) 9
The Disagreement Power of an Adversary 21
Introduction 21
Model and Definitions 23
Disagreement Power 24
The Conservative Back-Off Simulation (Sufficient Condition) 26
$k$-Set Agreement Protocol (Necessary Condition) 28
Equivalence Classes 31
Robustness against the Number of Processes 31
Simulating $k$ Processes with $k$-anti-$\\Omega$ 31
Concluding Remarks 33
References 34
New Bounds for the Controller Problem 35
Introduction 36
Background 36
Related Work 38
Our Contribution 39
Lower Bounds 40
The $\\Omega(N\\log\\frac{M}{W+1})$ Lower Bound 40
The $\\Omega(N {\\rm log} N)$ Lower Bound 41
An ($M,W$)-Controller 43
A Reduction from Trees to Paths 43
An $(M,M/2)$-Controller for a Path \u2014 Overview 45
References 46
On Set Consensus Numbers 48
Introduction 48
Model 50
Failure Patterns and Failure Detectors 50
Algorithms 50
Runs 50
Distributed Tasks 51
Weak Termination 51
Resilience and Active Resilience 51
Comparing Failure Detectors 52
The BG-Simulation Technique 52
The Main Result 53
Overview 53
Preliminaries 55
Main Result 56
Set Consensus Number: Categorizing Distributed Tasks 57
Related Work 57
In Place of Conclusion 58
References 59
The Abstract MAC Layer 61
Introduction 61
Model 63
System Components 63
Guarantees for the Abstract MAC Layer 65
Implementing an Abstract MAC Layer 67
Multiple Abstract MAC Layer Automata 67
Multi-Message Broadcast 68
Regionalized Networks 69
Leader Election 70
Regional Multi-Message Broadcast 72
Adapting RMMB for Mobile Networks 73
Conclusion 73
References 74
Randomization Can Be a Healer: Consensus with Dynamic Omission Failures 76
Introduction 76
Related Work 79
The $k$-Consensus Problem 80
SystemModel 80
The Algorithm 81
Correctness Proof 84
Performance 88
Conclusions 88
References 89
Transactional Memory (Session 1A) 10
Interrupting Snapshots and the Java^{TM} Size() Method 91
Introduction 91
Atomic Snapshots 92
Interrupting Snapshots in a Nutshell 92
Benefits of the New Algorithm 94
The Algorithm 95
Using the Size Object 99
Performance Evaluation 99
Benchmark I: Mixed Methods Per Thread 99
Benchmark II: Same Method Per Thread 101
Correctness Proof 102
Model 102
Sequential Specification 102
Proof of Wait-Free Progress 102
Linearizability Proof 103
References 105
Elastic Transactions 106
Introduction 106
System Model 108
Elastic Transactions: Definition 110
Implementation of Elastic Transactions 112
Evaluation 115
Abstraction 115
Extensibility 117
Experiments 118
Discussion and Related Work 118
Conclusion 119
References 120
Brief Announcement: Transactional Scheduling for Read-Dominated Workloads 121
References 122
Shared Memory (Session 1B) 10
Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus 124
Introduction 124
Model and Problem Definitions 125
$g$-Tight Group Renaming Implements g-Safe-Consensus 126
At Least $g$ + 1 Invocations Are Required to Implement Safe-Consensus 127
Safe-Consensus Implements Consensus 129
Consensus Using $O(2^{n})$ Safe-Consensus Tasks 129
Consensus Using $O(n^{2})$ Safe-Consensus Tasks 130
Safe Set-Consensus 132
(n,k)-Safe-Set-Consensus 132
Strong (n,k)-Safe-Set-Consensus 132
Conclusions 133
References 134
Appendix 135
Algorithm 1 Proof of Correctness 135
Algorithm 2 Proof of Correctness 135
Algorithm 3 Proof of Correctness 136
Algorithm 4 Proof of Correctness 136
Algorithm 5 Proof of Correctness 138
Algorithm 6 Proof of Correctness 138
The {\\sf RedBlue} Adaptive Universal Constructions 140
Introduction 140
Model 143
The {\\sf F-RedBlue} Algorithm 145
Modified Version of {\\sf F-RedBlue} That Uses Small Registers 148
Adaptive Universal Constructions for Large Objects 150
References 154
Help When Needed, But No More: Efficient Read/Write Partial Snapshot 155
Introduction 155
Context of the Study: Snapshot Objects 155
Content of the Paper and RelatedWork 157
Underlying Shared Memory Model 160
Definitions 160
Partial Snapshot Object 160
Additional Properties Related to the Implementation 161
An Efficient Partial Snapshot Construction 162
The Underlying Shared Objects 162
The {\\sf p snapshot()} Operation 163
The {\\sf Update()} Operation 164
Proof of the Algorithm 166
Using LL/SC Registers Instead of Read/Write Atomic Registers 167
Conclusion 167
References 168
Contention-Sensitive Data Structures and Algorithms 170
Introduction 170
Motivation 170
Contention-Sensitive Data Structures: The Basic Idea 171
A Simple Example: Contention-Sensitive Consensus 172
Summery of Contributions 172
RelatedWork 173
Defining Contention-Sensitive Data Structures 174
A Contention-Sensitive Double-Ended Queue Data Structure 176
Three Transformations 178
From Livelock-Freedom to Starvation-Freedom 178
From Obstruction-Freedom to Livelock-Freedom 179
From Prevention-Freedom to Livelock-Freedom 179
Generalizations 180
A Contention-Sensitive Election Algorithm 181
Discussion 182
References 183
Brief Announcement: Acceleration by Contention for Shared Memory Mutual Exclusion Algorithms 185
References 186
Brief Announcement: Incremental Component-Based Modeling, Verification, and Performance Evaluation of Distributed Reset 187
Motivation 187
Approach and Results 188
References 188
Distributed and Local Graph Algorithms (Session 1C) 10
Local Computation of Nearly Additive Spanners 189
Introduction 190
A Local Algorithm 192
Description of Algorithm {\\sc Local-Span} 192
Results 193
Analysis of Algorithm {\\sc Local-Span} 194
An Algorithm Based on Independent Dominating Sets 197
Definitions 197
Description of Algorithm {\\sc Dom-Span} 197
Analysis 198
An Improved Algorithm for $k$ = 3 199
References 201
A Local 2-Approximation Algorithm for the Vertex Cover Problem 204
Introduction 204
Preliminaries 205
Algorithm 207
Weighted Edge Packing 211
Weighted Vertex Cover 213
References 217
Distributed Discovery of Large Near-Cliques 219
Introduction 219
Definitions, Model, Results 222
Simple Approaches 223
Algorithm 225
Wrappers 228
Analysis 228
Complexity 228
Correctness 229
Summary 230
Discussion 231
References 232
Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality 234
Background and Results 234
Covering and Packing 237
Distributed Fractional Packing with $\\delta$ = 2 242
Distributed model for $\\delta$ = 2 242
Distributed Algorithm for $\\delta$ = 2 242
Distributed Fractional Packing with General $\\delta$ 245
Distributed Model for General $\\delta$ 245
Distributed Algorithm 245
Conclusions 248
References 248
Appendix 250
Brief Announcement: Decidable Graph Languages by Mediated Population Protocols 252
The GDM Model 252
References 253
Brief Announcement: Towards SecuredDistributed Polling in Social Network s 254
References 255
Modeling Issues (Session 1D) 11
What Can Be Observed Locally? 256
Introduction 256
Related Work 257
Outline of the Paper 258
Preliminaries: Description of Computation Models 259
Notation for Comparing the Power of Computational Models 261
Hierarchy of Quantum Models 262
Lower Time Bounds Based on Physical Locality ($\\varphi-\\mathcal{LOCAL}$) 265
Simple Problems in a Quantum Setting 267
Conclusions and Future Work 268
References 268
At-Most-Once Semantics in Asynchronous Shared Memory 271
Introduction 271
Model, Definitions, and Efficiency 274
Model and Adversary 274
At-Most-Once Problem, Effectiveness and Complexity 275
Lower Bound 276
Two Process Algorithms for At-Most-Once Problem 278
Algorithm \\text{{\\sc ao}}_{2,n} 278
Algorithm \\text{{\\sc ao}}^{'}_{2,n} 279
Effectiveness, Work and Space Complexity 279
Multiprocess Solution for the At-Most-Once problem 280
Conclusions 284
References 285
Nonblocking Algorithms and Backward Simulation 287
Introduction 287
Preliminaries 289
The Snark Algorithm 291
The Intermediate Automaton 294
Verification 295
Concluding Remarks 301
References 301
Brief Announcement: Efficient Model Checking of Fault-Tolerant Distributed Protocols Using Symmetry Reduction 302
References 303
Brief Announcement: Dynamic FTSS in Asynchronous Systems: The Case of Unison 304
References 305
Game Theory (Session 2A) 11
Dynamics in Network Interaction Games 307
Introduction 307
Related Work 309
Model and Notation 310
Sequential Dynamics 311
Concurrent Dynamics 313
Comparison of Convergence Times 316
Coordination Games 316
Anti-coordination Games 318
Conclusion 319
References 320
Brief Announcement: Cloud Computing Games: Pricing Services of Large Data Centers 322
References 323
Failure Detectors (Session 2C) 12
On the Existence ofWeakest Failure Detectors for Mutual Exclusion and $k$-Exclusion 324
Introduction 324
Explaining the Apparent Contradiction 325
RelatedWork 326
The Model 326
Implementing a Failure Detector 327
Comparing Failure Detectors 327
FCFS Mutual Exclusion Has NoWeakest Failure Detector 328
Definition of the Failure Detector $\\mathcal{D}_{k}$ 328
Proof of Property $P$3 329
Proof of Property $P$2 332
Proof of Property $P$1 333
Weakest Failure Detector for $k$-Exclusion 333
Definition of $\\Gamma^{k}$ 334
$\\Gamma^{k}$ Is Necessary 334
$\\Gamma^{k}$ Is Sufficient 336
References 337
Crash-Quiescent Failure Detection 339
Introduction 339
Definitions 341
Impossibility of Crash-Quiescent $\\Diamond\\mathcal{P}$ in $E_{CLPS}$ 343
Crash-Quiescent $\\Diamond\\mathcal{P}$ in $E_{CLPS}$ with Majority Correct 344
Proof of Correctness 345
Improving the Communication Bit Complexity 349
Communication Bit Complexity 352
Conclusion 352
References 353
The Price of Anonymity: Optimal Consensus Despite Asynchrony, Crash and Anonymity 354
Introduction 354
Computation Model 357
Base Model 357
The Failure Detector Class $\\psi$ 358
The Computation Model ${\\cal AARS}_{n,t}^{cl}[\\psi]$ 359
Solving Consensus in ${\\cal AARS}_{n,t}^{cl}[\\psi]$ 361
(2$t$ + 1) Is a Lower Bound 362
Early Decision and Halting 362
Early Decision 362
The System Model ${\\cal AARS}_{n,t}^{op}[\\psi]$ 363
An Early Deciding Algorithm for ${\\cal AARS}_{n,t}^{op}[\\psi]$ 363
From Consensus to $k$-Set Agreement 364
Solving $k$-Set Agreement in ${\\cal AARS}_{n,t}^{cl}[\\psi]$ with $t\\leq n-k$ 365
Solving the $k$-Set Agreement with Weaker Failure Detectors 365
Open Problems 366
References 366
Brief Announcement: On Implementing Omega Efficiently in the Crash-Recovery Model 369
Motivation 369
The Algorithm 369
References 370
Brief Announcement: The Minimum Failure Detector for Non-Local Tasks in Message-Passing Systems 371
References 372
Brief Announcement: Weak Synchrony Models and Failure Detectors for Message Passing ($k$-)Set Agreement 373
References 374
Graph Algorithms and Routing (Session 3B) 12
Brief Announcement Zab: A Practical Totally Ordered Broadcast Protocol 375
References 376
Compact Multicast Routing 377
Introduction 377
Preliminaries 379
Labeled Compact Multicast Routing 380
Name-Independent Compact Multicast Schemes 381
Balanced Name Independent Compact Multicast Routing for Growth Bounded Networks 383
Dynamic Compact Multicast Routing Schemes 385
Dynamic Compact Multicast Routing Schemes for Join-Only Events 386
Fully Dynamic Compact Multicast Routing Scheme 387
Conclusions 388
References 389
Building Blocks 389
Compact Routing in Power-Law Graphs 392
Introduction 392
Preliminaries 394
The Adapted Compact Routing Scheme 395
Analysis 397
Experiments 401
Conclusion 403
References 403
Virtual Ring Routing Trends 405
Introduction 405
Technical Approach 406
Contribution 407
Problem Description 408
Stretch Analysis 409
Simulation 414
Simulation Framework 414
Results 415
Conclusions 418
References 418
A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property 420
Introduction 420
Model and Notations 422
The Algorithm {\\sf LoopFreeMST} 424
High Level Description 424
Detailed Level Description 426
Complexity 432
Concluding Remarks 433
References 434
Euler Tour Lock-In Problem in the Rotor-Router Model 436
Introduction 437
Our Contribution and Outline of the Paper 437
The Euler Tour Lock-In Problem Revisited 438
Case Study of the Lock-In Problem 440
Border Cases 440
Almost Linear Lock-In
Case ${\\cal P}(\\mathit f){\\cal A}(\\circlearrowright)$ 442
The Two Remaining Cases 443
Further Work and Open Problems 447
References 448
Consensus and Byzantine Agreement (Session 3C) 13
Optimum Simultaneous Consensus for General Omissions Is Equivalent to an NP Oracle 449
Introduction 449
Model and Preliminary Definitions 452
Simultaneous Consensus and Common Knowledge 453
The CK Construction 455
Extensions and Conclusions 459
References 460
On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement 462
Introduction 462
Model 463
Motivation, Result, and Comparison 463
The Protocol 464
Overview 464
Correct-or-Detect Broadcast (CoD) 465
Proofs of Participation (PoP), Minority Case 467
Asynchronous Pre-Crash Consensus (PCC) 468
The Coin 471
The Final Protocol: Putting Things Together 472
Proofs of Participation (PoP), Majority Case 474
Observations 475
References 476
From Almost Everywhere to Everywhere: Byzantine Agreement with 藴O(n3/2) Bits 477
Introduction 477
Model 478
Problems 479
Results 479
Techniques 480
Related Work 481
The Almost Everywhere to Everywhere Universe Reduction Protocol 482
Proof of Correctness 485
Conclusion and Open Problems 488
References 488
Appendix: Sketch of Almost Everywhere Universe Reduction 489
Brief Announcement: A Leader-free Byzantine Consensus Algorithm 492
References 493
Radio Networks (Session 3D) 13
Efficient k-Shot Broadcasting in Radio Networks 494
Introduction 494
A k-Shot Broadcast Algorithm in Unknown Topology 497
A $k$-Shot Broadcast Algorithm for Small $k$ 497
A Fast $k$-Shot Broadcasting Protocol 500
Near-Optimal k-Shot Broadcasting in Known Topology 500
Partitions of a Set to Subsets in Base $k$ 501
A $k$-Shot Broadcast Schedule of Length $\\tilde{O}(k\\cdot\\sqrt[k]{\\max\\{|U|,\\sqrt{n}\\}})$ on bipartite graphs 502
The Composition Procedure 503
A $k$-Shot Broadcasting Schedule on Bipartite Graphs of Length $O(kn^{1/2k}\\log^{1+1/k} n)$ 504
Lower Bound 506
References 507
Keeping Mobile Robot Swarms Connected 509
Introduction 509
Preliminary Definitions 511
Distributed Connectivity Service 512
The Filtering Function 512
The Algorithm 513
Preserving Connectivity 514
Ensuring Progress for Graphs 515
Dependency Graphs 515
Ensuring Progress for Chains 517
Progress Function for Balanced and Separated Chains 518
Progress for Restricted Chains 518
Progress for Arbitrary Chains 519
Termination 520
Conclusion 522
References 523
Consensus and Mutual Exclusion in a Multiple Access Channel 525
Introduction 526
Infeasibility in the Weakest Model 530
Impact of Collision Detection 530
Availability of Collision Detection 530
Absence of Collision Detection 533
Global Clock 533
Known Number of Processes 535
From Consensus to Mutual Exclusion 535
Conclusion and Open Problems 537
References 538
Brief Announcement: Efficient Utilization of Multiple Interfaces in Wireless Ad Hoc Networks 540
References 541
Brief Announcement: The Speed of Broadcasting in Random Networks \u2013 Density Does Not Matter 542
Introduction 542
References 543
Author Index 544
Preface 4
Organization 6
Table of Contents 9
Michel Raynal and Shmuel Zaks 60th Birthday Symposium 9
The 2009 Edsger W. Dijkstra Prize in Distributed Computing 14
Computing, Observing, Controlling, Checkpointing: Symbiosis Is Even Better Than Agreement! 16
References 17
What Agreement Problems Owe Michel 18
Shmuel Zaks - The Early Years: A Combinatorialist in Distributed Computing 19
Shmuel Zaks - The Mathematician, Computer Scientist and Personality 20
References 20
Award Nominees (Session 2B) 9
The Disagreement Power of an Adversary 21
Introduction 21
Model and Definitions 23
Disagreement Power 24
The Conservative Back-Off Simulation (Sufficient Condition) 26
$k$-Set Agreement Protocol (Necessary Condition) 28
Equivalence Classes 31
Robustness against the Number of Processes 31
Simulating $k$ Processes with $k$-anti-$\\Omega$ 31
Concluding Remarks 33
References 34
New Bounds for the Controller Problem 35
Introduction 36
Background 36
Related Work 38
Our Contribution 39
Lower Bounds 40
The $\\Omega(N\\log\\frac{M}{W+1})$ Lower Bound 40
The $\\Omega(N {\\rm log} N)$ Lower Bound 41
An ($M,W$)-Controller 43
A Reduction from Trees to Paths 43
An $(M,M/2)$-Controller for a Path \u2014 Overview 45
References 46
On Set Consensus Numbers 48
Introduction 48
Model 50
Failure Patterns and Failure Detectors 50
Algorithms 50
Runs 50
Distributed Tasks 51
Weak Termination 51
Resilience and Active Resilience 51
Comparing Failure Detectors 52
The BG-Simulation Technique 52
The Main Result 53
Overview 53
Preliminaries 55
Main Result 56
Set Consensus Number: Categorizing Distributed Tasks 57
Related Work 57
In Place of Conclusion 58
References 59
The Abstract MAC Layer 61
Introduction 61
Model 63
System Components 63
Guarantees for the Abstract MAC Layer 65
Implementing an Abstract MAC Layer 67
Multiple Abstract MAC Layer Automata 67
Multi-Message Broadcast 68
Regionalized Networks 69
Leader Election 70
Regional Multi-Message Broadcast 72
Adapting RMMB for Mobile Networks 73
Conclusion 73
References 74
Randomization Can Be a Healer: Consensus with Dynamic Omission Failures 76
Introduction 76
Related Work 79
The $k$-Consensus Problem 80
SystemModel 80
The Algorithm 81
Correctness Proof 84
Performance 88
Conclusions 88
References 89
Transactional Memory (Session 1A) 10
Interrupting Snapshots and the Java^{TM} Size() Method 91
Introduction 91
Atomic Snapshots 92
Interrupting Snapshots in a Nutshell 92
Benefits of the New Algorithm 94
The Algorithm 95
Using the Size Object 99
Performance Evaluation 99
Benchmark I: Mixed Methods Per Thread 99
Benchmark II: Same Method Per Thread 101
Correctness Proof 102
Model 102
Sequential Specification 102
Proof of Wait-Free Progress 102
Linearizability Proof 103
References 105
Elastic Transactions 106
Introduction 106
System Model 108
Elastic Transactions: Definition 110
Implementation of Elastic Transactions 112
Evaluation 115
Abstraction 115
Extensibility 117
Experiments 118
Discussion and Related Work 118
Conclusion 119
References 120
Brief Announcement: Transactional Scheduling for Read-Dominated Workloads 121
References 122
Shared Memory (Session 1B) 10
Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus 124
Introduction 124
Model and Problem Definitions 125
$g$-Tight Group Renaming Implements g-Safe-Consensus 126
At Least $g$ + 1 Invocations Are Required to Implement Safe-Consensus 127
Safe-Consensus Implements Consensus 129
Consensus Using $O(2^{n})$ Safe-Consensus Tasks 129
Consensus Using $O(n^{2})$ Safe-Consensus Tasks 130
Safe Set-Consensus 132
(n,k)-Safe-Set-Consensus 132
Strong (n,k)-Safe-Set-Consensus 132
Conclusions 133
References 134
Appendix 135
Algorithm 1 Proof of Correctness 135
Algorithm 2 Proof of Correctness 135
Algorithm 3 Proof of Correctness 136
Algorithm 4 Proof of Correctness 136
Algorithm 5 Proof of Correctness 138
Algorithm 6 Proof of Correctness 138
The {\\sf RedBlue} Adaptive Universal Constructions 140
Introduction 140
Model 143
The {\\sf F-RedBlue} Algorithm 145
Modified Version of {\\sf F-RedBlue} That Uses Small Registers 148
Adaptive Universal Constructions for Large Objects 150
References 154
Help When Needed, But No More: Efficient Read/Write Partial Snapshot 155
Introduction 155
Context of the Study: Snapshot Objects 155
Content of the Paper and RelatedWork 157
Underlying Shared Memory Model 160
Definitions 160
Partial Snapshot Object 160
Additional Properties Related to the Implementation 161
An Efficient Partial Snapshot Construction 162
The Underlying Shared Objects 162
The {\\sf p snapshot()} Operation 163
The {\\sf Update()} Operation 164
Proof of the Algorithm 166
Using LL/SC Registers Instead of Read/Write Atomic Registers 167
Conclusion 167
References 168
Contention-Sensitive Data Structures and Algorithms 170
Introduction 170
Motivation 170
Contention-Sensitive Data Structures: The Basic Idea 171
A Simple Example: Contention-Sensitive Consensus 172
Summery of Contributions 172
RelatedWork 173
Defining Contention-Sensitive Data Structures 174
A Contention-Sensitive Double-Ended Queue Data Structure 176
Three Transformations 178
From Livelock-Freedom to Starvation-Freedom 178
From Obstruction-Freedom to Livelock-Freedom 179
From Prevention-Freedom to Livelock-Freedom 179
Generalizations 180
A Contention-Sensitive Election Algorithm 181
Discussion 182
References 183
Brief Announcement: Acceleration by Contention for Shared Memory Mutual Exclusion Algorithms 185
References 186
Brief Announcement: Incremental Component-Based Modeling, Verification, and Performance Evaluation of Distributed Reset 187
Motivation 187
Approach and Results 188
References 188
Distributed and Local Graph Algorithms (Session 1C) 10
Local Computation of Nearly Additive Spanners 189
Introduction 190
A Local Algorithm 192
Description of Algorithm {\\sc Local-Span} 192
Results 193
Analysis of Algorithm {\\sc Local-Span} 194
An Algorithm Based on Independent Dominating Sets 197
Definitions 197
Description of Algorithm {\\sc Dom-Span} 197
Analysis 198
An Improved Algorithm for $k$ = 3 199
References 201
A Local 2-Approximation Algorithm for the Vertex Cover Problem 204
Introduction 204
Preliminaries 205
Algorithm 207
Weighted Edge Packing 211
Weighted Vertex Cover 213
References 217
Distributed Discovery of Large Near-Cliques 219
Introduction 219
Definitions, Model, Results 222
Simple Approaches 223
Algorithm 225
Wrappers 228
Analysis 228
Complexity 228
Correctness 229
Summary 230
Discussion 231
References 232
Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality 234
Background and Results 234
Covering and Packing 237
Distributed Fractional Packing with $\\delta$ = 2 242
Distributed model for $\\delta$ = 2 242
Distributed Algorithm for $\\delta$ = 2 242
Distributed Fractional Packing with General $\\delta$ 245
Distributed Model for General $\\delta$ 245
Distributed Algorithm 245
Conclusions 248
References 248
Appendix 250
Brief Announcement: Decidable Graph Languages by Mediated Population Protocols 252
The GDM Model 252
References 253
Brief Announcement: Towards SecuredDistributed Polling in Social Network s 254
References 255
Modeling Issues (Session 1D) 11
What Can Be Observed Locally? 256
Introduction 256
Related Work 257
Outline of the Paper 258
Preliminaries: Description of Computation Models 259
Notation for Comparing the Power of Computational Models 261
Hierarchy of Quantum Models 262
Lower Time Bounds Based on Physical Locality ($\\varphi-\\mathcal{LOCAL}$) 265
Simple Problems in a Quantum Setting 267
Conclusions and Future Work 268
References 268
At-Most-Once Semantics in Asynchronous Shared Memory 271
Introduction 271
Model, Definitions, and Efficiency 274
Model and Adversary 274
At-Most-Once Problem, Effectiveness and Complexity 275
Lower Bound 276
Two Process Algorithms for At-Most-Once Problem 278
Algorithm \\text{{\\sc ao}}_{2,n} 278
Algorithm \\text{{\\sc ao}}^{'}_{2,n} 279
Effectiveness, Work and Space Complexity 279
Multiprocess Solution for the At-Most-Once problem 280
Conclusions 284
References 285
Nonblocking Algorithms and Backward Simulation 287
Introduction 287
Preliminaries 289
The Snark Algorithm 291
The Intermediate Automaton 294
Verification 295
Concluding Remarks 301
References 301
Brief Announcement: Efficient Model Checking of Fault-Tolerant Distributed Protocols Using Symmetry Reduction 302
References 303
Brief Announcement: Dynamic FTSS in Asynchronous Systems: The Case of Unison 304
References 305
Game Theory (Session 2A) 11
Dynamics in Network Interaction Games 307
Introduction 307
Related Work 309
Model and Notation 310
Sequential Dynamics 311
Concurrent Dynamics 313
Comparison of Convergence Times 316
Coordination Games 316
Anti-coordination Games 318
Conclusion 319
References 320
Brief Announcement: Cloud Computing Games: Pricing Services of Large Data Centers 322
References 323
Failure Detectors (Session 2C) 12
On the Existence ofWeakest Failure Detectors for Mutual Exclusion and $k$-Exclusion 324
Introduction 324
Explaining the Apparent Contradiction 325
RelatedWork 326
The Model 326
Implementing a Failure Detector 327
Comparing Failure Detectors 327
FCFS Mutual Exclusion Has NoWeakest Failure Detector 328
Definition of the Failure Detector $\\mathcal{D}_{k}$ 328
Proof of Property $P$3 329
Proof of Property $P$2 332
Proof of Property $P$1 333
Weakest Failure Detector for $k$-Exclusion 333
Definition of $\\Gamma^{k}$ 334
$\\Gamma^{k}$ Is Necessary 334
$\\Gamma^{k}$ Is Sufficient 336
References 337
Crash-Quiescent Failure Detection 339
Introduction 339
Definitions 341
Impossibility of Crash-Quiescent $\\Diamond\\mathcal{P}$ in $E_{CLPS}$ 343
Crash-Quiescent $\\Diamond\\mathcal{P}$ in $E_{CLPS}$ with Majority Correct 344
Proof of Correctness 345
Improving the Communication Bit Complexity 349
Communication Bit Complexity 352
Conclusion 352
References 353
The Price of Anonymity: Optimal Consensus Despite Asynchrony, Crash and Anonymity 354
Introduction 354
Computation Model 357
Base Model 357
The Failure Detector Class $\\psi$ 358
The Computation Model ${\\cal AARS}_{n,t}^{cl}[\\psi]$ 359
Solving Consensus in ${\\cal AARS}_{n,t}^{cl}[\\psi]$ 361
(2$t$ + 1) Is a Lower Bound 362
Early Decision and Halting 362
Early Decision 362
The System Model ${\\cal AARS}_{n,t}^{op}[\\psi]$ 363
An Early Deciding Algorithm for ${\\cal AARS}_{n,t}^{op}[\\psi]$ 363
From Consensus to $k$-Set Agreement 364
Solving $k$-Set Agreement in ${\\cal AARS}_{n,t}^{cl}[\\psi]$ with $t\\leq n-k$ 365
Solving the $k$-Set Agreement with Weaker Failure Detectors 365
Open Problems 366
References 366
Brief Announcement: On Implementing Omega Efficiently in the Crash-Recovery Model 369
Motivation 369
The Algorithm 369
References 370
Brief Announcement: The Minimum Failure Detector for Non-Local Tasks in Message-Passing Systems 371
References 372
Brief Announcement: Weak Synchrony Models and Failure Detectors for Message Passing ($k$-)Set Agreement 373
References 374
Graph Algorithms and Routing (Session 3B) 12
Brief Announcement Zab: A Practical Totally Ordered Broadcast Protocol 375
References 376
Compact Multicast Routing 377
Introduction 377
Preliminaries 379
Labeled Compact Multicast Routing 380
Name-Independent Compact Multicast Schemes 381
Balanced Name Independent Compact Multicast Routing for Growth Bounded Networks 383
Dynamic Compact Multicast Routing Schemes 385
Dynamic Compact Multicast Routing Schemes for Join-Only Events 386
Fully Dynamic Compact Multicast Routing Scheme 387
Conclusions 388
References 389
Building Blocks 389
Compact Routing in Power-Law Graphs 392
Introduction 392
Preliminaries 394
The Adapted Compact Routing Scheme 395
Analysis 397
Experiments 401
Conclusion 403
References 403
Virtual Ring Routing Trends 405
Introduction 405
Technical Approach 406
Contribution 407
Problem Description 408
Stretch Analysis 409
Simulation 414
Simulation Framework 414
Results 415
Conclusions 418
References 418
A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property 420
Introduction 420
Model and Notations 422
The Algorithm {\\sf LoopFreeMST} 424
High Level Description 424
Detailed Level Description 426
Complexity 432
Concluding Remarks 433
References 434
Euler Tour Lock-In Problem in the Rotor-Router Model 436
Introduction 437
Our Contribution and Outline of the Paper 437
The Euler Tour Lock-In Problem Revisited 438
Case Study of the Lock-In Problem 440
Border Cases 440
Almost Linear Lock-In
Case ${\\cal P}(\\mathit f){\\cal A}(\\circlearrowright)$ 442
The Two Remaining Cases 443
Further Work and Open Problems 447
References 448
Consensus and Byzantine Agreement (Session 3C) 13
Optimum Simultaneous Consensus for General Omissions Is Equivalent to an NP Oracle 449
Introduction 449
Model and Preliminary Definitions 452
Simultaneous Consensus and Common Knowledge 453
The CK Construction 455
Extensions and Conclusions 459
References 460
On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement 462
Introduction 462
Model 463
Motivation, Result, and Comparison 463
The Protocol 464
Overview 464
Correct-or-Detect Broadcast (CoD) 465
Proofs of Participation (PoP), Minority Case 467
Asynchronous Pre-Crash Consensus (PCC) 468
The Coin 471
The Final Protocol: Putting Things Together 472
Proofs of Participation (PoP), Majority Case 474
Observations 475
References 476
From Almost Everywhere to Everywhere: Byzantine Agreement with 藴O(n3/2) Bits 477
Introduction 477
Model 478
Problems 479
Results 479
Techniques 480
Related Work 481
The Almost Everywhere to Everywhere Universe Reduction Protocol 482
Proof of Correctness 485
Conclusion and Open Problems 488
References 488
Appendix: Sketch of Almost Everywhere Universe Reduction 489
Brief Announcement: A Leader-free Byzantine Consensus Algorithm 492
References 493
Radio Networks (Session 3D) 13
Efficient k-Shot Broadcasting in Radio Networks 494
Introduction 494
A k-Shot Broadcast Algorithm in Unknown Topology 497
A $k$-Shot Broadcast Algorithm for Small $k$ 497
A Fast $k$-Shot Broadcasting Protocol 500
Near-Optimal k-Shot Broadcasting in Known Topology 500
Partitions of a Set to Subsets in Base $k$ 501
A $k$-Shot Broadcast Schedule of Length $\\tilde{O}(k\\cdot\\sqrt[k]{\\max\\{|U|,\\sqrt{n}\\}})$ on bipartite graphs 502
The Composition Procedure 503
A $k$-Shot Broadcasting Schedule on Bipartite Graphs of Length $O(kn^{1/2k}\\log^{1+1/k} n)$ 504
Lower Bound 506
References 507
Keeping Mobile Robot Swarms Connected 509
Introduction 509
Preliminary Definitions 511
Distributed Connectivity Service 512
The Filtering Function 512
The Algorithm 513
Preserving Connectivity 514
Ensuring Progress for Graphs 515
Dependency Graphs 515
Ensuring Progress for Chains 517
Progress Function for Balanced and Separated Chains 518
Progress for Restricted Chains 518
Progress for Arbitrary Chains 519
Termination 520
Conclusion 522
References 523
Consensus and Mutual Exclusion in a Multiple Access Channel 525
Introduction 526
Infeasibility in the Weakest Model 530
Impact of Collision Detection 530
Availability of Collision Detection 530
Absence of Collision Detection 533
Global Clock 533
Known Number of Processes 535
From Consensus to Mutual Exclusion 535
Conclusion and Open Problems 537
References 538
Brief Announcement: Efficient Utilization of Multiple Interfaces in Wireless Ad Hoc Networks 540
References 541
Brief Announcement: The Speed of Broadcasting in Random Networks \u2013 Density Does Not Matter 542
Introduction 542
References 543
Author Index 544
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
