CS525 Advanced Distributed Systems Spring 2011What is a Distributed System? (examples)Can you name some examples of Operating Systems?Slide 4What is an Operating System?Slide 6FOLDOC definitionCan you name some examples of Distributed Systems?Slide 9What is a Distributed System?Slide 11Textbook definitionsUnsatisfactorySlide 14A working definition for usA range of interesting problems for Distributed System designersA range of challengesMulticastSlide 19Fault-tolerance and ScalabilityCentralizedTree-BasedA Third ApproachSlide 24Slide 25Slide 26“Epidemic” Multicast (or “Gossip”)PropertiesAnalysisAnalysis (contd.)Epidemic MulticastEpidemic Multicast AnalysisSlide 33Fault-toleranceSlide 35So,…Some implementationsNNTP Inter-server ProtocolSlide 39Angles of Distributed SystemsCS 525 and Distributed SystemsSlide 42Interesting: Area OverlapsSlide 44“Entrepreneurial”?“Research”?Tidbit: Research vs. UsersMaterials for CourseProject BuildupLet’s Look at the Course Information Sheet…Things for you to do todayNext LectureBackup SlidesSlide 541CS525 Advanced Distributed SystemsSpring 2011Indranil Gupta (Indy)Lecture 1January 18, 2011All Slides © IG2What is a Distributed System? (examples)The Internet Gnutella peer to peer systemFood Web of Little Rock Lake, WIA Sensor Network3Can you name some examples of Operating Systems?4Can you name some examples of Operating Systems?…Linux WinXP Vista Unix FreeBSD Mac OSX2K Aegis Scout Hydra Mach SPINOS/2 Express Flux Hope SpringAntaresOS EOS LOS SQOS LittleOS TINOSPalmOS WinCE TinyOS…5What is an Operating System?6What is an Operating System?•User interface to hardware (device driver)•Provides abstractions (processes, file system)•Resource manager (scheduler)•Means of communication (networking)•…7FOLDOC definition•The low-level software which handles the interface to peripheral hardware, schedules tasks, allocates storage, and presents a default interface to the user when no application program is running.•The OS may be split into a kernel which is always present and various system programs which use facilities provided by the kernel to perform higher-level house-keeping tasks, often acting as servers in a client-server relationship.•Some would include a graphical user interface and window system as part of the OS, others would not. The operating system loader, BIOS, or other firmware required at boot time or when installing the operating system would generally not be considered part of the operating system, though this distinction is unclear in the case of a roamable operating system such as RISC OS.•The facilities an operating system provides and its general design philosophy exert an extremely strong influence on programming style and on the technical cultures that grow up around the machines on which it runs.8Can you name some examples of Distributed Systems?9Can you name some examples of Distributed Systems?•Client-server (e.g., NFS)•The Internet•The Web•An ad-hoc network•A sensor network•DNS•BitTorrent (peer to peer overlays)•Datacenters10What is a Distributed System?11FOLDOC definitionA collection of (probably heterogeneous) automata whose distribution is transparent to the user so that the system appears as one local machine. This is in contrast to a network, where the user is aware that there are several machines, and their location, storage replication, load balancing and functionality is not transparent. Distributed systems usually use some kind of client-server organization.12Textbook definitions•A distributed system is a collection of independent computers that appear to the users of the system as a single computer [Andrew Tanenbaum] •A distributed system is several computers doing something together. Thus, a distributed system has three primary characteristics: multiple computers, interconnections, and shared state[Michael Schroeder]13Unsatisfactory•Why are these definitions short? •Why do these definitions look inadequate to us?•Because we are interested in the insides of a distributed system–algorithmics–design and implementation–maintenance–study14I shall not today attempt further to define the kinds of material I understand to be embraced within that shorthand description; and perhaps I could never succeed in intelligibly doing so. But I know it when I see it… [Potter Stewart, Associate Justice, US Supreme Court (talking about his interpretation of a technical term laid down in the law, case Jacobellis versus Ohio 1964) ]15A working definition for us A distributed system is a collection of entities, each of which is autonomous, programmable, asynchronous and failure-prone, and which communicate through an unreliable communication medium. •Our interest in distributed systems involves –algorithmics, design and implementation, maintenance, study•Entity=a process on a device (PC, PDA, mote)•Communication Medium=Wired or wireless network16A range of interesting problems for Distributed System designers• •Routing and Multicast [IP multicast, SRM, RMTP]•Post and retrieve [Usenet]•Search [BitTorrent, Google]•Programming [MapReduce, Pig, Dryad]•Storage [Databases, HDFS]•Coordination and Scheduling [EC2, SETI@Home]•Infrastructures [EC2, S3, AppEngine, CCT, OpenCirrus]• •17A range of challenges• •Failures: no longer the exception, but rather a norm•Scalability: 1000s of machines, Terabytes of data•Asynchrony: clock skew and clock drift•Security: of data, users, computations, etc.•18MulticastMulticast19MulticastDistributedDistributedGroup ofGroup of “ “Nodes”=Nodes”=ProcessesProcessesat Internet-at Internet-based hostsbased hostsNode with a piece of information to be communicated to everyone20Fault-tolerance and ScalabilityMulticast senderMulticast senderMulticast ProtocolMulticast Protocol Nodes may crashNodes may crash Packets may Packets may be dropped be dropped 1000’s of nodes1000’s of nodesXXXX21CentralizedUDP/TCP packets Simplest Simplest implementationimplementation Problems?Problems?22Tree-BasedUDP/TCP packets e.g., IPmulticast, SRMe.g., IPmulticast, SRM RMTP, TRAM,TMTPRMTP, TRAM,TMTP Tree setupTree setup and maintenanceand maintenance Problems?Problems?23A Third ApproachMulticast senderMulticast sender24Gossip messages (UDP)Gossip messages (UDP)Periodically, transmit to Periodically, transmit to b b random targetsrandom targets25Other nodes do same Other nodes do
View Full Document
Unlocking...