The MPC-DisWCSP4 algorithm for DisWCSP with privacy guarantees. More...

Inheritance diagram for frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >:

Public Member Functions
	MPC_DisWCSP4 (DCOPProblemInterface< V, AddableInteger > problem, Element params)
	Constructor.
Collection< MessageType >	getMsgTypes ()
void	notifyIn (Message msg)
Public Member Functions inherited from frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >
	MPC_DisCSP4 (DCOPProblemInterface< V, AddableInteger > problem, Element params)
	Constructor.
void	setQueue (Queue queue)
Collection< MessageType >	getMsgTypes ()
void	notifyIn (Message msg)

Static Public Attributes
static MessageType	START_MSG_TYPE = AgentInterface.START_AGENT
	The type of the start message.

Protected Member Functions
void	terminate ()
	Moves to the next target cost, or terminates if the maximum cost has been reached.
void	nextMultiplication ()
void	findFirstSolution ()
void	init ()
void	recordCandidateSol (AddableInteger publicCost, AddableInteger privateCost, List< BigInteger > sPrimePrime)
Protected Member Functions inherited from frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >
void	terminate ()
	Terminates.
void	nextMultiplication ()
	Moves to the next vector multiplication, if any remains.
void	revealSol ()
	Reveals to each agent all shares of its variables' optimal values.
void	processPending ()
	Processes pending messages.
void	findFirstSolution ()
	Initiates the arithmetic circuit on S that singles out its first 1 entry.
void	init ()
	Parses the problem.
void	recordCandidateSol (AddableInteger publicCost, AddableInteger privateCost, List< BigInteger > sPrimePrime)
	Records a candidate solution.
void	share0 ()
	Creates and sends share of 0.
void	shareVectorOfZeros ()
	Shares a vector full of zeros.

Private Member Functions
void	findAllSolutions (final int cost)
	Starts the computation of the p vector, which will have a share of 1 for each solution of the input cost.

Private Attributes
final AddableInteger	infiniteCost
	In private constraints, infinite costs are replaced with this value.
final int	maxCost
	The maximum total cost of any solution.
int	targetCost = 0
	The cost for which we are looking for all solutions.

Additional Inherited Members
Protected Attributes inherited from frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >
Queue	queue
	The queue used to exchange messages.
DCOPProblemInterface< V, AddableInteger >	problem
	The problem.
boolean	started
	Whether the algorithm has been started.
ArrayList< String >	agents
	The agents in lexicographic order.
int	nbrAgents
	The number of agents.
int	myAgentID
	This agent's index in the ordered list of agents.
int	nbrSols
	The number of publicly feasible solutions.
final BigInteger	modulo
	Shamir secret shares are modulo this number.
BigInteger[]	Sprime
	The vector S' of Shamir shares of the feasibility of each publicly feasible solution.
final PaillierCryptoScheme	cryptoScheme
	The Paillier crypto scheme.
BigInteger[]	S
	The vector S of Shamir shares of whether each solution is the optimal one.
BigInteger	hi
	When computing the vector S, the previous value of h.
BigInteger	Si
	When computing the vector S, the previous value of Si.
Phase	phase
	The current phase.
int	step
	A step of computation.
MultiPhase	multiPhase
	The current phase of the current multiplication operation.
boolean	currStep
	Boolean used to identify received messages that belong to the next phase and should be postponed.
int	sharesCount
	Counter used to keep track of the number of shares exchanged.
ArrayList< Message >	pendingMsgs
	Messages received too early to be processed.

Detailed Description

The MPC-DisWCSP4 algorithm for DisWCSP with privacy guarantees.

MPC-DisWCSP4 is MPC-DisCSP4, with the weak extension to DisWCSPs initially proposed for MPC-DisCSP2 in the following paper:

Marius-Calin Silaghi and Debasis Mitra. Distributed constraint satisfaction and optimization with privacy enforcement. In Proceedings of the 2004 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT'04), pages 531-535, Beijing, China, September 20-24 2004. IEEE Computer Society Press.

MPC-DisCSP4 is described in the following paper:

Marius-Calin Silaghi. Hiding absence of solution for a distributed constraint satisfaction problem (poster). In Proceedings of the Eighteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS'05), pages 854-855, Clearwater Beach, FL, USA, May 15-17 2005. AAAI Press.

Author: Thomas Leaute

Parameters

<V>	the type used for variable values

Todo: Important performance improvement: before un-shuffling, check whether it is necessary by checking whether the S vector sums up to 1.

Constructor & Destructor Documentation

◆ MPC_DisWCSP4()

frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.MPC_DisWCSP4	(	DCOPProblemInterface< V, AddableInteger >	problem,
		Element	params )

Constructor.

Parameters

problem	the overall problem
params	the parameters

References frodo2.solutionSpaces.AddableInteger.PlusInfinity.PLUS_INF, and frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.problem.

Referenced by getMsgTypes().

Member Function Documentation

◆ findAllSolutions()

void frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.findAllSolutions ( final int cost )

private

Starts the computation of the p vector, which will have a share of 1 for each solution of the input cost.

Parameters

cost	the cost of interest

References frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.modulo, frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.nbrSols, frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.S, frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.shareVectorOfZeros(), frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.Sprime, and frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.step.

Referenced by findFirstSolution(), and terminate().

Here is the call graph for this function:

◆ findFirstSolution()

void frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.findFirstSolution ( )

protected

See also: MPC_DisCSP4.findFirstSolution()

References findAllSolutions().

Here is the call graph for this function:

◆ getMsgTypes()

Collection< MessageType > frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.getMsgTypes ( )

See also: MPC_DisCSP4.getMsgTypes()

References frodo2.algorithms.mpc_discsp.EncrSharesMsg.ENCR_SHARES_MSG_TYPE, MPC_DisWCSP4(), frodo2.algorithms.mpc_discsp.OneShareMsg.ONE_SHARE_MSG, frodo2.algorithms.mpc_discsp.SharesMsg.SHARES_MSG_TYPE, and frodo2.algorithms.mpc_discsp.SolShareMsg.SOL_SHARE_MSG_TYPE.

Here is the call graph for this function:

◆ init()

void frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.init ( )

protected

See also: MPC_DisCSP4.init()

References frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V >.nbrSols.

Referenced by notifyIn().

◆ nextMultiplication()

void frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.nextMultiplication ( )

protected

See also: MPC_DisCSP4.nextMultiplication()

Here is the call graph for this function:

◆ notifyIn()

void frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.notifyIn ( Message msg )

See also: MPC_DisCSP4.notifyIn(Message)

Here is the call graph for this function:

◆ recordCandidateSol()

void frodo2.algorithms.mpc_discsp.MPC_DisWCSP4< V extends Addable< V > >.recordCandidateSol	(	AddableInteger	publicCost,
		AddableInteger	privateCost,
		List< BigInteger >	sPrimePrime )