ÿþ<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv=Content-Type content="text/html; charset=unicode"> <meta name=ProgId content=Word.Document> <meta name=Generator content="Microsoft Word 12"> <meta name=Originator content="Microsoft Word 12"> <link rel=File-List href="descrip2_files/filelist.xml"> <title>CS 542: Project Description</title> <!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>Mehdi</o:Author> <o:Template>Normal</o:Template> <o:LastAuthor>Mehdi Azarmi</o:LastAuthor> <o:Revision>3</o:Revision> <o:TotalTime>1</o:TotalTime> <o:Created>2011-01-20T16:45:00Z</o:Created> <o:LastSaved>2011-01-20T16:49:00Z</o:LastSaved> <o:Pages>3</o:Pages> <o:Words>2121</o:Words> <o:Characters>11374</o:Characters> <o:Company>Purdue University</o:Company> <o:Lines>94</o:Lines> <o:Paragraphs>26</o:Paragraphs> <o:CharactersWithSpaces>13469</o:CharactersWithSpaces> <o:Version>12.00</o:Version> </o:DocumentProperties> <o:OfficeDocumentSettings> <o:AllowPNG/> </o:OfficeDocumentSettings> </xml><![endif]--> <link rel=themeData href="descrip2_files/themedata.thmx"> <link rel=colorSchemeMapping href="descrip2_files/colorschememapping.xml"> <!--[if gte mso 9]><xml> <w:WordDocument> <w:SpellingState>Clean</w:SpellingState> <w:GrammarState>Clean</w:GrammarState> <w:TrackMoves/> <w:TrackFormatting/> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:DoNotPromoteQF/> <w:LidThemeOther>EN-US</w:LidThemeOther> <w:LidThemeAsian>X-NONE</w:LidThemeAsian> <w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript> <w:Compatibility> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> <w:SplitPgBreakAndParaMark/> <w:DontVertAlignCellWithSp/> <w:DontBreakConstrainedForcedTables/> <w:DontVertAlignInTxbx/> <w:Word11KerningPairs/> <w:CachedColBalance/> <w:UseFELayout/> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> <m:mathPr> <m:mathFont m:val="Cambria Math"/> <m:brkBin m:val="before"/> <m:brkBinSub m:val="&#45;-"/> <m:smallFrac m:val="off"/> <m:dispDef/> <m:lMargin m:val="0"/> <m:rMargin m:val="0"/> <m:defJc m:val="centerGroup"/> <m:wrapIndent m:val="1440"/> <m:intLim m:val="subSup"/> <m:naryLim m:val="undOvr"/> </m:mathPr></w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="false" DefSemiHidden="false" DefQFormat="false" LatentStyleCount="267"> <w:LsdException Locked="false" QFormat="true" Name="Normal"/> <w:LsdException Locked="false" QFormat="true" Name="heading 1"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 2"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 3"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 4"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 5"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 6"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 7"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 8"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 9"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="caption"/> <w:LsdException Locked="false" QFormat="true" Name="Title"/> <w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/> <w:LsdException Locked="false" QFormat="true" Name="Subtitle"/> <w:LsdException Locked="false" QFormat="true" Name="Strong"/> <w:LsdException Locked="false" QFormat="true" Name="Emphasis"/> <w:LsdException Locked="false" Priority="99" Name="No List"/> <w:LsdException Locked="false" QFormat="true" Name="No Spacing"/> <w:LsdException Locked="false" QFormat="true" Name="List Paragraph"/> <w:LsdException Locked="false" QFormat="true" Name="Quote"/> <w:LsdException Locked="false" QFormat="true" Name="Intense Quote"/> <w:LsdException Locked="false" QFormat="true" Name="Subtle Emphasis"/> <w:LsdException Locked="false" QFormat="true" Name="Intense Emphasis"/> <w:LsdException Locked="false" QFormat="true" Name="Subtle Reference"/> <w:LsdException Locked="false" QFormat="true" Name="Intense Reference"/> <w:LsdException Locked="false" QFormat="true" Name="Book Title"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="TOC Heading"/> </w:LatentStyles> </xml><![endif]--> <style> <!-- /* Font Definitions */ @font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:1; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:variable; mso-font-signature:0 0 0 0 0 0;} @font-face {font-family:Times; panose-1:2 2 6 3 5 4 5 2 3 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:536881799 -2147483648 8 0 511 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} a:link, span.MsoHyperlink {mso-style-unhide:no; color:blue; text-decoration:underline; text-underline:single;} a:visited, span.MsoHyperlinkFollowed {mso-style-unhide:no; color:blue; text-decoration:underline; text-underline:single;} p {mso-style-unhide:no; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-bidi-font-family:"Times New Roman";} span.SpellE {mso-style-name:""; mso-spl-e:yes;} span.GramE {mso-style-name:""; mso-gram-e:yes;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt;} @page WordSection1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.WordSection1 {page:WordSection1;} /* List Definitions */ @list l0 {mso-list-id:47607675; mso-list-template-ids:40119888;} @list l0:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l0:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1 {mso-list-id:202713231; mso-list-template-ids:1886444684;} @list l1:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l1:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2 {mso-list-id:721179252; mso-list-template-ids:-40043754;} @list l2:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l2:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3 {mso-list-id:804541954; mso-list-template-ids:-1277767832;} @list l3:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l3:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4 {mso-list-id:1346900452; mso-list-template-ids:597450756;} @list l4:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l4:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5 {mso-list-id:1410735043; mso-list-template-ids:1773587618;} @list l5:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l5:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6 {mso-list-id:1591305355; mso-list-template-ids:126377194;} @list l6:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l6:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7 {mso-list-id:1782993380; mso-list-template-ids:-1159289446;} @list l7:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l7:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8 {mso-list-id:2091542385; mso-list-template-ids:1424630416;} @list l8:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l8:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9 {mso-list-id:2109152583; mso-list-template-ids:-1010818392;} @list l9:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l9:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} ol {margin-bottom:0in;} ul {margin-bottom:0in;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin:0in; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";} </style> <![endif]--> <meta name=Title content="CS 542: Project Description"> <meta name=Keywords content=""> <!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="1026"/> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--> </head> <body bgcolor=white lang=EN-US link=blue vlink=blue style='tab-interval:.5in'> <div class=WordSection1> <p class=MsoNormal style='margin-bottom:10.0pt'><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'>&nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>CS542 -- Project Description </span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Implement Centralized Two Phase Locking<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Local <span class=SpellE>vs</span> Global Transactions in Optimistic CC<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Replicated Copy Control: Correct Read-From Precedence<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Adaptability<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Semantics<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Three Phase Commit Protocol<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Site Failure/Network Partitions<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Fail-Locks and Database Recovery<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Detection of Network Partitions<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Peer-to-Peer Multimedia Distribution <o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l6 level1 lfo1; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Verifying Data Integrity in Peer-to-Peer Video Streaming<o:p></o:p></span></li> </ul> <p class=MsoNormal><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>1. Implement Centralized Two Phase Locking (2PL)</span></b><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will implement the centralized 2PL (Global 2PL) approach to Concurrency Control and be able to detect/resolve deadlocks. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You may use Centralized Control for global decisions. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will generate at least three sites; you will maintain a lock table and a wait-for (dependency graph) at one site! <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>This means that all transactions arriving at different sites are sent to the centralized site. Queues for requesting /releasing locks will be maintained at this site. Processing must take place at the site where transaction is submitted. Locks will be released after waiting on the database at Centralized site. Updates for other sites will be sent (we assume fully replicated database) and they may arrive in different order. Your program must ensure that all updates at all sites are posted in the same order. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You may implement the algorithm of section 11.3.1 on page 318 of our text book (<span class=SpellE>Ozsu</span>) or a variation of it. <br> &nbsp; <br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>2. Local <span class=SpellE>vs</span> Global Transactions in Optimistic CC</span></b><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>More details are available in the note I handed out in class and a paper <i style='mso-bidi-font-style: normal'>Resilient Concurrency Control in Distributed Database Systems </i>present in the<i style='mso-bidi-font-style:normal'> </i>Chapter 10 of Prof. <span class=SpellE>Bhargava's</span> book (on reserve in Math library). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will implement the optimistic approach to concurrency control and maintain the data structures. <br> &nbsp; <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l7 level1 lfo2; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Dynamic conflict graph.<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l7 level1 lfo2; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Set of committed, semi committed and other active transactions.<o:p></o:p></span></li> </ul> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> You will do local and global validation for each transaction. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will send to a site, a mix of local transactions (that require and update at only this site) and global transaction <br> (that require an update on all copes). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will generate at least three sites and maintain a list of logical objects and directory of copies as in <i style='mso-bidi-font-style:normal'>Site Recovery in Replicated Distributed Database Systems</i> description (Chapter 11 of Prof. <span class=SpellE>Bhargava's</span> book. <span class=SpellE><span class=GramE>Its</span></span> on reserve in Math library). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You may assume that no failures occur in the system. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>One of the problems you will have to figure out is how to keep the list of committed transactions against which a global transaction must validate <b style='mso-bidi-font-weight:normal'>fixed</b> at each site without delaying the local transaction. <br> &nbsp; <br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>3. Replicated Copy Control: Correct Read-From Precedence</span></b><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>Transactions are validated and committed in the concurrency control server, while the database on different sites is posted by the I/O server (or access manager). There is an interval between the time of commit of a transaction <br> Ti, and the time of update by it on the database. During this interval, a new transaction can read an old value. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>For concurrency control, the new transaction is serialized after the commitment of Ti, while for accessing the database it is before Ti. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>The research and implementation question is: <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span class=GramE><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>a )</span></span><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'> How to eliminate this interval?, <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span class=GramE><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>and</span></span><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'> <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span class=GramE><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>b )</span></span><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'> How to establish the correct read-from relation for each pair of transactions for all servers on a site? <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You should design a policy (different than total blocking of the new transaction), and implement it. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will need to have at least two servers for each site. You need to generate at least two sites. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will need data structures that contain: <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>a) transaction id and time stamp of commit, <br> b) transaction id and time stamp of reading an object, <br> c) transaction id and time stamp of writing an object, <br> d) read-from relation for each transaction <span class=SpellE>w.r.t</span>. all other transactions (conflict graph). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will implement a protocol that will produce the same read-from relation for all transactions on each <span class=GramE>sites</span>. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You may be able to measure the delays caused by your policy. <br> &nbsp; <br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>4. Adaptability</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>More information is available in the paper ``<i style='mso-bidi-font-style:normal'>A Model for Adaptable Transaction Processing</i>'', in IEEE Transaction on Knowledge &amp; Data Engineering, December 1989 (Given as handout in the class). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will set up a data structure to capture the read/write set and time stamps for transactions that arrive on the site. This information will be used by three types of concurrency control; <br> &nbsp; <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l5 level1 lfo3; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>pessimistic time protocol,<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l5 level1 lfo3; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>optimistic time stamp protocol, and<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l5 level1 lfo3; tab-stops:list .5in'><span class=GramE><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'>locking</span></span><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt'> time stamp protocol.<o:p></o:p></span></li> </ul> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> You will output the <span class=SpellE>serializable</span> history as accepted by each of the above protocols. In addition you should be able to switch from one protocol to another. Certain conditions must be satisfied that are given in the technical report and need further study. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>For distributed concurrency control you may want to use the decentralized protocol of <span class=SpellE>Rosenkrantz</span>, <span class=SpellE>Stearn</span> and Lewis (ACM Transactions on Database Systems, June 1988). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will implement the <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>a) would-wait protocol, <br> b) wait-die protocol, <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span class=GramE><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>and</span></span><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'> should be able to switch among them. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>If you like, you may choose to adapt from distributed control to centralized control protocol or vice-versa. (This can be done for concurrency control as well as commit protocols.) <br> (Group project is possible.) <br> &nbsp; <br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>5. Semantics</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>The objective of this project is to identify semantics useful for concurrency control and/or recovery. The semantics will be provided by the user as a part of each transaction (e.g., breakpoints suggested by Lynch in ACM Transactions in Database Systems, December 1983, types of locks, <span class=SpellE>commutativity</span> of operation, user defined dependencies among transactions, types of objects and operations, etc.). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>The concurrency control protocol will use this semantics to serialize transactions and eliminate partial executions. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will need to implement a concurrency control method and change the transaction generator to add the semantics. <br> &nbsp; <br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>6. Three Phase Commit Protocol</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>More details are available in the Ph.D. thesis of Dale Skeen Chapter 5, Section 3, on page 102 of his paper (available from Prof. <span class=SpellE>Bhargava</span>). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>A minimum of three sites should be generated. Each site will contain data structures: <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l9 level1 lfo4; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>To maintain the status (commit, abort, wait, etc.) for each transaction as determined by this site.<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l9 level1 lfo4; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Global decision of all sites on every transaction.<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l9 level1 lfo4; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Up/Down status of sites.<o:p></o:p></span></li> </ul> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> Your program will initiate rounds of messages to terminate or commit a transaction and update the data structures. After two or three rounds, a decision will be made for the transaction. You will initiate transactions at each site. You will also simulate failures of different types. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You do not have to update the database. <br> &nbsp; <br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>7a. Site Failure in Partially Replicated Database</span></b><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>More details are available in the paper &quot;<i style='mso-bidi-font-style:normal'>Site Recovery in Replicated Distributed Database Systems&quot;</i>, 6th IEEE Distributed Computing Systems Conference, May 1986 (also Chapter 11 of Prof. <span class=SpellE>Bhargava's</span> book on reserve in Math library). <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will implement the protocol ``Read one copy, write all available copies.'' <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>A minimum of three sites should be generated. Each site will contain data structures for: <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l8 level1 lfo5; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>actual session number,<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l8 level1 lfo5; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>session vector,<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l8 level1 lfo5; tab-stops:list .5in'><span class=GramE><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'>logical</span></span><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt'> objects (at least five) and a directory for replicated copies.<o:p></o:p></span></li> </ul> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> Transactions will arrive at each site. A copy will be read from this site or another site that is up and contains a copy. All copies at up sites will be update. The up/down status is determined by session vector. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will simulate the up/down status of sites. You may assume initially that at least one site is always up. You will use a control transaction to announce the failure. You will recover a site by updating the data structures <span class=SpellE>correctly<span class=GramE>,and</span></span> will announce the recovery via another control transaction. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>Initially you do not have to worry about recovering the database. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>(Note that reading or writing of database will be simulated. <br> The data structures will be updated in reality.) <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>7b. Network Partitions (Two Partitions)</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>Several protocols are given in Chapter 1 of Prof. <span class=SpellE>Bhargava's</span> book (on <span class=SpellE>reserver</span> in Math library) to deal with this problem. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You would need to implement an optimistic or a pessimistic approach. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>For the pessimistic approach, you may read the technical report &quot;<i style='mso-bidi-font-style: normal'>Maintaining Mutual Consistency of Replicated Files in Partitioned Distributed Database System&quot;</i>, which is available from Prof. <span class=SpellE>Bhargava</span>. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will need to make several data structures: <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l3 level1 lfo6; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>partition graph,<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l3 level1 lfo6; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>site name vector,<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l3 level1 lfo6; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>linear order vector,<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l3 level1 lfo6; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>version number for each object, and<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l3 level1 lfo6; tab-stops:list .5in'><span class=GramE><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'>marker</span></span><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt'> vector.<o:p></o:p></span></li> </ul> <p class=MsoNormal><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will generate at least three sites. You will maintain a set of logical files and a directory of <br> physical copies (it could be the same as site name vector). You will simulate two partitions. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>(Note: You will not do any actual reading or writing of files for any transaction.) <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>You will implement the following procedures: <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l2 level1 lfo7; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>ISMAJORITY<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l2 level1 lfo7; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>PARTITION<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l2 level1 lfo7; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>RESOLVE<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l2 level1 lfo7; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>MERGE<o:p></o:p></span></li> </ul> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> These procedures will allow you to do all the necessary work to deal with transaction processing during network partitions. <br> &nbsp; <br> &nbsp; <o:p></o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>8. Fail Locks and Database Recovery (Multiple Failures)</span></b><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>(See notes for site failure in partially replicated database.) <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>Instead of recovering the site, you will concentrate on ensuring that the database is fully recovered at the failed site. The operational sites will maintain fail-locks (for each failed site) on copies that are updated. The recovering site will collect fail-lock table from each site and mark the corresponding data-items as unavailable. It will allow processing of transactions on other data items. If any site is down, you will maintain the fail-lock table on the <br> recovered site if any other site is down. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>The unavailable data-items will become available by one of the two approaches: <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l1 level1 lfo8; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Copier transactions (initiated by system).<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l1 level1 lfo8; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>An update from an operational site with up-to-date copy and a read request on the site with unavailable copy.<o:p></o:p></span></li> </ul> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> We may be able to measure by simulating the time it takes to make all unavailable copies up-to-date. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p>&nbsp;</o:p></span></p> <p class=MsoNormal align=center style='text-align:center'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>&nbsp;</span><b><span style='font-size:16.0pt;mso-bidi-font-size:10.0pt'>9.&nbsp; Peer-to-Peer Multimedia Distribution</span></b><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> Most of the contents distributed over the current P2P systems such as <span class=SpellE>Kazaa</span><span class=GramE>&nbsp; and</span> Gnutella are multimedia files, e.g., music files and videos.&nbsp; Nonetheless, current systems distribute these multimedia files<span class=GramE>&nbsp; using</span> bulk-file download, which does not consider the time inter-dependency among different segments of a multimedia file. This means that a client<span class=GramE>&nbsp; has</span> to download the <i>entire</i> file before starting&nbsp; playing it out.&nbsp; Consider for example, a one-hour movie recorded at 1 Mb/s, and<span class=GramE>&nbsp; being</span> downloaded by a client with an in-bound bandwidth of 1.5 Mb/s.&nbsp; Ignoring all protocols overhead and retransmissions, the client<span class=GramE>&nbsp; will</span> have to wait for 40 minutes to start watching the movie! <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>In this project, you will develop a real-time media streaming<span class=GramE>&nbsp; system</span> on top of a P2P lookup service. You can use any lookup service<span class=GramE>&nbsp; you</span> want. Examples include, JXTA<span class=GramE>&nbsp; (</span>jxta.org), Gnutella, and <span class=SpellE>FreePastry</span>.&nbsp;&nbsp; The real-time streaming system will start playing out the requested movie after a short (e.g., order of seconds) waiting period. For more information, check the<span class=GramE>&nbsp; paper</span> co-authored&nbsp; by professor <span class=SpellE>Bhargava</span> and available at&nbsp; (<a href="http://www.cs.purdue.edu/homes/bb/jmms03.pdf">http://www.cs.purdue.edu/homes/bb/jmms03.pdf</a>).&nbsp; <br> <br> You should do the following: <o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l4 level1 lfo9; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Use the lookup service to return multiple suppliers for a client. <o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l4 level1 lfo9; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Choose a subset of them and assign streaming rates and different data segments to each. <o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l4 level1 lfo9; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>At the client, re-assemble (in real-time) and put the contiguous<span class=GramE>&nbsp; data</span> in the player's buffer. You may use the Berkeley's mpeg player to<span class=GramE>&nbsp; play</span> out the media file while streaming.&nbsp;<o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l4 level1 lfo9; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Adapt to failures: if a supplier fails, you need to replace it with<span class=GramE>&nbsp; another</span> one from the set of backup suppliers. Then, redistribute rates and resume streaming. <o:p></o:p></span></li> </ul> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> A minimum of four sites (a client and at least two senders<span class=GramE>&nbsp; concurrently</span> sending and one backup) are required. <br> <br> If interested, first read the above paper. Then, discuss with the TA<span class=GramE>&nbsp; your</span> ideas and the scope of the project. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p>&nbsp;</o:p></span></p> <p align=center style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt; margin-left:0in;text-align:center'><b><span style='font-size:16.0pt;mso-bidi-font-size: 10.0pt'>10.&nbsp;&nbsp; Verifying Data Integrity in Peer-to-Peer Video Streaming</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>In P2P video streaming, multiple senders serve one client. Each sender provides different segments of the video. The segments are assembled and ordered by the client.&nbsp; A major concern in the P2P environment is whether a peer provides genuine data. If a peer provides corrupt data, it severely impact the quality of the streaming session. In this project you will implement distributed data verification protocols in P2P environment.&nbsp; The verification protocol has to run in real-time, i.e., during the streaming session. Two data verification protocols are proposed in the following paper:&nbsp; <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span class=SpellE><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt; color:black'>Ahsan</span></span><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt;color:black'> <span class=SpellE>Habib</span>, <span class=SpellE>Dongyan</span> <span class=SpellE>Xu</span>, Mikhail <span class=SpellE>Atallah</span>, Bharat <span class=SpellE>Bhargava</span>, &quot;<a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=240BBF3DABABA2F6D134D4E691EB6D22?doi=10.1.1.84.3579&amp;rep=rep1&amp;type=pdf">Verifying Data Integrity in Peer-to-Peer Video Streaming</a>,&quot; CERIAS TR 2002-39, Purdue University, Revised 2003, submitted for review.<o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><br> You should do the following:<o:p></o:p></span></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l0 level1 lfo10; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Read the above paper carefully. <o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l0 level1 lfo10; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Then, choose one of the protocols: (1) One Time Digest Protocol (OTDP) or<span class=GramE>&nbsp; (</span>2) Tree-based Forward Digest Protocol (TFDP). Implement the protocol and test it. <o:p></o:p></span></li> <li class=MsoNormal style='margin-top:.1pt;margin-bottom:.1pt;mso-list:l0 level1 lfo10; tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt'>Perform some experimental study (similar to those proposed in the paper). <o:p></o:p></span></li> </ul> <p class=MsoNormal><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p>&nbsp;</o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>A minimum of four<span class=GramE>&nbsp; sites</span> (a client and at three senders) are required. <br> If interested, first read the above paper. Then, discuss with the TA<span class=GramE>&nbsp; your</span> ideas and the scope of the project. <o:p></o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p>&nbsp;</o:p></span></p> <p style='margin-top:.1pt;margin-right:0in;margin-bottom:.1pt;margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p>&nbsp;</o:p></span></p> </div> </body> </html>