by Marius-Calin SilaghiKeywords: Distributed Constraint Satisfaction (DisCSP/DCSP), Distributed Constraint Reasoning, Negotiations, Auctions, Generalized English Auctions. Security, Continuous and Numerical CSP techniques for Nonlinear (In)Equations, Optimization
PhD Thesis at the Swiss Federal Institute of Technology at Lausanne
(EPFL)
June 27, 2002
Referees: Christian Bessiere, Boi V. Faltings, Karl
Aberer, Makoto Yokoo
Jury: Martin Oderski, Rachid Gerraoui
Abstract iii
Foreword vii
Acknowledgements ix
1 Introduction 1
Part I Background and Preliminaries 9
2 Constraint Satisfaction 11Part II Asynchronous Algorithms 57
3 Parallel and Distributed Search 23
4 Asynchronous Search 33
5 Dual, Primal, and Full approach 39
6 Nogood elimination in asynchronous search 59Part III Advanced Issues about DisCSP 157
7 Asynchronous Maintaining Consistency 65
8 Conflict Resources 77
9 Asynchronous Aggregation Search 87
10 Polynomial Space Asynchronous Dynamic Reordering 101
11 Asynchronous Reordering Heuristics 113
12 Multiply Asynchronous Search 121
13 Replicas-based Distributed CSPs 129
14 Optimization 135
15 Privacy with Cryptographic Protocols 141
16 Privacy enforcing Protocols 147
17 Generalized English Auctions --- Secure Verification of Conflicts 159Annexes 201
18 Distributed Generative Constraint Satisfaction 175
19 Openness in Complete Asynchronous Search 183
20 Distributed Systems Issues 191
Contributions and Conclusions 197
A Problem Solving 203If you remark a bug or an error, you can write me at (and your contribution will be acknowledged): marius.silaghi@cs.fit.edu.
B Problems with a secure test operator 225
C Properties of General English Auctions 233
D Centralized Aggregation 239
References 259
Curriculum Vitae 271
Corrected error | Date | Who remarked the error: |
1: Forgotten indexes added to the variables in the definition of gconsistent in chapter 15. | July, 25th, 2002 | myself |
2: Cost of valued consistency nogoods in (D)VR-MAS refers to the remaining values in the label rather than to eliminated values: (equations changed accordingly) | October 17, 2002 | myself |
In Definition 2.5 "a" should be "v" | December 20, 2006 | Markus Aschinger |