Distributed Problem Solving Problem environments Centrally controlled environments Cooperative processes Non-cooperative processes TCP: an illustration TCP: an illustration TCP: an illustration TCP: an illustration TCP: an illustration Tragedy of the Commons Distributing a Problem Problem Coupling Tightly Coupled Problems Tightly Coupled Problems Loosely coupled problems distributed.net Symmetric-key encryption: a brief digression Symmetric-key encryption: a brief digression distributed.net How does it work? How does it work? Grid computing vs. Public resource computing SETI@Home SETI@Home SETI@Home The SETI@Home architecture The SETI@Home architecture The distributed search problem Folding@Home Folding@Home BOINC BOINC ``Medium-coupled'' problems SummaryDistributed SoftwareDevelopmentProblem Solving IChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p. 1/??Distributed Problem Solving•The preliminary portion of the course focused on techniquesfor achieving properties or states in distributed systems.•Causal delivery, mutual exclusion, etc.•Now, we turn to the question of how to solve problems in adistributed fashion, assuming that we have implementedsome of these properties.Department of Computer Science — University of San Francisco – p. 2/??Problem environments•One dimension along which we can characterize distributedproblem solving is according to the degree of autonomy orself-interestedness of the participants.•How much can a protocol assume about the behavior andmotives of the participants?Department of Computer Science — University of San FranciscoCentrally controlled environments•At one extreme, all processes in a system are controlled by asingle individual or organization.•Beowulf cluster•Parallel computer•Intranet•This allows us to make fairly restrictive assumptions aboutthe behavior of system processes.•NFS, parallel computation (e.g. conjugate gradient)Department of Computer Science — University of San Francisco – p. 4/??Cooperative processes•We’ll also think about processes that are controlled byseparate individuals, but assumed to be cooperative.•SETI@Home, distributed.net•Meeting scheduling•TCP (originally)•In this case, we can assume that processes will actbenevolently, but that they will be heterogeno us.Department of Computer Science — University of San Francisco – p. 5/??Non-cooperative processes•We’ll also need to think about non-co operative systems, inwhich each process is self-interested.•Not necessarily malevolent, just concerned only aboutits own performance.•This will require a different set of assumptions about howour protocol should work.•Resource allocation, auctions, some schedulingproblems, file-sharingDepartment of Computer Science — University of San FranciscoTCP: an illustration•TCP is an example of a protocol that was designed to workin a cooperative environment.•Recall that TCP is built on top of UDP•UDP provides packet-oriented delivery.•TCP provides reliable in-order delivery on top of UDP.•Sender A sends a packet to receiver B.•B returns an acknowledgment that the packet was received.•If A does not receiv e an ACK before a timer expires, thepacket is resent.Department of Computer Science — University of San Francisco – p. 7/??TCP: an illustration•To improve transmission efficiency, TCP uses a conceptcalled sliding windows.•The sender has a “window”of size n. It sends all packetswithin that window.•As the lowest-numbered packet in the window isacknowleged, the window“slides”upward, and morepackets are sent.•This improves transmission rates - the goal is for thenetwork to be completely saturated.Department of Computer Science — University of San Francisco – p. 8/??TCP: an illustration•The problem is how to deal with congestion.•Packets may be dropped by the receiver, or byintermediate hosts.•When should the sender resend?•Too slow → inefficiency•Too quickly → oversaturation is worsened.•TCP uses an adaptive retransmission policy.•As connection performance changes, so does timeoutduration.Department of Computer Science — University of San FranciscoTCP: an illustration•The TCP congestion algorithm does the following (lo osely):•When a packet is lost, halve the window size and doubletimeout.•If all packets in a window are transmitted successfully,increase window size by 1.•There are lots of details in the implementation of this thatI’m glossing over.•The key point is this: This protocol works wonderfully, aslong as everyone else also uses it.•Designed to minimize congestion over the e ntireInternet.Department of Computer Science — University of San Francisco – p. 10/??TCP: an illustration•In the early days if the Internet, this was not a problem.•Small number of users, fewer bandwidth-saturatingapps.•Parallel download of images from web pages was the fi rstconcern.•Later, non-TCP protocols (RTSP, proprietary schemes)implemented their own congestion control algorithms.•These applications are not necessarily tuned to any sort ofglobal optimum.Department of Computer Science — University of San Francisco – p. 11/??Tragedy of the Commons•This is an example of a problem known as tragedy of thecommons.•Cost of using a resource is not borne equally by thebeneficiaries of that resource.•Leads to overuse.•Shared resources, such as networks, tend to be vulnerable tothis problem.•Game theory provides some ideas for dealing with thisdilemma.Department of Computer Science — University of San Francisco –Distributing a Problem•We’ll also need to think about how well a problem can bepartitioned.•Typically, a problem is distributed by dividing it intosubproblems.•Each node or process works on its own subproblem.•Processes may need to communicate with each other.•A center or coordinator is respo nsible for doling outsubproblems and collecting results.Department of Computer Science — University of San Francisco – p. 13/??Problem Coupling•We can characterize distributed problems by the degree ofinteraction that is required between nodes.•Tightly coupled: nodes must communicate frequently inorder to solve subproblems.•Loosely coupled: Subproblems are relatively independent ofeach other.•“Medium coupled”: Some interaction must take place.Department of Computer Science — University of San
View Full Document
Unlocking...