Unformatted text preview:

Live ObjectsLive ObjectsLive ObjectsLive ObjectsKrzys Ostrowski, Ken Birman, Danny DolevKrzys Ostrowski, Ken Birman, Danny DolevCornell University, Hebrew University*(*) Others are also involved in some aspects of this project… I’ll mention them when their work arises…Live Objects in an Active WebLive Objects in an Active WebImagine a world of Live Objects .Imagine a world of Live Objects….…. and an Active Web created with “drag and drop”Live Objects in an Active WebLive Objects in an Active WebImagine a world of Live Objects .Imagine a world of Live Objects….…. and an Active Web created with “drag and drop”Live Objects in an Active WebLive Objects in an Active WebUser builds applications much like powerpointUser builds applications much like powerpoint• Drag things onto a “live document” or desktop• Customize them via a properties sheetpp• Then share the live document Opening a document “joins” a session • New instance can obtain a state checkpoint• All see every update…• Platform offers privacy, security, reliability propertiesWhen would they be useful?When would they be useful? Build a disaster response system… … in the field (with no programming needed!) Coordinated planning and plan execution Create role-playing simulations, games Integrate data from web services into databases, spreadsheets Visualize complex distributed state Track business processes, status of major projects, even state of an applicationBig deal?Big deal?We think so!We think so!• It is very hard to build distributed systems today. If non-programmers can do the job numbers of such applications will soar• Live objects are robust to the extent that our platform is able to offer properties such as security privacyis able to offer properties such as security, privacy protection, fault-tolerance, stability Live objects might be a way to motivate users to jg yadopt a trustworthy technologyThe drag and drop worldThe drag and drop worldIt needs a global namespace of objectsIt needs a global namespace of objects• Video feeds, other data feeds, live maps, etc…• Our thinking: download them from a repository or gpy(rarely) build new ones Users make heavy use of live documents, share hkdfl bother kinds of live objects And this gives rise to a world with• Lots of live traffic, huge numbers of live objects• Any given node may be “in” lots of object groupsOverlapping groupsOverlapping groupsControl EventsBackground Radar ImagesATC eventsRadar track updatesBackground Radar ImagesMulticast groups supporting live Radar track updatesWeather notificationsobjectsNodes running live applications… posing technical challenges… posing technical challengesHow can we build a system thatHow can we build a system that…• Can sustain high data rates in groups• Can scale to large numbers of overlapping groupsgppggp• Can guarantee reliability and security properties Existing multicast systems can’t solve these problems!Existing technologies won’t work…Existing technologies won’t work…Kind of technology Why we rejected itIP multicast, pt-to-pt TCPToo many IPMC addrs. Too many TCP streamsSoftware group multicast li (“h ih”)Protocols designed for just one group at a time; h d I bili i l d lsolutions (“heavyweight”)overheads soar. Instability in large deploymentsLightweight groupsNodes get undesired traffic, data sent indirectlyPblihbibbUtblil dl tdt tidi tlPublish-subscribe busUnstable in large deployments, data sent indirectlyContent-filtering event notification.Very expensive. Nodes see undesired traffic. High latency paths are commonnotification.High latency paths are commonPeer-to-peer overlaysSimilar to content-filtering scenarioSteps to a new system!Steps to a new system!1. First,we’ll look at group overlap and will show that we ,gp pcan simplify a system with overlap and focus on a single “cover set” with a regular, hierarchical overlap2. Next, we’ll design a simple fault-tolerance protocol for high-speed data delivery in such systems3. We’ll look at its performance (and arrive at surprising insights that greatly enhance scalability under stress)ggy y )4. Last, ask how our solution can be enhanced to address need for stronger reliability securityneed for stronger reliability, securityCoping with Group OverlapCoping with Group OverlapIn a nutshell:In a nutshell:• Start by showing that even if groups overlap in an irregularway, we can “decompose” the structure into a collection of overlayed “cover sets”• Cover sets will have regularoverlapClean hierarchical inclusionClean, hierarchical inclusion Other good propertiesRegular OverlapRegular Overlapgroupsnodes Likely to arise in a data center that replicates services and automates layout of services on nodesLive Objects Live Objects ⇒⇒ Irregular overlapIrregular overlapLikely because users will have different interestsLikely because users will have different interests…Tiling an irregular overlapTiling an irregular overlapBuild some (small) number of regularly u d so e (s a ) u be o egu a yoverlapped sets of groups (“cover sets”) s.t.• Each group is in one cover set• Cover sets are nicely hierarchical• Traffic is as concentrated as possible Seems hard: O(2G) possible cover setsf’dld ll In fact we’ve developed a surprisingly simple algorithm that works really well. Ymir Vigfusson has been helping us study this:has been helping us study this:Algorithm in a nutshellAlgorithm in a nutshell1Remove tiny groups and collapse identical ones1.Remove tiny groups and collapse identical ones2. Pick a big, busy group1.Look for another big, busy group with extensive overlap1.Look for another big, busy group with extensive overlap2. Given multiple candidates, take the one that creates the largest “regions of overlap”3. Repeat within overlap regions (if large enough)ABABNodes only in group ANodes only in group BNodes in A and BWhy this worksWhy this worksin general, it wouldn’t work!… in general, it wouldnt work! But many studies suggest that groups would have power-law popularity distributionspowerlaw popularity distributions• Seen in studies of financial trading systems, RSS feeds • Explained by “preferential attachment” models In such cases the overlap has hidden structure… and the algorithm finds it! It also works


View Full Document

CORNELL CS 5410 - Live Objects

Download Live Objects
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 Live Objects 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 Live Objects 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?