Fundamental Problems in Computing (eBook)

Foreword 6
Preface and Introduction 7
References 16
Selected Reprints from Professor Rosenkrantz's Seminal Contributions 21
Matrix Equations and Normal Forms for Context-Free Grammars 22
Preliminaries 22
Systems of Equations 23
Regular Expressions and the Closure of a Matrix 24
Normal Form with Terminal Production Heads 25
Normal Form with Terminal Heads and Tails 28
References 29
Attributed Translations 30
Introduction 30
Translation Grammars 32
Attributed Translations 33
Attributed Translation Grammars 33
Examples 36
Attributed Pushdown Machines 43
Performing Translations Nondeterministically 45
Performing Translations Deterministically 51
Performing Arbitrary Translations 57
Summary 58
References 59
An analysis of several heuristics for the traveling salesman problem 60
Introduction 61
Nearest Neighbor Algorithm 62
Insertion Methods 69
Nearest Insertion and Cheapest Insertion 72
Farthest Insert 77
Some Other Approximation Methods 78
k-Optimality 80
References 83
System Level Concurrency Control for Distributed Database Systems 84
Introduction 85
Consistency 87
Process Termination and Abortion 88
Linearizing Concurrency Controls 89
Conflicts 90
Strict Concurrency Controls 91
Responses to Conflicts 94
Waiting Forever 95
Fixed Order Concurrency Controls 98
Restarting Forever 100
The WAIT-DIE System 101
The Wound-Wait System 101
Comparison of WAIT-DIE and WOUND-WAIT Systems 103
Centralized Concurrency Control 104
Hybrid Concurrency Controls 105
References 109
Consistency and serializability in concurrent database systems 111
Introduction 112
Concurrency Control 115
Databases 116
Transactions 116
Version Graphs 118
Version Graph Analysis 120
Datatraces 123
Main Results 126
Assuring Consistency 127
The Converse Result 129
The Read-Before-Write Assumption 136
Time Assumptions 138
Conclusion 142
References 143
An efficient method for representing and transmitting message patterns on multiprocessor interconnection networks 145
Introduction 146
The Omega Network 149
Definition of a Mask Formalism 151
Mask Normal Form 153
Classes of Message Patterns Representable by (s,d)-Masks 154
(s,d)-Masks and Detecting Congestion 156
Detecting Conflicts in an (s,d)-Mask 158
Detecting Congestion in an (s,d)-Mask 162
Minimum Round Partitioning for (s,d)-Masks 164
Minimum Round Partitioning for Non-Broadcast Omega Networks 165
Minimum Round Partitioning for Broadcast Omega Networks 169
Conclusion 171
References 172
Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications 174
Introduction 175
Basic Definitions and Concepts 182
Expressive Power of the VDAG Model 187
VDAG Construction 191
Stamp Uniqueness Property and the Effect of Bounded Stamp Multiplicity 198
Construction of Number Functions 204
Handling Non-VDAG-Generable Forests 207
Relative Conciseness of VDAG Model 208
Automatic Simplification 211
Conclusion 216
References 217
The Complexity of Processing Hierarchical Specifications 219
Introduction 220
Definitions and Terminology of Hierarchical Specifications 222
Linear Space Simulation of Weakly Acyclic Circuits 226
Acyclic Circuits: Lower Bounds 231
2O(n) time Simulation of Acyclic Circuits 236
Analysis Problems for Circuits with Cycles 242
References 248
Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems 250
Introduction and Motivation 251
Basic Definitions and Problem Formulations 252
Summary of Results 254
Hardness Results 254
Approximation Algorithms 254
Related Work 255
Degree-Constrained Node-Weighted Steiner Trees 256
High Level Description 257
The Algorithm and Its Performance Guarantee 257
A Procedure to Find Minimum Ratio Spiders 257
Bounding the Total Degree of Deleted Nodes 261
Spider Decompositions and an Averaging Lemma 262
A Potential Function Argument 264
Extension to Proper Function Cut Covers 266
Algorithms Under Triangle Inequality 266
Results for Spanning Trees 267
Extension to Higher Connectivities 268
Hardness Results 270
Hardness Results for Spanning Tree Problems 270
Hardness Results for Steiner Tree Problems 271
Concluding Remarks 272
References 274
Efficient Algorithms for Segmentation of Item-Set Time Series 276
Introduction 277
Terminology and Definitions 281
Computation of Segment Differences 282
Segment Difference Computation for the Count Measure 282
Segment Difference Computation for the Density Measure 287
Optimal Segmentations 290
Experiments 292
Comparison of Optimal and Oblivious Segmentations 292
Study of the Performance of Proposed Methods 298
Related Work 300
Conclusions 301
References 303
Contributed Articles 306
Sums-of-Products and Subproblem Independence 307
Introduction 307
Examples 309
The Plus and Times Operators 316
Quantified Sums 319
Connection to Memory-Bounded Nondeterminism 324
Measures of Independence 329
Thank You Dan 330
References 331
An Optimistic Concurrency Control Protocol for Replicated Databases 332
Introduction 333
Related Work 334
System Model 336
Virtual Sites and Replication Graph 340
Virtual Sites 340
Replication Graph 341
Commit-Oriented Protocol (COP) 344
Implementation Issues 348
Message Overhead 348
Failures and Recovery 350
Conclusions 352
References 353
SNAPSHOT Isolation: Why Do Some People Call it SERIALIZABLE? 356
Introduction 356
Correctness of Transaction Processing Systems 357
Concurrency Controls, Two-Phase Locking, and Isolation Levels 358
Isolation Levels 359
SNAPSHOT Isolation 359
Non-Serializable Execution at SNAPSHOT Isolation 361
Non-Serializable but Correct Execution 361
Phantoms at SNAPSHOT Isolation 362
The Read-Only Anomaly 363
A Sufficient Condition for Serializable Execution at SNAPSHOT Isolation 363
The Infrastructure/State Design Pattern 365
Automatic Constraint Checking 366
The Disjoint-Predicate-Write Property 367
Read-Only, Update-Only, and Read-Update Transactions 367
State and Infrastructure Items and Transactions 368
The Infrastructure/State Design Pattern 369
Justification for the I/S Design Pattern 371
State and Infrastructure Items and Transactions 371
The Disjoint-Predicate-Write Property 372
Conclusion 373
Dedication 374
References 375
A Richer Understanding of the Complexity of Election Systems 376
Introduction 377
Elections and Election Systems: Preliminaries 378
Complexity of Winning: Dodgson's 1876 Election System 381
Complexity of Manipulation and Bribery: Scoring Systems and Dichotomy Theorems 388
Complexity of Control: Making Someone Win or Keeping Someone From Winning 396
Conclusions 403
References 404
Fully Dynamic Bin Packing 408
Introduction 409
Background-Off-Line and On-Line Bin Packing 409
The Performance of Fully Dynamic Approximation Algorithms 411
The Main Results 412
Moving a Constant Number of Items Per Operation 412
A 5/4-Competitive Algorithm for Fully Dynamic Bin Packing 416
Some Definitions 417
LLS-Maximality and M-Thoroughness 419
MMP Insert and Delete operations-The Key Concepts 421
Showing that MMP Is 54-Competitive 425
The Running Time of MMP Is Theta(logn) 425
Partially dynamic bin packing 426
Uniform Algorithms for Partially Dynamic Bin Packing 426
Amortized Algorithms for Partially Dynamic Bin Packing 427
Conclusion 431
Moving a Constant Number of Items Per Operation 432
Fully Dynamic Bin Packing and MMP 432
Partially Dynamic Bin Packing 432
References 433
Online Job Admission 435
Introduction 436
Problem Definition and Preliminaries 438
Our Results 438
Previous Work 439
The Offline Problem 440
Lower Bounds 441
Competitive Algorithms 447
A Greedy-Type Deterministic Algorithm 447
An Algorithm Based on Classify and Randomly Select 448
An Improved Deterministic Algorithm 449
Conclusions 452
References 453
A Survey of Graph Algorithms Under Extended Streaming Models of Computation 455
Introduction 455
Lower Bounds 457
Communication Complexity 457
Semi-Streaming Model 460
Spanners 461
Sparsification 462
W-Stream 463
Connected Components in W-Stream 464
Single-Source Shortest Paths 465
The Stream-Sort Model 468
Connected Components in Stream-Sort 469
Summary and Conclusions 473
Thank You Dan 473
References 474
Interactions among human behavior, social networks, and societal infrastructures: A Case Study in Computational Epidemiology 476
Introduction 477
The PIN Problem in Computational Epidemiology 478
Network Based Computational Epidemiology 480
SimDemics 481
A Mathematical Model to Capture Co-Evolution 483
Specifying PIN Problems in CE Using Co-Evolving Discrete Dynamical Systems 485
Computational Experiments 487
Basic Experimental Setup 487
Experiment 1 488
Experiment 2 492
Comparing Adaptive and Non-Adaptive Strategies 495
A Mathematical Formulation 496
Preliminaries: A Simplified Model 496
Policy Planning Problems 497
Individual Behavior Problems: A Game Theoretic/ Dynamical Systems Viewpoint 499
Discussion of the Different Formulations 502
Concluding Remarks 503
Thank You Dan 503
References 504
Subject Index 
508