USF CS 682 - Distributed Software Development

Unformatted text preview:

{small lecturenumber - heblocknumber :} Distributed Problem Solvingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Problem environmentsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Centrally controlled environmentsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Cooperative processesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Non-cooperative processesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} TCP: an illustrationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} TCP: an illustrationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} TCP: an illustrationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} TCP: an illustrationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} TCP: an illustrationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tragedy of the Commonsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Distributing a Problemaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Problem Couplingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tightly Coupled Problemsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tightly Coupled Problemsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Loosely coupled problemsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} distributed.netaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Symmetric-key encryption: a brief digressionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Symmetric-key encryption: a brief digressionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} distributed.netaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} How does it work?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} How does it work?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} SETI@Homeaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} SETI@Homeaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} SETI@Homeaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} The SETI@Home architectureaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} The SETI@Home architectureaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} The distributed search problemaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} ``Medium-coupled'' problemsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Summaryaddtocounter {blocknumber}{1}Distributed Software DevelopmentProblem Solving IChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p.1/??11-0: Distributed Problem SolvingIn the first half of the course, we focused on techniques forachieving properties or states in distributed systems.Causal delivery, mutual exclusion, etc.Now, we’ll turn to the question of how to solve problems ina distributed fashion, assuming that we have implementedsome of these properties.Department of Computer Science — University of San Francisco – p.2/??11-1: Problem environmentsOne dimension along which we can characterizedistributed problem solving is according to the degree ofautonomy or self-interestedness of the participants.How much can a protocol assume about the behavior andmotives of the participants?Department of Computer Science — University of San Francisco – p.3/??11-2: Centrally controlledenvironmentsAt one extreme, all processes in a system are controlledby a single individual or organization.Beowulf clusterParallel computerIntranetThis 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/??11-3: Cooperative processesWe’ll also think about processes that are controlled byseparate individuals, but assumed to be cooperative.SETI@Home, distributed.netMeeting schedulingTCP (originally)In this case, we can assume that processes will actbenevolently, but that they will be heterogenous.Department of Computer Science — University of San Francisco – p.5/??11-4: Non-cooperative processesWe’ll also need to think about non-cooperative 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 Francisco – p.6/??11-5: TCP: an illustrationTCP is an example of a protocol that was designed towork in a cooperative environment.Recall that TCP is built on top of UDPUDP 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 wasreceived.If A does not receive an ACK before a timer expires, thepacket is resent.Department of Computer Science — University of San Francisco – p.7/??11-6: TCP: an illustrationTo improve transmission efficiency, TCP uses a conceptcalled sliding windows.The sender has a “window” of size n. It sends allpackets within 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/??11-7: TCP: an illustrationThe problem is how to deal with congestion.Packets may be dropped by the receiver, or byintermediate hosts.When should the sender resend?Too slow → inefficiencyToo quickly → oversaturation is worsened.TCP uses an adaptive retransmission policy.As connection performance changes, so does timeoutduration.Department of Computer Science — University of San Francisco – p.9/??11-8: TCP: an illustrationThe TCP congestion algorithm does the following(loosely):When a packet is lost, halve the window size anddouble timeout.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


View Full Document

USF CS 682 - Distributed Software Development

Documents in this Course
Load more
Download Distributed Software Development
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Distributed Software Development and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Distributed Software Development 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?