Asynchronously solving problems with privacy requirements


Marius-Calin Silaghi


Swiss Federal Institute of Technology (EPFL)


Boi Faltings


Asynchronous search techniques for distributed satisfaction problems are among the scientific challenges of Distributed Artificial Intelligence. They are useful in applications like negotiations (Generalized English Auctions), distributed meeting scheduling with private constraints, distributed configuration with secret know-how.

Asynchronous search also has an important theoretic value, defining generic techniques whose properties, once proven, apply to a large number of not only distributed but also centralized old and new algorithms. A convincing example is the technique I propose for using backtracking nogoods in consistency (Section~\ref{sec:AMC:dmac-abt}), technique that can be straightforwardly applied to classic centralized versions of backtracking (as I show in Section~\ref{sec:DPF:FBT}) with improvements of efficiency.

Despite the continuous effort of the last ten years, several important issues remained open until now. This thesis describes several advances that allow the agents to get more opportunities to communicate. It also proposes new frameworks for distributed constraint satisfaction, and strategies for agents. The main focus is on asynchronous complete search with polynomial space requirements in the size of the global problem, where the global problem is distributed naturally.

Among the main contributions I mention:

  • Local consistency is a technique bringing gains that are exponential in the size of the problem, by deposing an effort that is exponential in the size of the used predicates (constraints). The effort can therefore be polynomial in the size of the global problem. {\bf Exponential gain with polynomial cost} made local consistency the most important technique in constraint satisfaction where it was shown that any opportunity must be used for exploiting it ({\em consistency maintenance}). I generalize the concept of centralized consistency maintenance in a way that makes it applicable to asynchronous techniques. This is the first technique allowing for consistency maintenance in asynchronous search and is very efficient (Chapter~\ref{chap:AMC}).

  • I noticed that the use of CSPs techniques for numeric problems over \R{} was possible by something that can be described as: {\em letting the domain splits have existential meaning rather than the universal meaning in classical backtracking}. Existing asynchronous search protocols supported only proposals with universal quantifiers (e.g. {\bf require}($\forall x\in{1})$). I modify and generalize existing asynchronous search protocols to support proposals with existential quantifiers (e.g. {\bf require}($\exists x\in{[1.5,10^5]\cup{0,1}}$)). This efficient technique is the first to allow a {\bf proper use of intervals} in proposals and is a first step I took for extending the applicability of asynchronous search to Numeric CSPs. Since this idea came when I tried to integrate in ABT an aggregation technique described in~\cite{rfia00}, the first protocol with the desired property is called Asynchronous Aggregation Search (see Chapter~\ref{chap:AAS}).

  • Existing algorithms enforced a static priority on agents. This is a drawback. It entangles agents to {\em verify conflicts in Generalized English Auctions} (Chapter~\ref{chap:ASS}), for defending themselves from unfair competition. One only knew to remove that constraint at the expense of requiring an unbounded computer memory (e.g. RAM). This is infeasible and leads to unwarranted protocols. I designed the first solving protocol that {\bf allows the needed dynamic reordering} and still has {\bf a guaranteed termination} with polynomially bounded computer space requirements. Moreover, the designed technique is very general as it can introduce all important reordering heuristics used for efficiency in centralized techniques (see Chapter~\ref{chap:ABTR}).

  • Besides the aforementioned reordering technique, I propose a suite of other techniques for dynamic reordering with other types of heuristics and still offering guaranteed termination with polynomial space requirements: Reordering with increasing delay restarts (Section~\ref{sec:ABTR:restarts}), and Finite number of reorderings. These two techniques are simple but allow only simplistic reordering heuristics. Dynamic Partial Order is discussed in Section~\ref{sec:ABTR:poas}.

  • Proposals with existential quantifiers are not sufficient for enabling application of search to numeric problems. The remaining requirement is that {\em proposals must not be binding}. Actually, one of the powerful and general available centralized techniques for solving numeric problems is the one proposed in Section~\ref{sec:cDPF:uca6}. Domains are split recursively, and {\bf the same constraints are recursively reverified} until complete satisfaction or an acceptable resolution is obtained.

  • Asynchronous techniques requested an agent only once its proposal. The proposals were therefore necessarily binding. This is incompatible with the practice required for numeric problems, as mentioned at the previous item. After understanding this problem, I proposed a modeling technique called Replica-based search. Several replicas of the same agent are asked proposals at different levels of abstractions. As a result, {\bf proposals of the replicas are not binding}. They can be refused by subsequent replicas (e.g. After an agent sends {\bf require}($\exists x\in{[1.5,10^5]\cup{0,1}}$), it can be more restrictive in a subsequent replica, {\bf require}($\exists x\in{[15,1000]}$), and later can even abandon completely its proposal, {\bf require}($x\not\in{[1.5,10^5]\cup{0,1}}$)). This technique, described in Chapter~\ref{chap:RDisCSP} closes the sequence of ideas required for developing asynchronous techniques for numeric problems over \R.

  • One of the main motivations for distributed algorithms is the enforcement of privacy. A framework for modeling and quantifying privacy loss and a {\bf theoretic comparison on the power of different protocols in saving privacy} are proposed in Chapter~\ref{chap:Privacy}.

  • Hewlett-Packard, learning that the ink-jet printer is a competitor for their main product, the laser printer, decided to also develop ink-jet printers in parallel. With the same principle in mind, I developed and analyzed an expensive secure protocol (SCSPS), proposed in Chapter~\ref{chap:Secure}. I also developed and analyzed {a set of cryptographic protocols for both discrete and numeric distributed satisfaction problems} (Annex~\ref{chap:Test}). For the work described in Annex~\ref{chap:Test}, another important contribution is the discovery of the feebleness of that type of techniques, the ``S-attacks''. The obtained cryptographic protocols have some drawbacks such that a trade-off remains between the competing techniques. Secure protocols and distributed algorithms will continue to coexist for a while, as laser printers and ink-jet printers.

  • Several distributed optimization techniques have been developed so far. Those techniques are not general and abstract enough for allowing extensions like consistency maintenance and reordering. The notion of cost was unclear. I {\bf introduce the notion of cost in nogoods, obtaining a general stand-alone communication atom}. In Chapter~\ref{chap:Optimization} I describe a generalization of all the existing distributed satisfaction and optimization techniques. This generalization allows the introduction of consistency maintenance, reordering, etc. in distributed optimization.

  • Negotiations are defined by the fact that the participants yield from their constraints to reach common solutions. This is technically called: constraint relaxation. No relaxation technique existed for private problems. I propose such a technique for private constraints (Section~\ref{sec:GEA:CR}). A classical dualism for CSPs defines a standard transfer between privacy on constraints and privacy on domains (see Section~\ref{sec:domain-constraints} and Chapter~\ref{chap:DisGCSP}). We have also defined a primal version of this technique.


Friday, August 2, 2002