Ravi / Shukla Fundamental Problems in Computing

Essays in Honor of Professor Daniel J. Rosenkrantz
1. Auflage 2009
ISBN: 978-1-4020-9688-4
Verlag: Springer Netherlands
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 516 Seiten

Not applicable for bookstore catalogue

Autoren/Hrsg.

Ravi, Sekharipuram S.

Shukla, Sandeep Kumar

Inhaltsverzeichnis

1;Foreword;6
2;Preface and Introduction;7
3;References;16
4;Selected Reprints from Professor Rosenkrantz's Seminal Contributions;21
4.1;Matrix Equations and Normal Forms for Context-Free Grammars;22
4.1.1;Preliminaries ;22
4.1.2;Systems of Equations ;23
4.1.3;Regular Expressions and the Closure of a Matrix ;24
4.1.4;Normal Form with Terminal Production Heads ;25
4.1.5;Normal Form with Terminal Heads and Tails ;28
4.1.6;References;29
4.2;Attributed Translations;30
4.2.1;Introduction ;30
4.2.2;Translation Grammars ;32
4.2.3;Attributed Translations ;33
4.2.4;Attributed Translation Grammars ;33
4.2.5;Examples ;36
4.2.6;Attributed Pushdown Machines ;43
4.2.7;Performing Translations Nondeterministically ;45
4.2.8;Performing Translations Deterministically ;51
4.2.9;Performing Arbitrary Translations ;57
4.2.10;Summary ;58
4.2.11;References;59
4.3;An analysis of several heuristics for the traveling salesman problem;60
4.3.1;Introduction ;61
4.3.2;Nearest Neighbor Algorithm ;62
4.3.3;Insertion Methods ;69
4.3.4;Nearest Insertion and Cheapest Insertion ;72
4.3.5;Farthest Insert ;77
4.3.6;Some Other Approximation Methods ;78
4.3.7;k-Optimality ;80
4.3.8;References;83
4.4;System Level Concurrency Control for Distributed Database Systems;84
4.4.1;Introduction ;85
4.4.2;Consistency ;87
4.4.3;Process Termination and Abortion ;88
4.4.4;Linearizing Concurrency Controls ;89
4.4.5;Conflicts ;90
4.4.6;Strict Concurrency Controls ;91
4.4.7;Responses to Conflicts ;94
4.4.8;Waiting Forever ;95
4.4.9;Fixed Order Concurrency Controls ;98
4.4.10;Restarting Forever ;100
4.4.11;The WAIT-DIE System ;101
4.4.12;The Wound-Wait System ;101
4.4.13;Comparison of WAIT-DIE and WOUND-WAIT Systems ;103
4.4.14;Centralized Concurrency Control ;104
4.4.15;Hybrid Concurrency Controls ;105
4.4.16;References;109
4.5;Consistency and serializability in concurrent database systems;111
4.5.1;Introduction ;112
4.5.2;Concurrency Control ;115
4.5.3;Databases ;116
4.5.4;Transactions ;116
4.5.5;Version Graphs ;118
4.5.6;Version Graph Analysis ;120
4.5.7;Datatraces ;123
4.5.8;Main Results ;126
4.5.9;Assuring Consistency ;127
4.5.10;The Converse Result ;129
4.5.11;The Read-Before-Write Assumption ;136
4.5.12;Time Assumptions ;138
4.5.13;Conclusion ;142
4.5.14;References;143
4.6;An efficient method for representing and transmitting message patterns on multiprocessor interconnection networks;145
4.6.1;Introduction ;146
4.6.2;The Omega Network ;149
4.6.3;Definition of a Mask Formalism ;151
4.6.4;Mask Normal Form ;153
4.6.5;Classes of Message Patterns Representable by (s,d)-Masks ;154
4.6.6;(s,d)-Masks and Detecting Congestion ;156
4.6.6.1;Detecting Conflicts in an (s,d)-Mask ;158
4.6.6.2;Detecting Congestion in an (s,d)-Mask ;162
4.6.7;Minimum Round Partitioning for (s,d)-Masks ;164
4.6.7.1;Minimum Round Partitioning for Non-Broadcast Omega Networks ;165
4.6.7.2;Minimum Round Partitioning for Broadcast Omega Networks ;169
4.6.8;Conclusion ;171
4.6.9;References;172
4.7;Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications;174
4.7.1;Introduction ;175
4.7.2;Basic Definitions and Concepts ;182
4.7.3;Expressive Power of the VDAG Model ;187
4.7.4;VDAG Construction ;191
4.7.5;Stamp Uniqueness Property and the Effect of Bounded Stamp Multiplicity ;198
4.7.6;Construction of Number Functions ;204
4.7.7;Handling Non-VDAG-Generable Forests ;207
4.7.8;Relative Conciseness of VDAG Model ;208
4.7.9;Automatic Simplification ;211
4.7.10;Conclusion ;216
4.7.11;References;217
4.8;The Complexity of Processing Hierarchical Specifications;219
4.8.1;Introduction ;220
4.8.2;Definitions and Terminology of Hierarchical Specifications ;222
4.8.3;Linear Space Simulation of Weakly Acyclic Circuits ;226
4.8.4;Acyclic Circuits: Lower Bounds ;231
4.8.5;2O(n) time Simulation of Acyclic Circuits ;236
4.8.6;Analysis Problems for Circuits with Cycles ;242
4.8.7;References;248
4.9;Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems;250
4.9.1;Introduction and Motivation ;251
4.9.2;Basic Definitions and Problem Formulations ;252
4.9.3;Summary of Results ;254
4.9.3.1;Hardness Results ;254
4.9.3.2;Approximation Algorithms ;254
4.9.4;Related Work ;255
4.9.5;Degree-Constrained Node-Weighted Steiner Trees ;256
4.9.5.1;High Level Description ;257
4.9.5.2;The Algorithm and Its Performance Guarantee ;257
4.9.5.3;A Procedure to Find Minimum Ratio Spiders ;257
4.9.5.4;Bounding the Total Degree of Deleted Nodes ;261
4.9.5.5;Spider Decompositions and an Averaging Lemma ;262
4.9.5.6;A Potential Function Argument ;264
4.9.5.7;Extension to Proper Function Cut Covers ;266
4.9.6;Algorithms Under Triangle Inequality ;266
4.9.6.1;Results for Spanning Trees ;267
4.9.6.2;Extension to Higher Connectivities ;268
4.9.7;Hardness Results ;270
4.9.7.1;Hardness Results for Spanning Tree Problems ;270
4.9.7.2;Hardness Results for Steiner Tree Problems ;271
4.9.8;Concluding Remarks ;272
4.9.9;References;274
4.10;Efficient Algorithms for Segmentation of Item-Set Time Series;276
4.10.1;Introduction ;277
4.10.2;Terminology and Definitions ;281
4.10.3;Computation of Segment Differences ;282
4.10.3.1;Segment Difference Computation for the Count Measure ;282
4.10.3.2;Segment Difference Computation for the Density Measure ;287
4.10.4;Optimal Segmentations ;290
4.10.5;Experiments ;292
4.10.5.1;Comparison of Optimal and Oblivious Segmentations ;292
4.10.5.2;Study of the Performance of Proposed Methods ;298
4.10.6;Related Work ;300
4.10.7;Conclusions ;301
4.10.8;References;303
5;Contributed Articles;306
5.1;Sums-of-Products and Subproblem Independence;307
5.1.1;Introduction ;307
5.1.2;Examples ;309
5.1.3;The Plus and Times Operators ;316
5.1.4;Quantified Sums ;319
5.1.5;Connection to Memory-Bounded Nondeterminism ;324
5.1.6;Measures of Independence ;329
5.1.7;Thank You Dan ;330
5.1.8;References;331
5.2;An Optimistic Concurrency Control Protocol for Replicated Databases;332
5.2.1;Introduction ;333
5.2.2;Related Work ;334
5.2.3;System Model ;336
5.2.4;Virtual Sites and Replication Graph ;340
5.2.4.1;Virtual Sites ;340
5.2.4.2;Replication Graph ;341
5.2.5;Commit-Oriented Protocol (COP) ;344
5.2.6;Implementation Issues ;348
5.2.6.1;Message Overhead ;348
5.2.6.2;Failures and Recovery ;350
5.2.7;Conclusions ;352
5.2.8;References;353
5.3;SNAPSHOT Isolation: Why Do Some People Call it SERIALIZABLE?;356
5.3.1;Introduction ;356
5.3.2;Correctness of Transaction Processing Systems ;357
5.3.3;Concurrency Controls, Two-Phase Locking, and Isolation Levels ;358
5.3.3.1;Isolation Levels ;359
5.3.4;SNAPSHOT Isolation ;359
5.3.4.1;Non-Serializable Execution at SNAPSHOT Isolation ;361
5.3.4.2;Non-Serializable but Correct Execution ;361
5.3.4.3;Phantoms at SNAPSHOT Isolation ;362
5.3.4.4;The Read-Only Anomaly ;363
5.3.5;A Sufficient Condition for Serializable Execution at SNAPSHOT Isolation ;363
5.3.6;The Infrastructure/State Design Pattern ;365
5.3.6.1;Automatic Constraint Checking ;366
5.3.6.2;The Disjoint-Predicate-Write Property ;367
5.3.6.3;Read-Only, Update-Only, and Read-Update Transactions ;367
5.3.6.4;State and Infrastructure Items and Transactions ;368
5.3.6.5;The Infrastructure/State Design Pattern ;369
5.3.7;Justification for the I/S Design Pattern ;371
5.3.7.1;State and Infrastructure Items and Transactions ;371
5.3.7.2;The Disjoint-Predicate-Write Property ;372
5.3.8;Conclusion ;373
5.3.9;Dedication ;374
5.3.10;References;375
5.4;A Richer Understanding of the Complexity of Election Systems;376
5.4.1;Introduction ;377
5.4.2;Elections and Election Systems: Preliminaries ;378
5.4.3;Complexity of Winning: Dodgson's 1876 Election System ;381
5.4.4;Complexity of Manipulation and Bribery: Scoring Systems and Dichotomy Theorems ;388
5.4.5;Complexity of Control: Making Someone Win or Keeping Someone From Winning ;396
5.4.6;Conclusions ;403
5.4.7;References;404
5.5;Fully Dynamic Bin Packing;408
5.5.1;Introduction ;409
5.5.1.1;Background-Off-Line and On-Line Bin Packing ;409
5.5.1.2;The Performance of Fully Dynamic Approximation Algorithms ;411
5.5.1.3;The Main Results ;412
5.5.2;Moving a Constant Number of Items Per Operation ;412
5.5.3;A 5/4-Competitive Algorithm for Fully Dynamic Bin Packing ;416
5.5.3.1;Some Definitions ;417
5.5.3.2;LLS-Maximality and M-Thoroughness ;419
5.5.3.3;MMP Insert and Delete operations-The Key Concepts ;421
5.5.3.4;Showing that MMP Is 54-Competitive ;425
5.5.3.5;The Running Time of MMP Is Theta(logn) ;425
5.5.4;Partially dynamic bin packing ;426
5.5.4.1;Uniform Algorithms for Partially Dynamic Bin Packing ;426
5.5.4.2;Amortized Algorithms for Partially Dynamic Bin Packing ;427
5.5.5;Conclusion ;431
5.5.5.1;Moving a Constant Number of Items Per Operation ;432
5.5.5.2;Fully Dynamic Bin Packing and MMP ;432
5.5.5.3;Partially Dynamic Bin Packing ;432
5.5.5.4;References;433
5.6;Online Job Admission;435
5.6.1;Introduction ;436
5.6.2;Problem Definition and Preliminaries ;438
5.6.2.1;Our Results ;438
5.6.2.2;Previous Work ;439
5.6.3;The Offline Problem ;440
5.6.4;Lower Bounds ;441
5.6.5;Competitive Algorithms ;447
5.6.5.1;A Greedy-Type Deterministic Algorithm ;447
5.6.5.2;An Algorithm Based on Classify and Randomly Select ;448
5.6.5.3;An Improved Deterministic Algorithm ;449
5.6.6;Conclusions ;452
5.6.7;References;453
5.7;A Survey of Graph Algorithms Under Extended Streaming Models of Computation;455
5.7.1;Introduction ;455
5.7.2;Lower Bounds ;457
5.7.2.1;Communication Complexity ;457
5.7.3;Semi-Streaming Model ;460
5.7.3.1;Spanners ;461
5.7.3.2;Sparsification ;462
5.7.4;W-Stream ;463
5.7.4.1;Connected Components in W-Stream ;464
5.7.4.2;Single-Source Shortest Paths ;465
5.7.5;The Stream-Sort Model ;468
5.7.5.1;Connected Components in Stream-Sort ;469
5.7.6;Summary and Conclusions ;473
5.7.7;Thank You Dan ;473
5.7.8;References;474
5.8;Interactions among human behavior, social networks, and societal infrastructures: A Case Study in Computational Epidemiology;476
5.8.1;Introduction ;477
5.8.2;The PIN Problem in Computational Epidemiology ;478
5.8.3;Network Based Computational Epidemiology ;480
5.8.3.1;SimDemics ;481
5.8.4;A Mathematical Model to Capture Co-Evolution ;483
5.8.4.1;Specifying PIN Problems in CE Using Co-Evolving Discrete Dynamical Systems ;485
5.8.5;Computational Experiments ;487
5.8.5.1;Basic Experimental Setup ;487
5.8.5.2;Experiment 1 ;488
5.8.5.3;Experiment 2 ;492
5.8.5.4;Comparing Adaptive and Non-Adaptive Strategies ;495
5.8.6;A Mathematical Formulation ;496
5.8.6.1;Preliminaries: A Simplified Model ;496
5.8.6.2;Policy Planning Problems ;497
5.8.6.3;Individual Behavior Problems: A Game Theoretic/ Dynamical Systems Viewpoint ;499
5.8.6.4;Discussion of the Different Formulations ;502
5.8.7;Concluding Remarks ;503
5.8.8;Thank You Dan ;503
5.8.9;References;504
6;Subject Index
;508