rinri
/
distributed-and-network-programming-course
1
0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1 Commit
1 Branch
2.1 MiB
 
 
 
Branch: master
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'master'
${ noResults }
distributed-and-network-pro.../lab5/Week 5.html

386 lines
63 KiB
Raw Permalink Blame History 

  1. <!DOCTYPE html>

  2. 

  3. <html lang="en">

  4. 

  5. <head>

  6.     <meta charset="utf-8">

  7.     <meta http-equiv="X-UA-Compatible" content="IE=edge">

  8.     <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">

  9.     <meta name="apple-mobile-web-app-capable" content="yes">

  10.     <meta name="apple-mobile-web-app-status-bar-style" content="black">

  11.     <meta name="mobile-web-app-capable" content="yes">

  12.     <title>

  13.         Week 5 - Distributed Hash Tables - HackMD

  14.     </title>

  15.     <link rel="icon" type="image/png" href="https://hackmd.io/favicon.png">

  16.     <link rel="apple-touch-icon" href="https://hackmd.io/apple-touch-icon.png">

  17. 

  18.     <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/3.3.7/css/bootstrap.min.css" integrity="sha256-916EbMg70RQy9LHiGkXzG8hSg9EdNy97GazNG/aiY1w=" crossorigin="anonymous" />

  19.     <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css" integrity="sha256-eZrrJcwDc/3uDhsdt61sL2oOBY362qM3lon1gyExkL0=" crossorigin="anonymous" />

  20.     <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/ionicons/2.0.1/css/ionicons.min.css" integrity="sha256-3iu9jgsy9TpTwXKb7bNQzqWekRX7pPK+2OLj3R922fo=" crossorigin="anonymous" />

  21.     <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/octicons/3.5.0/octicons.min.css" integrity="sha256-QiWfLIsCT02Sdwkogf6YMiQlj4NE84MKkzEMkZnMGdg=" crossorigin="anonymous" />

  22.     <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.5.1/themes/prism.min.css" integrity="sha256-vtR0hSWRc3Tb26iuN2oZHt3KRUomwTufNIf5/4oeCyg=" crossorigin="anonymous" />

  23.     <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@hackmd/emojify.js@2.1.0/dist/css/basic/emojify.min.css" integrity="sha256-UOrvMOsSDSrW6szVLe8ZDZezBxh5IoIfgTwdNDgTjiU=" crossorigin="anonymous" />

  24.     <style>

  25.         @import url(https://fonts.googleapis.com/css?family=Roboto:300,300i,400,400i,500,500i|Source+Code+Pro:300,400,500|Source+Sans+Pro:300,300i,400,400i,600,600i|Source+Serif+Pro&subset=latin-ext);.hljs{background:#fff;color:#333;display:block;overflow-x:auto;padding:.5em}.hljs-comment,.hljs-meta{color:#969896}.hljs-emphasis,.hljs-quote,.hljs-string,.hljs-strong,.hljs-template-variable,.hljs-variable{color:#df5000}.hljs-keyword,.hljs-selector-tag,.hljs-type{color:#a71d5d}.hljs-attribute,.hljs-bullet,.hljs-literal,.hljs-number,.hljs-symbol{color:#0086b3}.hljs-built_in,.hljs-builtin-name{color:#005cc5}.hljs-name,.hljs-section{color:#63a35c}.hljs-tag{color:#333}.hljs-attr,.hljs-selector-attr,.hljs-selector-class,.hljs-selector-id,.hljs-selector-pseudo,.hljs-title{color:#795da3}.hljs-addition{background-color:#eaffea;color:#55a532}.hljs-deletion{background-color:#ffecec;color:#bd2c00}.hljs-link{text-decoration:underline}.markdown-body{word-wrap:break-word;font-size:16px;line-height:1.5}.markdown-body:after,.markdown-body:before{content:"";display:table}.markdown-body:after{clear:both}.markdown-body>:first-child{margin-top:0!important}.markdown-body>:last-child{margin-bottom:0!important}.markdown-body a:not([href]){color:inherit;text-decoration:none}.markdown-body .absent{color:#c00}.markdown-body .anchor{float:left;line-height:1;margin-left:-20px;padding-right:4px}.markdown-body .anchor:focus{outline:none}.markdown-body blockquote,.markdown-body dl,.markdown-body ol,.markdown-body p,.markdown-body pre,.markdown-body table,.markdown-body ul{margin-bottom:16px;margin-top:0}.markdown-body hr{background-color:#e7e7e7;border:0;height:.25em;margin:24px 0;padding:0}.markdown-body blockquote{border-left:.25em solid #ddd;color:#777;font-size:16px;padding:0 1em}.markdown-body blockquote>:first-child{margin-top:0}.markdown-body blockquote>:last-child{margin-bottom:0}.markdown-body kbd,.popover kbd{background-color:#fcfcfc;border:1px solid;border-color:#ccc #ccc #bbb;border-radius:3px;box-shadow:inset 0 -1px 0 #bbb;color:#555;display:inline-block;font-size:11px;line-height:10px;padding:3px 5px;vertical-align:middle}.markdown-body .loweralpha{list-style-type:lower-alpha}.markdown-body h1,.markdown-body h2,.markdown-body h3,.markdown-body h4,.markdown-body h5,.markdown-body h6{font-weight:600;line-height:1.25;margin-bottom:16px;margin-top:24px}.markdown-body h1 .octicon-link,.markdown-body h2 .octicon-link,.markdown-body h3 .octicon-link,.markdown-body h4 .octicon-link,.markdown-body h5 .octicon-link,.markdown-body h6 .octicon-link{color:#000;vertical-align:middle;visibility:hidden}.markdown-body h1:hover .anchor,.markdown-body h2:hover .anchor,.markdown-body h3:hover .anchor,.markdown-body h4:hover .anchor,.markdown-body h5:hover .anchor,.markdown-body h6:hover .anchor{text-decoration:none}.markdown-body h1:hover .anchor .octicon-link,.markdown-body h2:hover .anchor .octicon-link,.markdown-body h3:hover .anchor .octicon-link,.markdown-body h4:hover .anchor .octicon-link,.markdown-body h5:hover .anchor .octicon-link,.markdown-body h6:hover .anchor .octicon-link{visibility:visible}.markdown-body h1 code,.markdown-body h1 tt,.markdown-body h2 code,.markdown-body h2 tt,.markdown-body h3 code,.markdown-body h3 tt,.markdown-body h4 code,.markdown-body h4 tt,.markdown-body h5 code,.markdown-body h5 tt,.markdown-body h6 code,.markdown-body h6 tt{font-size:inherit}.markdown-body h1{font-size:2em}.markdown-body h1,.markdown-body h2{border-bottom:1px solid #eee;padding-bottom:.3em}.markdown-body h2{font-size:1.5em}.markdown-body h3{font-size:1.25em}.markdown-body h4{font-size:1em}.markdown-body h5{font-size:.875em}.markdown-body h6{color:#777;font-size:.85em}.markdown-body ol,.markdown-body ul{padding-left:2em}.markdown-body ol.no-list,.markdown-body ul.no-list{list-style-type:none;padding:0}.markdown-body ol ol,.markdown-body ol ul,.markdown-body ul ol,.markdown-body ul ul{margin-bottom:0;margin-top:0}.markdown-body li>p{margin-top:16px}.markdown-body li+li{padding-top:.25em}.markdown-body dl{padding:0}.markdown-body dl dt{font-size:1em;font-style:italic;font-weight:700;margin-top:16px;padding:0}.markdown-body dl dd{margin-bottom:16px;padding:0 16px}.markdown-body table{display:block;overflow:auto;width:100%;word-break:normal;word-break:keep-all}.markdown-body table th{font-weight:700}.markdown-body table td,.markdown-body table th{border:1px solid #ddd;padding:6px 13px}.markdown-body table tr{background-color:#fff;border-top:1px solid #ccc}.markdown-body table tr:nth-child(2n){background-color:#f8f8f8}.markdown-body img{background-color:#fff;box-sizing:initial;max-width:100%}.markdown-body img[align=right]{padding-left:20px}.markdown-body img[align=left]{padding-right:20px}.markdown-body .emoji{background-color:initial;max-width:none;vertical-align:text-top}.markdown-body span.frame{display:block;overflow:hidden}.markdown-body span.frame>span{border:1px solid #ddd;display:block;float:left;margin:13px 0 0;overflow:hidden;padding:7px;width:auto}.markdown-body span.frame span img{display:block;float:left}.markdown-body span.frame span span{clear:both;color:#333;display:block;padding:5px 0 0}.markdown-body span.align-center{clear:both;display:block;overflow:hidden}.markdown-body span.align-center>span{display:block;margin:13px auto 0;overflow:hidden;text-align:center}.markdown-body span.align-center span img{margin:0 auto;text-align:center}.markdown-body span.align-right{clear:both;display:block;overflow:hidden}.markdown-body span.align-right>span{display:block;margin:13px 0 0;overflow:hidden;text-align:right}.markdown-body span.align-right span img{margin:0;text-align:right}.markdown-body span.float-left{display:block;float:left;margin-right:13px;overflow:hidden}.markdown-body span.float-left span{margin:13px 0 0}.markdown-body span.float-right{display:block;float:right;margin-left:13px;overflow:hidden}.markdown-body span.float-right>span{display:block;margin:13px auto 0;overflow:hidden;text-align:right}.markdown-body code,.markdown-body tt{background-color:#0000000a;border-radius:3px;font-size:85%;margin:0;padding:.2em 0}.markdown-body code:after,.markdown-body code:before,.markdown-body tt:after,.markdown-body tt:before{content:"\00a0";letter-spacing:-.2em}.markdown-body code br,.markdown-body tt br{display:none}.markdown-body del code{text-decoration:inherit}.markdown-body pre{word-wrap:normal}.markdown-body pre>code{background:#0000;border:0;font-size:100%;margin:0;padding:0;white-space:pre;word-break:normal}.markdown-body .highlight{margin-bottom:16px}.markdown-body .highlight pre{margin-bottom:0;word-break:normal}.markdown-body .highlight pre,.markdown-body pre{background-color:#f7f7f7;border-radius:3px;font-size:85%;line-height:1.45;overflow:auto;padding:16px}.markdown-body pre code,.markdown-body pre tt{word-wrap:normal;background-color:initial;border:0;display:inline;line-height:inherit;margin:0;max-width:auto;overflow:visible;padding:0}.markdown-body pre code:after,.markdown-body pre code:before,.markdown-body pre tt:after,.markdown-body pre tt:before{content:normal}.markdown-body .csv-data td,.markdown-body .csv-data th{font-size:12px;line-height:1;overflow:hidden;padding:5px;text-align:left;white-space:nowrap}.markdown-body .csv-data .blob-line-num{background:#fff;border:0;padding:10px 8px 9px;text-align:right}.markdown-body .csv-data tr{border-top:0}.markdown-body .csv-data th{background:#f8f8f8;border-top:0;font-weight:700}.news .alert .markdown-body blockquote{border:0;padding:0 0 0 40px}.activity-tab .news .alert .commits,.activity-tab .news .markdown-body blockquote{padding-left:0}.task-list-item{list-style-type:none}.task-list-item label{font-weight:400}.task-list-item.enabled label{cursor:pointer}.task-list-item+.task-list-item{margin-top:3px}.task-list-item-checkbox{cursor:default!important;float:left;margin:.31em 0 .2em -1.3em!important;vertical-align:middle}.markdown-body{max-width:758px;overflow:visible!important;padding-bottom:40px;padding-top:40px;position:relative}.markdown-body.next-editor{overflow-x:hidden!important}.markdown-body .emoji{vertical-align:top}.markdown-body pre{border:inherit!important}.markdown-body code{color:inherit!important}.markdown-body pre code .wrapper{display:-moz-inline-flex;display:-ms-inline-flex;display:-o-inline-flex;display:inline-flex}.markdown-body pre code .gutter{float:left;overflow:hidden;-webkit-user-select:none;user-select:none}.markdown-body pre code .gutter.linenumber{border-right:3px solid #6ce26c!important;box-sizing:initial;color:#afafaf!important;cursor:default;display:inline-block;min-width:20px;padding:0 8px 0 0;position:relative;text-align:right;z-index:4}.markdown-body pre code .gutter.linenumber>span:before{content:attr(data-linenumber)}.markdown-body pre code .code{float:left;margin:0 0 0 16px}.markdown-body .gist .line-numbers{border-bottom:none;border-left:none;border-top:none}.markdown-body .gist .line-data{border:none}.markdown-body .gist table{border-collapse:inherit!important;border-spacing:0}.markdown-body code[data-gist-id]{background:none;padding:0}.markdown-body code[data-gist-id]:after,.markdown-body code[data-gist-id]:before{content:""}.markdown-body code[data-gist-id] .blob-num{border:unset}.markdown-body code[data-gist-id] table{margin-bottom:unset;overflow:unset}.markdown-body code[data-gist-id] table tr{background:unset}.markdown-body[dir=rtl] pre{direction:ltr}.markdown-body[dir=rtl] code{direction:ltr;unicode-bidi:embed}.markdown-body .alert>p:last-child{margin-bottom:0}.markdown-body pre.abc,.markdown-body pre.flow-chart,.markdown-body pre.graphviz,.markdown-body pre.mermaid,.markdown-body pre.sequence-diagram,.markdown-body pre.vega{background-color:inherit;border-radius:0;overflow:visible;text-align:center;white-space:inherit}.markdown-body pre.abc>code,.markdown-body pre.flow-chart>code,.markdown-body pre.graphviz>code,.markdown-body pre.mermaid>code,.markdown-body pre.sequence-diagram>code,.markdown-body pre.vega>code{text-align:left}.markdown-body pre.abc>svg,.markdown-body pre.flow-chart>svg,.markdown-body pre.graphviz>svg,.markdown-body pre.mermaid>svg,.markdown-body pre.sequence-diagram>svg,.markdown-body pre.vega>svg{height:100%;max-width:100%}.markdown-body pre>code.wrap{word-wrap:break-word;white-space:pre-wrap;white-space:-moz-pre-wrap;white-space:-pre-wrap;white-space:-o-pre-wrap}.markdown-body .alert>p:last-child,.markdown-body .alert>ul:last-child{margin-bottom:0}.markdown-body summary{display:list-item}.markdown-body summary:focus{outline:none}.markdown-body details summary{cursor:pointer}.markdown-body details:not([open])>:not(summary){display:none}.markdown-body figure{margin:1em 40px}.markdown-body .mark,.markdown-body mark{background-color:#fff1a7}.vimeo,.youtube{background-color:#000;background-position:50%;background-repeat:no-repeat;background-size:contain;cursor:pointer;display:table;overflow:hidden;text-align:center}.vimeo,.youtube{position:relative;width:100%}.youtube{padding-bottom:56.25%}.vimeo img{object-fit:contain;width:100%;z-index:0}.youtube img{object-fit:cover;z-index:0}.vimeo iframe,.youtube iframe,.youtube img{height:100%;left:0;position:absolute;top:0;width:100%}.vimeo iframe,.youtube iframe{vertical-align:middle;z-index:1}.vimeo .icon,.youtube .icon{color:#fff;height:auto;left:50%;opacity:.3;position:absolute;top:50%;transform:translate(-50%,-50%);transition:opacity .2s;width:auto;z-index:0}.vimeo:hover .icon,.youtube:hover .icon{opacity:.6;transition:opacity .2s}.slideshare .inner,.speakerdeck .inner{position:relative;width:100%}.slideshare .inner iframe,.speakerdeck .inner iframe{bottom:0;height:100%;left:0;position:absolute;right:0;top:0;width:100%}.figma{display:table;padding-bottom:56.25%;position:relative;width:100%}.figma iframe{border:1px solid #eee;bottom:0;height:100%;left:0;position:absolute;right:0;top:0;width:100%}.markmap-container{height:300px}.markmap-container>svg{height:100%;width:100%}.MJX_Assistive_MathML{display:none}#MathJax_Message{z-index:1000!important}.ui-infobar{color:#777;margin:25px auto -25px;max-width:760px;position:relative;z-index:2}.toc .invisable-node{list-style-type:none}.ui-toc{bottom:20px;position:fixed;z-index:998}.ui-toc.both-mode{margin-left:8px}.ui-toc.both-mode .ui-toc-label{border-bottom-left-radius:0;border-top-left-radius:0;height:40px;padding:10px 4px}.ui-toc-label{background-color:#e6e6e6;border:none;color:#868686;transition:opacity .2s}.ui-toc .open .ui-toc-label{color:#fff;opacity:1;transition:opacity .2s}.ui-toc-label:focus{background-color:#ccc;color:#000;opacity:.3}.ui-toc-label:hover{background-color:#ccc;opacity:1;transition:opacity .2s}.ui-toc-dropdown{margin-bottom:20px;margin-top:20px;max-height:70vh;max-width:45vw;overflow:auto;padding-left:10px;padding-right:10px;text-align:inherit;width:25vw}.ui-toc-dropdown>.toc{max-height:calc(70vh - 100px);overflow:auto}.ui-toc-dropdown[dir=rtl] .nav{letter-spacing:.0029em;padding-right:0}.ui-toc-dropdown a{overflow:hidden;text-overflow:ellipsis;white-space:pre}.ui-toc-dropdown .nav>li>a{color:#767676;display:block;font-size:13px;font-weight:500;padding:4px 20px}.ui-toc-dropdown .nav>li:first-child:last-child>ul,.ui-toc-dropdown .toc.expand ul{display:block}.ui-toc-dropdown .nav>li>a:focus,.ui-toc-dropdown .nav>li>a:hover{background-color:initial;border-left:1px solid #000;color:#000;padding-left:19px;text-decoration:none}.ui-toc-dropdown[dir=rtl] .nav>li>a:focus,.ui-toc-dropdown[dir=rtl] .nav>li>a:hover{border-left:none;border-right:1px solid #000;padding-right:19px}.ui-toc-dropdown .nav>.active:focus>a,.ui-toc-dropdown .nav>.active:hover>a,.ui-toc-dropdown .nav>.active>a{background-color:initial;border-left:2px solid #000;color:#000;font-weight:700;padding-left:18px}.ui-toc-dropdown[dir=rtl] .nav>.active:focus>a,.ui-toc-dropdown[dir=rtl] .nav>.active:hover>a,.ui-toc-dropdown[dir=rtl] .nav>.active>a{border-left:none;border-right:2px solid #000;padding-right:18px}.ui-toc-dropdown .nav .nav{display:none;padding-bottom:10px}.ui-toc-dropdown .nav>.active>ul{display:block}.ui-toc-dropdown .nav .nav>li>a{font-size:12px;font-weight:400;padding-bottom:1px;padding-left:30px;padding-top:1px}.ui-toc-dropdown[dir=rtl] .nav .nav>li>a{padding-right:30px}.ui-toc-dropdown .nav .nav>li>ul>li>a{font-size:12px;font-weight:400;padding-bottom:1px;padding-left:40px;padding-top:1px}.ui-toc-dropdown[dir=rtl] .nav .nav>li>ul>li>a{padding-right:40px}.ui-toc-dropdown .nav .nav>li>a:focus,.ui-toc-dropdown .nav .nav>li>a:hover{padding-left:29px}.ui-toc-dropdown[dir=rtl] .nav .nav>li>a:focus,.ui-toc-dropdown[dir=rtl] .nav .nav>li>a:hover{padding-right:29px}.ui-toc-dropdown .nav .nav>li>ul>li>a:focus,.ui-toc-dropdown .nav .nav>li>ul>li>a:hover{padding-left:39px}.ui-toc-dropdown[dir=rtl] .nav .nav>li>ul>li>a:focus,.ui-toc-dropdown[dir=rtl] .nav .nav>li>ul>li>a:hover{padding-right:39px}.ui-toc-dropdown .nav .nav>.active:focus>a,.ui-toc-dropdown .nav .nav>.active:hover>a,.ui-toc-dropdown .nav .nav>.active>a{font-weight:500;padding-left:28px}.ui-toc-dropdown[dir=rtl] .nav .nav>.active:focus>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active:hover>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active>a{padding-right:28px}.ui-toc-dropdown .nav .nav>.active>.nav>.active:focus>a,.ui-toc-dropdown .nav .nav>.active>.nav>.active:hover>a,.ui-toc-dropdown .nav .nav>.active>.nav>.active>a{font-weight:500;padding-left:38px}.ui-toc-dropdown[dir=rtl] .nav .nav>.active>.nav>.active:focus>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active>.nav>.active:hover>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active>.nav>.active>a{padding-right:38px}.markdown-body{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Helvetica,Roboto,Arial,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol}html[lang^=ja] .markdown-body{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Helvetica,Roboto,Arial,Hiragino Kaku Gothic Pro,ヒラギノ角ゴ Pro W3,Osaka,Meiryo,メイリオ,MS Gothic,ＭＳ ゴシック,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol}html[lang=zh-tw] .markdown-body{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Helvetica,Roboto,Arial,PingFang TC,Microsoft JhengHei,微軟正黑,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol}html[lang=zh-cn] .markdown-body{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Helvetica,Roboto,Arial,PingFang SC,Microsoft YaHei,微软雅黑,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol}html .markdown-body[lang^=ja]{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Helvetica,Roboto,Arial,Hiragino Kaku Gothic Pro,ヒラギノ角ゴ Pro W3,Osaka,Meiryo,メイリオ,MS Gothic,ＭＳ ゴシック,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol}html .markdown-body[lang=zh-tw]{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Helvetica,Roboto,Arial,PingFang TC,Microsoft JhengHei,微軟正黑,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol}html .markdown-body[lang=zh-cn]{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Helvetica,Roboto,Arial,PingFang SC,Microsoft YaHei,微软雅黑,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol}html[lang^=ja] .ui-toc-dropdown{font-family:Source Sans Pro,Helvetica,Arial,Meiryo UI,MS PGothic,ＭＳ Ｐゴシック,sans-serif}html[lang=zh-tw] .ui-toc-dropdown{font-family:Source Sans Pro,Helvetica,Arial,Microsoft JhengHei UI,微軟正黑UI,sans-serif}html[lang=zh-cn] .ui-toc-dropdown{font-family:Source Sans Pro,Helvetica,Arial,Microsoft YaHei UI,微软雅黑UI,sans-serif}html .ui-toc-dropdown[lang^=ja]{font-family:Source Sans Pro,Helvetica,Arial,Meiryo UI,MS PGothic,ＭＳ Ｐゴシック,sans-serif}html .ui-toc-dropdown[lang=zh-tw]{font-family:Source Sans Pro,Helvetica,Arial,Microsoft JhengHei UI,微軟正黑UI,sans-serif}html .ui-toc-dropdown[lang=zh-cn]{font-family:Source Sans Pro,Helvetica,Arial,Microsoft YaHei UI,微软雅黑UI,sans-serif}.ui-affix-toc{max-height:70vh;max-width:15vw;overflow:auto;position:fixed;top:0}.back-to-top,.expand-toggle,.go-to-bottom{color:#999;display:block;font-size:12px;font-weight:500;margin-left:10px;margin-top:10px;padding:4px 10px}.back-to-top:focus,.back-to-top:hover,.expand-toggle:focus,.expand-toggle:hover,.go-to-bottom:focus,.go-to-bottom:hover{color:#563d7c;text-decoration:none}.back-to-top,.go-to-bottom{margin-top:0}.ui-user-icon{background-position:50%;background-repeat:no-repeat;background-size:cover;border-radius:50%;display:block;height:20px;margin-bottom:2px;margin-right:5px;margin-top:2px;width:20px}.ui-user-icon.small{display:inline-block;height:18px;margin:0 0 .2em;vertical-align:middle;width:18px}.ui-infobar>small>span{line-height:22px}.ui-infobar>small .dropdown{display:inline-block}.ui-infobar>small .dropdown a:focus,.ui-infobar>small .dropdown a:hover{text-decoration:none}.ui-more-info{color:#888;cursor:pointer;vertical-align:middle}.ui-more-info .fa{font-size:16px}.ui-connectedGithub,.ui-published-note{color:#888}.ui-connectedGithub{line-height:23px;white-space:nowrap}.ui-connectedGithub a.file-path{color:#888;padding-left:22px;text-decoration:none}.ui-connectedGithub a.file-path:active,.ui-connectedGithub a.file-path:hover{color:#888;text-decoration:underline}.ui-connectedGithub .fa{font-size:20px}.ui-published-note .fa{font-size:20px;vertical-align:top}.unselectable{-webkit-user-select:none;-o-user-select:none;user-select:none}.selectable{-webkit-user-select:text;-o-user-select:text;user-select:text}.inline-spoiler-section{cursor:pointer}.inline-spoiler-section .spoiler-text{background-color:#333;border-radius:2px}.inline-spoiler-section .spoiler-text>*{opacity:0}.inline-spoiler-section .spoiler-img{filter:blur(10px)}.inline-spoiler-section.raw{background-color:#333;border-radius:2px}.inline-spoiler-section.raw>*{opacity:0}.inline-spoiler-section.unveil{cursor:auto}.inline-spoiler-section.unveil .spoiler-text{background-color:#3333331a}.inline-spoiler-section.unveil .spoiler-text>*{opacity:1}.inline-spoiler-section.unveil .spoiler-img{filter:none}@media print{blockquote,div,img,pre,table{page-break-inside:avoid!important}a[href]:after{font-size:12px!important}}.markdown-body.slides{color:#222;position:relative;z-index:1}.markdown-body.slides:before{background-color:currentColor;bottom:0;box-shadow:0 0 0 50vw;content:"";display:block;left:0;position:absolute;right:0;top:0;z-index:-1}.markdown-body.slides section[data-markdown]{background-color:#fff;margin-bottom:1.5em;position:relative;text-align:center}.markdown-body.slides section[data-markdown] code{text-align:left}.markdown-body.slides section[data-markdown]:before{content:"";display:block;padding-bottom:56.23%}.markdown-body.slides section[data-markdown]>div:first-child{left:1em;max-height:100%;overflow:hidden;position:absolute;right:1em;top:50%;transform:translateY(-50%)}.markdown-body.slides section[data-markdown]>ul{display:inline-block}.markdown-body.slides>section>section+section:after{border:3px solid #777;content:"";height:1.5em;position:absolute;right:1em;top:-1.5em}.site-ui-font{font-family:Source Sans Pro,Helvetica,Arial,sans-serif}html[lang^=ja] .site-ui-font{font-family:Source Sans Pro,Helvetica,Arial,Hiragino Kaku Gothic Pro,ヒラギノ角ゴ Pro W3,Osaka,Meiryo,メイリオ,MS Gothic,ＭＳ ゴシック,sans-serif}html[lang=zh-tw] .site-ui-font{font-family:Source Sans Pro,Helvetica,Arial,PingFang TC,Microsoft JhengHei,微軟正黑,sans-serif}html[lang=zh-cn] .site-ui-font{font-family:Source Sans Pro,Helvetica,Arial,PingFang SC,Microsoft YaHei,微软雅黑,sans-serif}body{font-smoothing:subpixel-antialiased!important;-webkit-font-smoothing:subpixel-antialiased!important;-moz-osx-font-smoothing:auto!important;-webkit-overflow-scrolling:touch;font-family:Source Sans Pro,Helvetica,Arial,sans-serif;letter-spacing:.025em}html[lang^=ja] body{font-family:Source Sans Pro,Helvetica,Arial,Hiragino Kaku Gothic Pro,ヒラギノ角ゴ Pro W3,Osaka,Meiryo,メイリオ,MS Gothic,ＭＳ ゴシック,sans-serif}html[lang=zh-tw] body{font-family:Source Sans Pro,Helvetica,Arial,PingFang TC,Microsoft JhengHei,微軟正黑,sans-serif}html[lang=zh-cn] body{font-family:Source Sans Pro,Helvetica,Arial,PingFang SC,Microsoft YaHei,微软雅黑,sans-serif}abbr[title]{border-bottom:none;text-decoration:underline;-webkit-text-decoration:underline dotted;text-decoration:underline dotted}abbr[data-original-title],abbr[title]{cursor:help}body.modal-open{overflow-y:auto;padding-right:0!important}svg{text-shadow:none}

  26.     </style>

  27.     <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->

  28.     <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->

  29.     <!--[if lt IE 9]>

  30.     	<script src="https://cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv.min.js" integrity="sha256-3Jy/GbSLrg0o9y5Z5n1uw0qxZECH7C6OQpVBgNFYa0g=" crossorigin="anonymous"></script>

  31.     	<script src="https://cdnjs.cloudflare.com/ajax/libs/respond.js/1.4.2/respond.min.js" integrity="sha256-g6iAfvZp+nDQ2TdTR/VVKJf3bGro4ub5fvWSWVRi2NE=" crossorigin="anonymous"></script>

  32. 		<script src="https://cdnjs.cloudflare.com/ajax/libs/es5-shim/4.5.9/es5-shim.min.js" integrity="sha256-8E4Is26QH0bD52WoQpcB+R/tcWQtpzlCojrybUd7Mxo=" crossorigin="anonymous"></script>

  33.     <![endif]-->

  34. </head>

  35. 

  36. <body>

  37.     <div id="doc" class="markdown-body container-fluid comment-inner comment-enabled" data-hard-breaks="true"><h1 id="Week-5---Distributed-Hash-Tables" data-id="Week-5---Distributed-Hash-Tables"><a class="anchor hidden-xs" href="#Week-5---Distributed-Hash-Tables" title="Week-5---Distributed-Hash-Tables"><span class="octicon octicon-link"></span></a><span>Week 5 - Distributed Hash Tables</span></h1><blockquote>

  38. <p><span>Distributed Systems and Network Programming - Spring 2023</span></p>

  39. </blockquote><h2 id="Overview" data-id="Overview"><a class="anchor hidden-xs" href="#Overview" title="Overview"><span class="octicon octicon-link"></span></a><span>Overview</span></h2><p><span>Your task for this lab is to implement a simplified version of the </span><a href="https://en.wikipedia.org/wiki/Chord_(peer-to-peer)" target="_blank" rel="noopener"><span>Chord</span></a><span> algorithm used to maintain a Distributed Hash Table (DHT) in peer-to-peer systems</span></p><ul>

  40. <li><span>DHT is a regular dictionary (HashMap) in which entries (i.e., keys and their corresponding values) are distributed over multiple nodes (peers) based on the consistent hash of the key</span></li>

  41. <li><span>Nodes only support the two basic hash table operations: </span><code>get(key)</code><span> and </span><code>put(key, value)</code></li>

  42. </ul><h2 id="System-Architecture" data-id="System-Architecture"><a class="anchor hidden-xs" href="#System-Architecture" title="System-Architecture"><span class="octicon octicon-link"></span></a><span>System Architecture</span></h2><p><span>Chord operates over a structured P2P overlay network in which nodes (peers) are organized in a ring</span></p><ul>

  43. <li><span>Each node has an integer identifier: </span><span class="mathjax"><span class="MathJax_Preview" style="color: inherit;"></span><span id="MathJax-Element-1-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" style="font-size: 119%; position: relative;" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>n</mi><mo>&amp;#x2208;</mo><mo stretchy=&quot;false&quot;>[</mo><mn>0</mn><mo>,</mo><msup><mn>2</mn><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi>M</mi></mrow></msup><mo stretchy=&quot;false&quot;>)</mo></math>" role="presentation"><span id="MJXc-Node-1" class="mjx-math" aria-hidden="true"><span id="MJXc-Node-2" class="mjx-mrow"><span id="MJXc-Node-3" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">n</span></span><span id="MJXc-Node-4" class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.265em; padding-bottom: 0.37em;">∈</span></span><span id="MJXc-Node-5" class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">[</span></span><span id="MJXc-Node-6" class="mjx-mn"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.37em;">0</span></span><span id="MJXc-Node-7" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="margin-top: -0.155em; padding-bottom: 0.528em;">,</span></span><span id="MJXc-Node-8" class="mjx-msubsup MJXc-space1"><span class="mjx-base"><span id="MJXc-Node-9" class="mjx-mn"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.318em;">2</span></span></span><span class="mjx-sup" style="font-size: 70.7%; vertical-align: 0.591em; padding-left: 0px; padding-right: 0.071em;"><span id="MJXc-Node-10" class="mjx-texatom" style=""><span id="MJXc-Node-11" class="mjx-mrow"><span id="MJXc-Node-12" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.081em;">M</span></span></span></span></span></span><span id="MJXc-Node-13" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">)</span></span></span></span><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mi>M</mi></mrow></msup><mo stretchy="false">)</mo></math></span></span><script type="math/tex" id="MathJax-Element-1">n \in [0, 2^{M})</script></span><span>, where </span><span class="mathjax"><span class="MathJax_Preview" style="color: inherit;"></span><span id="MathJax-Element-2-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" style="font-size: 119%; position: relative;" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>M</mi></math>" role="presentation"><span id="MJXc-Node-14" class="mjx-math" aria-hidden="true"><span id="MJXc-Node-15" class="mjx-mrow"><span id="MJXc-Node-16" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.081em;">M</span></span></span></span><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>M</mi></math></span></span><script type="math/tex" id="MathJax-Element-2">M</script></span><span> is the key-length in bits</span></li>

  44. <li><span>Total number of nodes: </span><span class="mathjax"><span class="MathJax_Preview" style="color: inherit;"></span><span id="MathJax-Element-3-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" style="font-size: 119%; position: relative;" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>N</mi><mo>&amp;#x2264;</mo><msup><mn>2</mn><mi>M</mi></msup></math>" role="presentation"><span id="MJXc-Node-17" class="mjx-math" aria-hidden="true"><span id="MJXc-Node-18" class="mjx-mrow"><span id="MJXc-Node-19" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.085em;">N</span></span><span id="MJXc-Node-20" class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.475em;">≤</span></span><span id="MJXc-Node-21" class="mjx-msubsup MJXc-space3"><span class="mjx-base"><span id="MJXc-Node-22" class="mjx-mn"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.318em;">2</span></span></span><span class="mjx-sup" style="font-size: 70.7%; vertical-align: 0.591em; padding-left: 0px; padding-right: 0.071em;"><span id="MJXc-Node-23" class="mjx-mi" style=""><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.081em;">M</span></span></span></span></span></span><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>N</mi><mo>≤</mo><msup><mn>2</mn><mi>M</mi></msup></math></span></span><script type="math/tex" id="MathJax-Element-3">N \leq 2^M</script></span></li>

  45. <li><span>Each node should stay up-to-date about the current topology of the ring</span></li>

  46. <li><span>Nodes communicate over the network using RPC</span></li>

  47. </ul><h3 id="Node" data-id="Node"><a class="anchor hidden-xs" href="#Node" title="Node"><span class="octicon octicon-link"></span></a><span>Node</span></h3><ul>

  48. <li>

  49. <p><span>Each node is responsible for storing values for keys in the range </span><code>(predecessor_id, node_id]</code><span> except the first node which stores values for keys in the range </span><code>(predecessor_id, 2**M) U [0, node_id]</code></p>

  50. </li>

  51. <li>

  52. <p><span>Each node maintains a </span><strong><span>finger table</span></strong><span> (i.e., a list of identifiers for some other nodes)</span></p>

  53. <ul>

  54. <li>

  55. <p><span>A finger table contains </span><span class="mathjax"><span class="MathJax_Preview" style="color: inherit;"></span><span id="MathJax-Element-28-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" style="font-size: 119%; position: relative;" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>M</mi></math>" role="presentation"><span id="MJXc-Node-402" class="mjx-math" aria-hidden="true"><span id="MJXc-Node-403" class="mjx-mrow"><span id="MJXc-Node-404" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.081em;">M</span></span></span></span><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>M</mi></math></span></span><script type="math/tex" id="MathJax-Element-28">M</script></span><span> entries (repetitions are allowed)</span></p>

  56. </li>

  57. <li>

  58. <p><span>The value of the </span><span class="mathjax"><span class="MathJax_Preview" style="color: inherit;"></span><span id="MathJax-Element-29-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" style="font-size: 119%; position: relative;" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><msup><mi>i</mi><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi>t</mi><mi>h</mi></mrow></msup></math>" role="presentation"><span id="MJXc-Node-405" class="mjx-math" aria-hidden="true"><span id="MJXc-Node-406" class="mjx-mrow"><span id="MJXc-Node-407" class="mjx-msubsup"><span class="mjx-base"><span id="MJXc-Node-408" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.423em; padding-bottom: 0.265em;">i</span></span></span><span class="mjx-sup" style="font-size: 70.7%; vertical-align: 0.513em; padding-left: 0px; padding-right: 0.071em;"><span id="MJXc-Node-409" class="mjx-texatom" style=""><span id="MJXc-Node-410" class="mjx-mrow"><span id="MJXc-Node-411" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.423em; padding-bottom: 0.265em;">t</span></span><span id="MJXc-Node-412" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em;">h</span></span></span></span></span></span></span></span><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>i</mi><mrow class="MJX-TeXAtom-ORD"><mi>t</mi><mi>h</mi></mrow></msup></math></span></span><script type="math/tex" id="MathJax-Element-29">i^{th}</script></span><span> element in the finger table for node </span><span class="mathjax"><span class="MathJax_Preview" style="color: inherit;"></span><span id="MathJax-Element-30-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" style="font-size: 119%; position: relative;" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>n</mi></math>" role="presentation"><span id="MJXc-Node-413" class="mjx-math" aria-hidden="true"><span id="MJXc-Node-414" class="mjx-mrow"><span id="MJXc-Node-415" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">n</span></span></span></span><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math></span></span><script type="math/tex" id="MathJax-Element-30">n</script></span><span> is defined as follows:</span></p>

  59. <p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit;"></span><span class="mjx-chtml MJXc-display" style="text-align: center;"><span id="MathJax-Element-31-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" style="font-size: 119%; text-align: center; position: relative;" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot; display=&quot;block&quot;><mi>F</mi><msub><mi>T</mi><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi>n</mi></mrow></msub><mo stretchy=&quot;false&quot;>[</mo><mi>i</mi><mo stretchy=&quot;false&quot;>]</mo><mo>=</mo><mi>s</mi><mi>u</mi><mi>c</mi><mi>c</mi><mi>e</mi><mi>s</mi><mi>s</mi><mi>o</mi><mi>r</mi><mo stretchy=&quot;false&quot;>(</mo><mo stretchy=&quot;false&quot;>(</mo><mi>n</mi><mo>+</mo><msup><mn>2</mn><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi>i</mi></mrow></msup><mo stretchy=&quot;false&quot;>)</mo><mspace width=&quot;1em&quot; /><mi>mod</mi><mspace width=&quot;thinmathspace&quot; /><mspace width=&quot;thinmathspace&quot; /><msup><mn>2</mn><mi>M</mi></msup><mo stretchy=&quot;false&quot;>)</mo><mo>,</mo><mi>i</mi><mo>&amp;#x2208;</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mn>0..</mn><mi>M</mi><mo>&amp;#x2212;</mo><mn>1</mn><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation"><span id="MJXc-Node-416" class="mjx-math" aria-hidden="true"><span id="MJXc-Node-417" class="mjx-mrow"><span id="MJXc-Node-418" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.106em;">F</span></span><span id="MJXc-Node-419" class="mjx-msubsup"><span class="mjx-base" style="margin-right: -0.12em;"><span id="MJXc-Node-420" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.12em;">T</span></span></span><span class="mjx-sub" style="font-size: 70.7%; vertical-align: -0.212em; padding-right: 0.071em;"><span id="MJXc-Node-421" class="mjx-texatom" style=""><span id="MJXc-Node-422" class="mjx-mrow"><span id="MJXc-Node-423" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">n</span></span></span></span></span></span><span id="MJXc-Node-424" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">[</span></span><span id="MJXc-Node-425" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.423em; padding-bottom: 0.265em;">i</span></span><span id="MJXc-Node-426" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">]</span></span><span id="MJXc-Node-427" class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.055em; padding-bottom: 0.318em;">=</span></span><span id="MJXc-Node-428" class="mjx-mi MJXc-space3"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">s</span></span><span id="MJXc-Node-429" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">u</span></span><span id="MJXc-Node-430" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">c</span></span><span id="MJXc-Node-431" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">c</span></span><span id="MJXc-Node-432" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">e</span></span><span id="MJXc-Node-433" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">s</span></span><span id="MJXc-Node-434" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">s</span></span><span id="MJXc-Node-435" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">o</span></span><span id="MJXc-Node-436" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">r</span></span><span id="MJXc-Node-437" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">(</span></span><span id="MJXc-Node-438" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">(</span></span><span id="MJXc-Node-439" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.213em; padding-bottom: 0.265em;">n</span></span><span id="MJXc-Node-440" class="mjx-mo MJXc-space2"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.318em; padding-bottom: 0.423em;">+</span></span><span id="MJXc-Node-441" class="mjx-msubsup MJXc-space2"><span class="mjx-base"><span id="MJXc-Node-442" class="mjx-mn"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.318em;">2</span></span></span><span class="mjx-sup" style="font-size: 70.7%; vertical-align: 0.591em; padding-left: 0px; padding-right: 0.071em;"><span id="MJXc-Node-443" class="mjx-texatom" style=""><span id="MJXc-Node-444" class="mjx-mrow"><span id="MJXc-Node-445" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.423em; padding-bottom: 0.265em;">i</span></span></span></span></span></span><span id="MJXc-Node-446" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">)</span></span><span id="MJXc-Node-447" class="mjx-TeXmathchoice"><span id="MJXc-Node-448" class="mjx-mspace" style="width: 1em; height: 0px;"></span></span><span id="MJXc-Node-449" class="mjx-mi MJXc-space1"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.423em; padding-bottom: 0.37em;">mod</span></span><span id="MJXc-Node-450" class="mjx-mspace" style="width: 0.167em; height: 0px;"></span><span id="MJXc-Node-451" class="mjx-mspace" style="width: 0.167em; height: 0px;"></span><span id="MJXc-Node-452" class="mjx-msubsup MJXc-space1"><span class="mjx-base"><span id="MJXc-Node-453" class="mjx-mn"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.318em;">2</span></span></span><span class="mjx-sup" style="font-size: 70.7%; vertical-align: 0.591em; padding-left: 0px; padding-right: 0.071em;"><span id="MJXc-Node-454" class="mjx-mi" style=""><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.081em;">M</span></span></span></span><span id="MJXc-Node-455" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">)</span></span><span id="MJXc-Node-456" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="margin-top: -0.155em; padding-bottom: 0.528em;">,</span></span><span id="MJXc-Node-457" class="mjx-mi MJXc-space1"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.423em; padding-bottom: 0.265em;">i</span></span><span id="MJXc-Node-458" class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.265em; padding-bottom: 0.37em;">∈</span></span><span id="MJXc-Node-459" class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">{</span></span><span id="MJXc-Node-460" class="mjx-mn"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.37em;">0..</span></span><span id="MJXc-Node-461" class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top: 0.475em; padding-bottom: 0.265em; padding-right: 0.081em;">M</span></span><span id="MJXc-Node-462" class="mjx-mo MJXc-space2"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.318em; padding-bottom: 0.423em;">−</span></span><span id="MJXc-Node-463" class="mjx-mn MJXc-space2"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.37em; padding-bottom: 0.318em;">1</span></span><span id="MJXc-Node-464" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top: 0.475em; padding-bottom: 0.58em;">}</span></span></span></span><span class="MJX_Assistive_MathML MJX_Assistive_MathML_Block" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mi>F</mi><msub><mi>T</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msub><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>=</mo><mi>s</mi><mi>u</mi><mi>c</mi><mi>c</mi><mi>e</mi><mi>s</mi><mi>s</mi><mi>o</mi><mi>r</mi><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mi>i</mi></mrow></msup><mo stretchy="false">)</mo><mspace width="1em"></mspace><mi>mod</mi><mspace width="thinmathspace"></mspace><mspace width="thinmathspace"></mspace><msup><mn>2</mn><mi>M</mi></msup><mo stretchy="false">)</mo><mo>,</mo><mi>i</mi><mo>∈</mo><mo fence="false" stretchy="false">{</mo><mn>0..</mn><mi>M</mi><mo>−</mo><mn>1</mn><mo fence="false" stretchy="false">}</mo></math></span></span></span><script type="math/tex; mode=display" id="MathJax-Element-31">

  60. FT_{n}[i] = successor((n + 2^{i}) \mod 2^M), i \in \{0..M-1\}

  61. </script></span></p>

  62. </li>

  63. <li>

  64. <p><span>Successor function returns the identifier of the next online node in the ring (clockwise direction).</span></p>

  65. </li>

  66. <li>

  67. <p><span>Finger tables are used by the Chord algorithm to achieve a logarithmic search time. They are the reason behind Chord scalability.</span></p>

  68. </li>

  69. </ul>

  70. </li>

  71. <li>

  72. <p><span>Chord algorithm relies on two functions (</span><code>find_successor</code><span> and </span><code>closest_preceding_node</code><span>) to determine in which node should an entry (key-value pair) reside. The pseudo-code for these functions is given below:</span></p>

  73. <pre><code class="python hljs"><span class="hljs-comment"># Recursive function returning the identifier of the node responsible for a given id</span>

  74. n.find_successor(<span class="hljs-built_in">id</span>):

  75.   <span class="hljs-keyword">if</span> <span class="hljs-built_in">id</span> == n.<span class="hljs-built_in">id</span>:

  76.       <span class="hljs-keyword">return</span> <span class="hljs-built_in">id</span>

  77. 

  78.   <span class="hljs-comment"># Note the half-open interval and that L &lt;= R does not necessarily hold</span>

  79.   <span class="hljs-keyword">if</span> <span class="hljs-built_in">id</span> ∈ (n.<span class="hljs-built_in">id</span>, n.successor_id] then

  80.       <span class="hljs-keyword">return</span> n.successor_id

  81.    

  82.   <span class="hljs-comment"># Forward the query to the closest preceding node in the finger table for n</span>

  83.   n0 := closest_preceding_node(<span class="hljs-built_in">id</span>)

  84.   <span class="hljs-keyword">return</span> n0.find_successor(<span class="hljs-built_in">id</span>)

  85. </code></pre>

  86. <pre><code class="python hljs"><span class="hljs-comment"># Returns the closest preceeding node (from n.finger_table) for a given id</span>

  87. n.closest_preceding_node(<span class="hljs-built_in">id</span>):

  88.   <span class="hljs-comment"># Note the full-open interval and that L &lt;= R does not necessarily hold</span>

  89.   <span class="hljs-keyword">for</span> i = m downto <span class="hljs-number">1</span> do

  90.       <span class="hljs-keyword">if</span> finger[i].<span class="hljs-built_in">id</span> ∈ (n.<span class="hljs-built_in">id</span>, <span class="hljs-built_in">id</span>) then

  91.           <span class="hljs-keyword">return</span> finger[i]

  92.   <span class="hljs-keyword">return</span> n

  93. </code></pre>

  94. </li>

  95. </ul><h3 id="Client" data-id="Client"><a class="anchor hidden-xs" href="#Client" title="Client"><span class="octicon octicon-link"></span></a><span>Client</span></h3><ul>

  96. <li>

  97. <p><span>The client provided uses </span><a href="https://docs.python.org/3/library/xmlrpc.html" target="_blank" rel="noopener"><span>xmlrpc</span></a><span> to:</span></p>

  98. <ul>

  99. <li><span>Call a random node over RPC, the node should be ready and listening</span></li>

  100. <li><span>Ask the node to insert an entry into the chord</span></li>

  101. <li><span>Then execute some lookup operations</span>

  102. <ul>

  103. <li><span>Lookup operation asks a certain node about the value for a certain key</span></li>

  104. </ul>

  105. </li>

  106. </ul>

  107. </li>

  108. <li>

  109. <p><span>For the node to answer a request, it may contact other nodes as explained above</span></p>

  110. <ul>

  111. <li><strong><span>For </span><code>put</code><span> queries:</span></strong><span> return </span><code>True</code><span> on successful insertion and </span><code>False</code><span> otherwise</span></li>

  112. <li><strong><span>For </span><code>get</code><span> queries:</span></strong>

  113. <ul>

  114. <li><span>If the value for the given key is found, return that value</span></li>

  115. <li><span>If the value is not found, return </span><code>-1</code></li>

  116. </ul>

  117. </li>

  118. </ul>

  119. </li>

  120. </ul><h2 id="Task" data-id="Task"><a class="anchor hidden-xs" href="#Task" title="Task"><span class="octicon octicon-link"></span></a><span>Task</span></h2><ul>

  121. <li><span>Implement the Node class as explained above. The boilerplate is given in </span><code>node.py</code>

  122. <ul>

  123. <li><span>Parse one integer argument (</span><code>node_id</code><span>)</span></li>

  124. <li><span>Create a Node instance and register its methods for calling over XML-RPC</span></li>

  125. <li><span>Run XML-RPC server on </span><a href="http://0.0.0.0:1234" target="_blank" rel="noopener"><span>http://0.0.0.0:1234</span></a></li>

  126. <li><span>Write implementation for </span><code>find_successor</code><span> and </span><code>closest_preceding_node</code><span> according to the provided pseudo-code</span></li>

  127. <li><span>Write the logic for </span><code>n.get(key)</code><span> and </span><code>n.put(key, value)</code><span> to insert and retrieve data from the Chord</span></li>

  128. </ul>

  129. </li>

  130. <li><span>Test your code using docker as explained below. </span><strong><span>Code which does not work will receive 0 grade</span></strong></li>

  131. <li><span>Submit a single file </span><code>node_NameSurname.py</code></li>

  132. </ul><h2 id="Example-Run" data-id="Example-Run"><a class="anchor hidden-xs" href="#Example-Run" title="Example-Run"><span class="octicon octicon-link"></span></a><span>Example Run</span></h2><h3 id="Input" data-id="Input"><a class="anchor hidden-xs" href="#Input" title="Input"><span class="octicon octicon-link"></span></a><span>Input</span></h3><ul>

  133. <li>

  134. <p><span>We have prepared an example ring of 6 nodes and the required docker files to run all such nodes in one network, nodes are reachable from each other by their hostname (e.g., </span><code>http://node_22:1234</code><span>)</span></p>

  135. </li>

  136. <li>

  137. <p><span>An example client is also provided (</span><code>client.py</code><span>). The client runs in the same network with nodes and contacts random nodes from the ring, asking them to insert data into the Chord</span></p>

  138. <ul>

  139. <li><span>Overall, the client inserts 32 key-value pairs (i.e., </span><code>(0, "value_0")</code><span> up to </span><code>(31, "value_31")</code><span>)</span></li>

  140. </ul>

  141. </li>

  142. <li>

  143. <p><span>To run the example, execute the following command in the project directory</span></p>

  144. <pre><code class="bash hljs">docker-compose build --no-cache &amp;&amp; docker-compose up

  145. </code></pre>

  146. </li>

  147. <li>

  148. <p><span>Note that your code will be tested on different rings, a correct implementation should always work</span></p>

  149. </li>

  150. </ul><h3 id="Output" data-id="Output"><a class="anchor hidden-xs" href="#Output" title="Output"><span class="octicon octicon-link"></span></a><span>Output</span></h3><ul>

  151. <li>

  152. <p><span>The output shows how lookup queries are routed through the ring, the routing order is deterministic.</span></p>

  153. </li>

  154. <li>

  155. <p><span>For simplicity, the Chord does not have any data stored in this run (that is why </span><code>-1</code><span> is returned)</span></p>

  156. </li>

  157. <li>

  158. <p><span>The </span><code>client.py</code><span> provided should result in more output as </span><code>put</code><span> requests are routed between nodes. </span><code>get</code><span> requests should then return the expected values (i.e., </span><code>lookup(N, X) = "value_X"</code><span>)</span></p>

  159. <p><img src="https://i.imgur.com/oQwlFla.png" alt="output" loading="lazy"></p>

  160. </li>

  161. </ul><h3 id="Visualization" data-id="Visualization"><a class="anchor hidden-xs" href="#Visualization" title="Visualization"><span class="octicon octicon-link"></span></a><span>Visualization</span></h3><ul>

  162. <li><span>You can use </span><a href="https://msindwan.github.io/chordgen/" target="_blank" rel="noopener"><span>Chordgen</span></a><span> to visualize test cases and verify finger tables and lookup order</span></li>

  163. <li><span>The following diagram shows the given example ring and data allocation</span><br>

  164. <img src="https://i.imgur.com/0vQxm0W.png" alt="example" loading="lazy"></li>

  165. </ul><h2 id="Checklist" data-id="Checklist"><a class="anchor hidden-xs" href="#Checklist" title="Checklist"><span class="octicon octicon-link"></span></a><span>Checklist</span></h2><ul class="contains-task-list">

  166. <li class="task-list-item enabled"><input class="task-list-item-checkbox" type="checkbox" disabled="disabled"><span> A single submitted file (</span><code>node_NameSurname.py</code><span>)</span></li>

  167. <li class="task-list-item enabled"><input class="task-list-item-checkbox" type="checkbox" disabled="disabled"><span> The code is formatted and does not use any external dependencies</span></li>

  168. <li class="task-list-item enabled"><input class="task-list-item-checkbox" type="checkbox" disabled="disabled"><span> Logging shows the finger table for each node</span></li>

  169. <li class="task-list-item enabled"><input class="task-list-item-checkbox" type="checkbox" disabled="disabled"><span> Logging shows which node functions were called over RPC and how the request was routed (see example output above)</span></li>

  170. <li class="task-list-item enabled"><input class="task-list-item-checkbox" type="checkbox" disabled="disabled"><span> The system provides the correct output for </span><strong><span>the given example</span></strong><span> ring and lookup queries</span></li>

  171. <li class="task-list-item enabled"><input class="task-list-item-checkbox" type="checkbox" disabled="disabled"><span> The system provides the correct output for </span><strong><span>a different</span></strong><span> ring and lookup queries</span></li>

  172. <li class="task-list-item enabled"><input class="task-list-item-checkbox" type="checkbox" disabled="disabled"><span> The source code is the author’s original work. Both parties will be penalized for detected plagiarism</span></li>

  173. </ul><h2 id="Additional-Notes" data-id="Additional-Notes"><a class="anchor hidden-xs" href="#Additional-Notes" title="Additional-Notes"><span class="octicon octicon-link"></span></a><span>Additional Notes</span></h2><ul>

  174. <li><span>Chord is quite a complex protocol, you can find the original implementation </span><a href="https://github.com/sit/dht" target="_blank" rel="noopener"><span>here</span></a></li>

  175. <li><span>The following simplifications were made to adjust the complexity of the task:</span>

  176. <ul>

  177. <li><span>Each node is initialized with knowledge about other nodes in the ring, removing the need to implement notification procedures</span></li>

  178. <li><span>The system topology is fixed, removing the need to implement procedures for stabilization, node joining/exiting and finger table updates</span></li>

  179. <li><span>A client is provided to test the system. In real-world scenarios, that client is typically a node as well</span></li>

  180. </ul>

  181. </li>

  182. <li><span>In real-world implementations, the Chord and its finger tables should update dynamically as nodes enter and exit the system. Periodical stabilization procedures are also used to ensure that nodes stay up-to-date with the current topology of the ring</span></li>

  183. </ul></div>

  184.     <div class="ui-toc dropup unselectable hidden-print" style="display:none;">

  185.         <div class="pull-right dropdown">

  186.             <a id="tocLabel" class="ui-toc-label btn btn-default" data-toggle="dropdown" href="#" role="button" aria-haspopup="true" aria-expanded="false" title="Table of content">

  187.                 <i class="fa fa-bars"></i>

  188.             </a>

  189.             <ul id="ui-toc" class="ui-toc-dropdown dropdown-menu" aria-labelledby="tocLabel">

  190.                 <div class="toc"><ul class="nav">

  191. <li><a href="#Week-5---Distributed-Hash-Tables" title="Week 5 - Distributed Hash Tables">Week 5 - Distributed Hash Tables</a><ul class="nav">

  192. <li><a href="#Overview" title="Overview">Overview</a></li>

  193. <li><a href="#System-Architecture" title="System Architecture">System Architecture</a><ul class="nav">

  194. <li><a href="#Node" title="Node">Node</a></li>

  195. <li><a href="#Client" title="Client">Client</a></li>

  196. </ul>

  197. </li>

  198. <li><a href="#Task" title="Task">Task</a></li>

  199. <li><a href="#Example-Run" title="Example Run">Example Run</a><ul class="nav">

  200. <li><a href="#Input" title="Input">Input</a></li>

  201. <li><a href="#Output" title="Output">Output</a></li>

  202. <li><a href="#Visualization" title="Visualization">Visualization</a></li>

  203. </ul>

  204. </li>

  205. <li><a href="#Checklist" title="Checklist">Checklist</a></li>

  206. <li><a href="#Additional-Notes" title="Additional Notes">Additional Notes</a></li>

  207. </ul>

  208. </li>

  209. </ul>

  210. </div><div class="toc-menu"><a class="expand-toggle" href="#">Expand all</a><a class="back-to-top" href="#">Back to top</a><a class="go-to-bottom" href="#">Go to bottom</a></div>

  211.             </ul>

  212.         </div>

  213.     </div>

  214.     <div id="ui-toc-affix" class="ui-affix-toc ui-toc-dropdown unselectable hidden-print" data-spy="affix" style="top:17px;display:none;" null null>

  215.         <div class="toc"><ul class="nav">

  216. <li><a href="#Week-5---Distributed-Hash-Tables" title="Week 5 - Distributed Hash Tables">Week 5 - Distributed Hash Tables</a><ul class="nav">

  217. <li><a href="#Overview" title="Overview">Overview</a></li>

  218. <li><a href="#System-Architecture" title="System Architecture">System Architecture</a><ul class="nav">

  219. <li><a href="#Node" title="Node">Node</a></li>

  220. <li><a href="#Client" title="Client">Client</a></li>

  221. </ul>

  222. </li>

  223. <li><a href="#Task" title="Task">Task</a></li>

  224. <li><a href="#Example-Run" title="Example Run">Example Run</a><ul class="nav">

  225. <li><a href="#Input" title="Input">Input</a></li>

  226. <li><a href="#Output" title="Output">Output</a></li>

  227. <li><a href="#Visualization" title="Visualization">Visualization</a></li>

  228. </ul>

  229. </li>

  230. <li><a href="#Checklist" title="Checklist">Checklist</a></li>

  231. <li><a href="#Additional-Notes" title="Additional Notes">Additional Notes</a></li>

  232. </ul>

  233. </li>

  234. </ul>

  235. </div><div class="toc-menu"><a class="expand-toggle" href="#">Expand all</a><a class="back-to-top" href="#">Back to top</a><a class="go-to-bottom" href="#">Go to bottom</a></div>

  236.     </div>

  237.     <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.1.1/jquery.min.js" integrity="sha256-hVVnYaiADRTO2PzUGmuLJr8BLUSjGIZsDYGmIJLv2b8=" crossorigin="anonymous"></script>

  238.     <script src="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/3.3.7/js/bootstrap.min.js" integrity="sha256-U5ZEeKfGNOja007MMD3YBI0A3OSZOQbeG6z2f2Y0hu8=" crossorigin="anonymous" defer></script>

  239.     <script src="https://cdnjs.cloudflare.com/ajax/libs/gist-embed/2.6.0/gist-embed.min.js" integrity="sha256-KyF2D6xPIJUW5sUDSs93vWyZm+1RzIpKCexxElmxl8g=" crossorigin="anonymous" defer></script>

  240.     <script>

  241.         var markdown = $(".markdown-body");

  242.         //smooth all hash trigger scrolling

  243.         function smoothHashScroll() {

  244.             var hashElements = $("a[href^='#']").toArray();

  245.             for (var i = 0; i < hashElements.length; i++) {

  246.                 var element = hashElements[i];

  247.                 var $element = $(element);

  248.                 var hash = element.hash;

  249.                 if (hash) {

  250.                     $element.on('click', function (e) {

  251.                         // store hash

  252.                         var hash = this.hash;

  253.                         if ($(hash).length <= 0) return;

  254.                         // prevent default anchor click behavior

  255.                         e.preventDefault();

  256.                         // animate

  257.                         $('body, html').stop(true, true).animate({

  258.                             scrollTop: $(hash).offset().top

  259.                         }, 100, "linear", function () {

  260.                             // when done, add hash to url

  261.                             // (default click behaviour)

  262.                             window.location.hash = hash;

  263.                         });

  264.                     });

  265.                 }

  266.             }

  267.         }

  268. 

  269.         smoothHashScroll();

  270.         var toc = $('.ui-toc');

  271.         var tocAffix = $('.ui-affix-toc');

  272.         var tocDropdown = $('.ui-toc-dropdown');

  273.         //toc

  274.         tocDropdown.click(function (e) {

  275.             e.stopPropagation();

  276.         });

  277. 

  278.         var enoughForAffixToc = true;

  279. 

  280.         function generateScrollspy() {

  281.             $(document.body).scrollspy({

  282.                 target: ''

  283.             });

  284.             $(document.body).scrollspy('refresh');

  285.             if (enoughForAffixToc) {

  286.                 toc.hide();

  287.                 tocAffix.show();

  288.             } else {

  289.                 tocAffix.hide();

  290.                 toc.show();

  291.             }

  292.             $(document.body).scroll();

  293.         }

  294. 

  295.         function windowResize() {

  296.             //toc right

  297.             var paddingRight = parseFloat(markdown.css('padding-right'));

  298.             var right = ($(window).width() - (markdown.offset().left + markdown.outerWidth() - paddingRight));

  299.             toc.css('right', right + 'px');

  300.             //affix toc left

  301.             var newbool;

  302.             var rightMargin = (markdown.parent().outerWidth() - markdown.outerWidth()) / 2;

  303.             //for ipad or wider device

  304.             if (rightMargin >= 133) {

  305.                 newbool = true;

  306.                 var affixLeftMargin = (tocAffix.outerWidth() - tocAffix.width()) / 2;

  307.                 var left = markdown.offset().left + markdown.outerWidth() - affixLeftMargin;

  308.                 tocAffix.css('left', left + 'px');

  309.             } else {

  310.                 newbool = false;

  311.             }

  312.             if (newbool != enoughForAffixToc) {

  313.                 enoughForAffixToc = newbool;

  314.                 generateScrollspy();

  315.             }

  316.         }

  317.         $(window).resize(function () {

  318.             windowResize();

  319.         });

  320.         $(document).ready(function () {

  321.             windowResize();

  322.             generateScrollspy();

  323.         });

  324. 

  325.         //remove hash

  326.         function removeHash() {

  327.             window.location.hash = '';

  328.         }

  329. 

  330.         var backtotop = $('.back-to-top');

  331.         var gotobottom = $('.go-to-bottom');

  332. 

  333.         backtotop.click(function (e) {

  334.             e.preventDefault();

  335.             e.stopPropagation();

  336.             if (scrollToTop)

  337.                 scrollToTop();

  338.             removeHash();

  339.         });

  340.         gotobottom.click(function (e) {

  341.             e.preventDefault();

  342.             e.stopPropagation();

  343.             if (scrollToBottom)

  344.                 scrollToBottom();

  345.             removeHash();

  346.         });

  347. 

  348.         var toggle = $('.expand-toggle');

  349.         var tocExpand = false;

  350. 

  351.         checkExpandToggle();

  352.         toggle.click(function (e) {

  353.             e.preventDefault();

  354.             e.stopPropagation();

  355.             tocExpand = !tocExpand;

  356.             checkExpandToggle();

  357.         })

  358. 

  359.         function checkExpandToggle () {

  360.             var toc = $('.ui-toc-dropdown .toc');

  361.             var toggle = $('.expand-toggle');

  362.             if (!tocExpand) {

  363.                 toc.removeClass('expand');

  364.                 toggle.text('Expand all');

  365.             } else {

  366.                 toc.addClass('expand');

  367.                 toggle.text('Collapse all');

  368.             }

  369.         }

  370. 

  371.         function scrollToTop() {

  372.             $('body, html').stop(true, true).animate({

  373.                 scrollTop: 0

  374.             }, 100, "linear");

  375.         }

  376. 

  377.         function scrollToBottom() {

  378.             $('body, html').stop(true, true).animate({

  379.                 scrollTop: $(document.body)[0].scrollHeight

  380.             }, 100, "linear");

  381.         }

  382.     </script>

  383. </body>

  384. 

  385. </html>