Asynchronously solving problems with privacy requirements
by Marius-Calin Silaghi
Keywords: 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 11
3 Parallel and Distributed Search 23
4 Asynchronous Search 33
5 Dual, Primal, and Full approach 39
Part II Asynchronous Algorithms 57
6 Nogood elimination in asynchronous search 59
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
Part III Advanced Issues about DisCSP 157
17 Generalized English Auctions --- Secure Verification of Conflicts 159
18 Distributed Generative Constraint Satisfaction 175
19 Openness in Complete Asynchronous Search 183
20 Distributed Systems Issues 191
Contributions and Conclusions 197
Annexes 201
A Problem Solving 203
B Problems with a secure test operator 225
C Properties of General English Auctions 233
D Centralized Aggregation 239
References 259
Curriculum Vitae 271
If you remark a bug or an error, you can write me at (and your contribution will be acknowledged):
Errata for the final version:
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