Distributed Software Development More Problem Solving Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science University of San Francisco p 1 Distributed Problem Solving Last week we talked about loosely coupled distributed problems Primarily distributed search A large data set is divided across clients Clients interact only with a central server no client client communication Department of Computer Science University of San Francisco p 2 Medium coupled problems In medium coupled problems each node can do a substantial amount of computing on its own A final solution will require communication between nodes Actions taken by one node can affect other nodes Department of Computer Science University of San Francisco p 3 Example scheduling classes Before the semester starts Benson sends every teacher an email When and where do you want your classes Each professor has their own constraints and can come up with choices locally Brooks no classes before 10 am in Kudlick Wolber No classes on Friday Galles Mornings nothing on Lone Mountain Brooks is able to eliminate some possible schedules without consulting with anyone else Department of Computer Science University of San Francisco p 4 Example scheduling classes Some choices require communication with a center Benson Only one class in Kudlick at a time Some classes may be constrained by other departments choices CS 110 and Calculus I should be at different times Nodes start with a large set of constraints some are eliminated by the center Hopefully at least one viable schedule remains If not someone is encouraged to relax their constraints Department of Computer Science University of San Francisco p 5 Constraint Satisfaction A constraint satisfaction problem is one of assigning values to variables so as to satisfy a set of constraints Typically any solution that satisfies the constraints is equally acceptable Toy problems N queens map coloring Real problems Scheduling CS classes Building a car Register allocation Department of Computer Science University of San Francisco p 6 Constraint Satisfaction More formally a CSP consists of a set of variables x1 x2 xn Each variable as a domain of possible values D1 D2 Dn and a set of constraints C1 C2 Unary constraints x 10 ymod2 0 etc Binary constraints x y x y 50 etc N ary constraints x1 x2 xn 75 a problem with N ary constraints can be transformed into a binary constraint problem with an increase in the number of variables Department of Computer Science University of San Francisco p 7 Formalizing a CSP An assignment of values to variables that satisfies all constraints is called a consistent solution We might might also have an objective function y f x1 xn that lets us compare solutions Department of Computer Science University of San Francisco p 8 Approaches If the domain of all variables is continuous i e real numbers and constraints are all linear functions we can use linear programming to solve the problem This is actually the easy version in P Express the problem as a system of equations If variables are discrete the problem is harder We can use dynamic programming Often variables have complex or symbolic values In the most general case we can express a CSP as a search problem Department of Computer Science University of San Francisco p 9 Solving CSPs with search We can use depth first search to solve a CSP Begin with an initial state no values assigned to x1 xn Sequentially assign values to variables We are done if we find an assignment to each variable such that all constraints are met Since CSPs are commutative for a solution it doesn t matter which order values are assigned we can consider one variable at a time Department of Computer Science University of San Francisco p 10 Backtracking With CSPs the challenge is deciding how to proceed when a constraint is violated Some assignment of values to variables must be undone but which This decision is called backtracking Standard DFS undoes the most recently assigned value This is called chronological backtracking Easy to implement Problem an early assignment may have doomed us to an inconsistent solution Department of Computer Science University of San Francisco p 11 Example Three coloring the map of Australia Assigning Q red NSW green V blue T red cannot lead to a solution Different values for T will not change this V needs value Northern Territory Queensland Western Australia South Australia New South Wales Victoria Tasmania a different Department of Computer Science University of San Francisco p 12 Distributed CSP In some cases the variables in a CSP may be distributed over multiple nodes or processes or agents Natural division of problem e g scheduling a meeting coordinating research teams Information may be private or difficult to quantify and share Constraints may be intra agent or inter agent Agents communicate by message passing with asynchronous communication Department of Computer Science University of San Francisco p 13 Algorithms for Distributed CSP For purposes of demonstration we ll make the following assumptions Each process has a single variable All variables have binary values All constraints are binary Note this is just to keep the examples simple the algorithms work fine without these assumptions Department of Computer Science University of San Francisco p 14 Asynchronous Backtracking Asynchronous backtracking extends normal backtracking search to a distributed environment Each process has a priority pi Each agent chooses a value for its variable and send this value to all processes that it shares a constraint with No defined order in which messages are sent asynchronous communication All agents are selecting values simultaneously If a node cannot find a consistent value it generates a nogood Department of Computer Science University of San Francisco p 15 Asynchronous Backtracking Example x1 x2 1 2 x1 and x3 can be either 1 or 2 x2 can only be 2 x1 x3 x2 x3 we can see that the only solution is x1 x2 2 x3 1 2 x3 1 2 Department of Computer Science University of San Francisco p 16 Asynchronous Backtracking Example Each node sends messages to other nodes that it shares a constraint with Includes all known assignments For example x1 sends an ok x1 1 to x3 x2 sends ok x2 2 to x3 x3 constructs a local view from this x1 1 x2 2 x3 cannot choose a value consistent with this local view Department of Computer Science University of San Francisco p 17 Asynchronous Backtracking Example x3
View Full Document
Unlocking...