From Parallel to Emergent Computing

Cover......Page 1
Half Title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Contents......Page 6
Preface......Page 10
Editor Bios......Page 12
Contributors......Page 14
Editorial Boards of the International Journal of Parallel, Emergent and Distributed Systems......Page 20
Part 1: Networks and Parallel Computing......Page 22
1.1 Introduction......Page 24
1.2.1 Generating entanglement......Page 26
1.2.2 Distinguishing entangled states......Page 27
1.2.3 Generalization......Page 29
1.3 Quantum Bit Commitment......Page 30
1.3.1 BB84 quantum bit commitment......Page 31
1.3.2.1 Commit phase......Page 33
1.3.2.3 Unbinding entanglement......Page 34
1.4 Oblivious Transfer......Page 40
1.4.1 Protocol description......Page 41
1.4.2 Sequential approach: single-qubit measurements......Page 43
1.4.3 Attack strategy for Alice......Page 45
1.4.4 Attack strategy for Bob......Page 46
References......Page 49
2.1 Introduction......Page 52
2.2 Related Work......Page 53
2.3 Modeling a Multiserver System......Page 54
2.4.1 A Markov chain model......Page 56
2.4.2 Cost and performance metrics......Page 60
2.4.3 Numerical data......Page 62
2.5 Optimal Elasticity......Page 63
2.6 Summary......Page 67
References......Page 68
3.1 Introduction......Page 70
3.2 Related Works......Page 73
3.3.1 Studied environment......Page 76
3.3.2 Semi-Markov model and basic equations......Page 78
3.4.1 Evaluation methodology......Page 81
3.4.2.1 Scenario 1: “Home-to-Work”......Page 83
3.4.2.3 Scenario 3: “Going Out”......Page 86
3.4.2.4 Scenario 4: The Semi-Markov Protocol......Page 90
3.5 Conclusions......Page 92
Acknowledgment......Page 93
References......Page 94
4.1 Introduction......Page 98
4.2 Relation to Cyclic Connectivities......Page 100
4.3 Relation to Good-Neighbor Connectivities......Page 105
4.4 Relation to Restricted Connectivities and Component Connectivities......Page 112
4.5 Relation to Conditional Diagnosability and Matching Preclusions......Page 114
4.6 Relation to Menger Connectedness......Page 116
4.7 Conclusion......Page 120
References......Page 121
Part 2: Distributed Systems......Page 124
5.1 Introduction......Page 126
5.2 Model......Page 127
5.3.1 Data collection......Page 128
5.4 Results......Page 129
5.5 Conclusions......Page 134
References......Page 136
6.1.1 Biological pattern formation: an important problem of information processing......Page 138
6.1.2 Reservoir network structures – artificial neural networks studied under perturbation......Page 141
6.2.1 Reservoir network......Page 143
6.3.1 A reservoir computing model of development......Page 144
6.3.2 Perturbation of reservoir network mimics experimental results......Page 146
6.4 Discussion......Page 149
References......Page 151
7.1 A Primer to Classical versus Evolutionary Computation......Page 156
7.2.1 Symbolic regression in fault detection......Page 158
7.2.2 Swarm-based optimization in signal denoising......Page 161
7.2.3 Multi-objective optimization in power quality forecasting......Page 163
7.3.1 Social networks......Page 168
7.3.2.1 Differential evolution......Page 169
7.3.2.2 Differential evolution dynamics representation......Page 171
7.3.3 Short-interval networks......Page 172
7.3.4 Short-interval network based on the differential evolution dynamics......Page 173
7.3.5 Experiments......Page 174
7.3.5.1 Benchmark set and parameter settings......Page 175
7.3.5.2 Experimental results......Page 176
7.3.5.3 Discussion and conclusion......Page 177
7.4 Swarm Intelligence in Gamesourcing......Page 183
7.5 Artificial Neural Network Synthesis......Page 187
7.5.1 Symbolic regression in astrophysics......Page 190
References......Page 193
8.1 Introduction......Page 198
8.1.1 Motivation......Page 199
8.1.2 Design goals and contribution......Page 200
8.2.1 Domain partitioning......Page 201
8.2.2 Simulation data......Page 202
8.2.3 Load balancing......Page 203
8.2.4 Communication......Page 204
8.3.1 Structured subdomains......Page 206
8.3.2 Indexing......Page 207
8.3.3 Inter-primitive data exchange......Page 208
8.4.1 Discretisations......Page 210
8.4.2 Matrix-free approach......Page 211
8.4.3 Iterative solvers......Page 212
8.5.1 Stokes flow......Page 213
8.5.2 Energy transport......Page 214
8.6 Conclusion and Outlook......Page 215
References......Page 216
9.1 Introduction......Page 220
9.2.1 The basic idea......Page 221
9.2.3 Dynamics of the interactions among agents......Page 222
9.2.4 DRIMA in action......Page 224
9.2.4.2 Example 2: two deterministic agents......Page 225
9.3 DRIMA and BacDRIMA......Page 226
9.3.1 What bacteria, bees, ants, and athenians have in common......Page 228
9.3.2 A dilemma of prisoners and bacteria......Page 229
9.3.4 Movement and chemotaxis......Page 230
9.3.5 Reproduction......Page 231
9.4.1 Description......Page 232
9.4.2 Analysis......Page 233
9.4.2.1 Influence of mutation rate......Page 235
9.5 Discussion and Concluding Remarks......Page 238
References......Page 239
10.1 Introduction......Page 242
10.2 Soil-Filled Template to Make Crabs’ Burying Behaviour Ineffective......Page 243
10.3.1 Materials and methods......Page 244
10.3.2 Results and discussion......Page 246
10.4.1 Materials and methods......Page 248
10.4.2 Results and discussion......Page 251
10.5 General Discussion......Page 253
References......Page 258
11.1 Introduction......Page 260
11.2 Survey of Existing Works......Page 262
11.3 Hierarchical-Fitness-Based Evolving Benchmark Generator......Page 264
11.3.1 Statistical test......Page 265
11.3.2.1 Hierarchical fitness with U-test......Page 266
11.3.2.2 Hierarchical fitness with H-test......Page 269
11.3.2.3 Hierarchical-fitness comparison......Page 270
11.4.1 Experimental settings......Page 271
11.4.2 Composing a benchmark suite......Page 272
11.4.3 On CEC 2013 test suite......Page 274
11.4.4 Single-run search effort......Page 275
11.4.5 Enriching the training set of the algorithm selector......Page 276
11.5 Conclusion......Page 277
References......Page 278
12.1 Introduction......Page 282
12.2 Talmudic Hermeneutics and Qal Wa-H.omer......Page 283
12.3 Ant Roads and Qal Wa-H.omer......Page 287
12.4 Spatial Logic of Ant Propagation According to Qal Wa-H.omer......Page 292
References......Page 293
13.1 Introduction: Memory in Discrete Maps......Page 294
13.2 Biomorphs with Memory......Page 295
13.2.1 Algebraic transformations......Page 296
13.2.2 Partial memory......Page 298
13.2.3 Transcendental transformations......Page 299
13.2.5 Delay memory......Page 300
13.3 Conclusion and Future Work......Page 302
Acknowledgments......Page 303
References......Page 304
14.1.1 About tilings......Page 306
14.1.2 Signals in tilings......Page 307
14.2 A Star-Exponential in the Euclidean Plane......Page 308
14.3 About Hyperbolic Geometry......Page 314
14.3.2 A tiling of the hyperbolic plane: the tiling {7,3}......Page 315
14.3.3 Tiles generating a sector of the tiling {7,3}......Page 318
14.4.1 Constructing an exponential signal......Page 323
14.4.2 Tiling implementation......Page 325
14.5 Iterating the Exponential......Page 327
14.5.1 Signal for a *-exponential......Page 329
14.5.2 Tiles for a *-exponential......Page 330
14.6 Conclusion......Page 333
References......Page 334
Tilemachos Bontzorlos, Georgios Ch. Sirakoulis, and Franciszek Seredynski......Page 336
15.1.2 System architectures......Page 337
15.1.3 Swarm intelligence for area coverage......Page 339
15.2 Related Work......Page 340
15.2.1 Communication through a central system......Page 341
15.2.2 Direct communication......Page 342
15.2.4 Assisted communication......Page 343
15.3.1 Definition of the problem......Page 344
15.3.2.1 Deposition of pheromone......Page 345
15.3.2.2 Evaporation of pheromone......Page 348
15.3.3 Equipment and capabilities of the robots......Page 349
15.3.4 Swarm intelligence for area surveillance bio-inspired by ants......Page 350
15.4 Simulation Results......Page 351
15.4.1 Results for simulation space of size 25 × 25......Page 352
15.4.3 Space coverage approximation equations......Page 354
15.4.4 Comparison to other coverage strategies......Page 358
15.5 Conclusions......Page 360
References......Page 361
Part 3: Emergent Computing......Page 366
16.1 Introduction......Page 368
16.2.1 One-way functions......Page 370
16.2.2 Sorting with a twist......Page 372
16.2.3 Computational complexity as a function of time......Page 373
16.2.6 Variables that influence one another......Page 374
16.2.8 Working with a global variable......Page 375
16.3 Data Rearrangement......Page 377
16.4 Cyclic Shift......Page 378
16.5 Time Stamps......Page 379
16.6 Data Stream......Page 380
16.7 Unpredictable Data......Page 381
16.8 Setting the Elements of an Array......Page 382
16.10 Conclusion......Page 383
References......Page 385
17.1 Introduction......Page 388
17.1.1 Emergent patterns in the game of life......Page 389
17.2.2 Lossless compression......Page 391
17.2.3 Algorithmic probability and complexity......Page 392
17.2.4 Coding theorem and block decomposition methods......Page 394
17.3.1 Algorithmic probability of emergent patterns......Page 395
17.3.2 Algorithmic dynamics of evolving patterns......Page 397
Acknowledgements......Page 402
References......Page 403
18.1 Introduction......Page 406
18.2 Reservoir Computing Essentials......Page 407
18.3 Mathematical Primitives of Reservoir Computing......Page 408
18.4 The Computing Capacity of a Reservoir Computer......Page 410
18.5 A Landscape of Open Problems......Page 412
18.6 Terra Incognita of Practical Theorems......Page 415
18.7 Numerical Examples......Page 421
18.8 Conclusions......Page 423
References......Page 426
19.1 Introduction......Page 428
19.1.1 Central dogma of biology......Page 429
19.2 Structural DNA Nanotechnology......Page 430
19.2.1 DNA tiles and DNA origami......Page 432
19.3.1 DNA hybridization reactions......Page 433
19.3.4 DNA gates: duplex, seesaw, hairpin......Page 434
19.3.5 Leaks......Page 435
19.4 DNA Software......Page 436
19.6 DNA Computation......Page 437
19.7.2 Latest localized DNA computation demonstrations......Page 438
19.7.3 Localized cascade DNA hybridization reactions using DNA hairpin gates......Page 439
19.8 Summary and Future Outlook......Page 441
References......Page 442
20.1 Introduction......Page 446
20.2 Definitions......Page 447
20.3.1 The graph G1......Page 448
20.3.2 The graph G2......Page 449
20.3.3 The graph G3......Page 450
20.3.4 Decryption......Page 451
20.4 Cryptanalysis......Page 452
20.5 Applications......Page 453
20.5.1 Graphs in databases......Page 454
20.6.1 Implementation......Page 455
20.6.2.1 Encrypting the edges of each vertex separately......Page 456
20.6.2.3 Matrix confusion and diffusion......Page 457
20.6.2.5 The spider web......Page 458
20.7 Conclusion......Page 460
References......Page 461
21.1 Introduction......Page 464
21.2 Material Topology Optimisation......Page 465
21.2.1 Natural evolution method......Page 466
21.2.2 Specific parameters......Page 468
21.2.3.3 One-bit half-adder......Page 469
21.3 Natural Erosion of Sandstone......Page 472
21.3.1 Modelling of natural erosion......Page 474
21.3.2 Specific parameters......Page 476
21.3.3.1 and gate......Page 477
21.3.3.2 xor gate......Page 478
21.3.3.3 One-bit half-adder......Page 479
21.4 Heat Conduction......Page 480
21.4.1 Specific parameters......Page 483
21.4.2.2 xor gate......Page 488
Supplementary materials......Page 490
References......Page 491
22.1 Introduction......Page 496
22.2 Methods......Page 497
22.3.1 Numerical analysis......Page 498
22.3.2 Cluster analysis......Page 501
22.4 Discussion......Page 504
References......Page 506
23.1 Introduction......Page 510
23.2.1 Single-electron oscillator......Page 511
23.2.2 Single-electron box......Page 512
23.2.3 Single-electron memory......Page 513
23.3 Design of Nature-Inspired and Biomimetic Circuits......Page 514
23.4.1 Approach based on cellular automata model......Page 516
23.4.2 Approach based on slime-mold behaviors......Page 520
References......Page 526
24.1 Introduction: Different Modeling Approaches to Representing Natural Scenes......Page 530
24.2 Model Description......Page 537
24.2.3 V1 monocular surfaces......Page 538
24.2.4 V2 boundaries......Page 539
24.2.5 V2 monocular surfaces......Page 540
24.3.1 University of Tsukuba scene with ground truth......Page 542
24.3.2 Pentagon images......Page 544
24.3.3 Barn images......Page 545
24.4 Model Equations......Page 548
24.5 Discussion......Page 559
References......Page 562
25.1 Introduction......Page 568
25.2 Quadrupedal Locomotion......Page 570
25.3 Robot Prototype, Dynamic Simulation and CPG Model......Page 571
25.4 Motion Control of Each Leg......Page 576
25.5.1 Trot......Page 578
25.5.2 Canter......Page 582
25.5.3 Gallop......Page 584
25.6 Gait Transition......Page 586
25.7 Heading Control......Page 587
25.7.1 Straightforward path......Page 590
25.7.2 Piecewise linear path......Page 592
25.8 Conclusion......Page 593
References......Page 594
26.1 Introduction......Page 596
26.2.1 Why AF and MT, not DNA?......Page 597
26.3 Carriers of Information......Page 598
26.4 Collision-Based Computing......Page 599
26.5.1 Meso-scale memory via re-orientation of filaments bundles......Page 600
26.6.1 Optical I/O......Page 601
26.6.3.1 Millisecond time resolution......Page 602
26.7.1 MT assembly......Page 603
26.8.1 Cytoskeleton containing electronic components......Page 604
26.8.3 Logical inference machine......Page 605
References......Page 606
Index......Page 618