分布式计算论文

  • r3_990519
    了解作者
  • 1.2MB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-05 06:16
    上传日期
分布式计算论文 lease paxos
paper.rar
  • paper2-1.pdf
    239.8KB
  • 89-leases.pdf
    1.1MB
内容介绍
<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/6272fb457ec58a2c01185528/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6272fb457ec58a2c01185528/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">Leases: <span class="ls1 ws1">An <span class="_ _0"> </span><span class="ls2 ws2">Efficient <span class="_ _1"> </span><span class="ls3 ws3">Fault-Tolerant <span class="_ _2"> </span><span class="ls4 ws4">Mechanism </span></span></span></span></div><div class="t m0 x2 h2 y2 ff1 fs0 fc0 sc0 ls5 ws5">for <span class="_ _3"> </span><span class="ls6 ws6">Distributed <span class="_ _4"> </span><span class="ls7 ws7">File <span class="_ _5"> </span><span class="ls8 ws8">Cache <span class="ls9 ws9">Consistency </span></span></span></span></div><div class="t m1 x3 h3 y3 ff1 fs1 fc0 sc0 lsa wsa">Cary <span class="_ _2"> </span><span class="lsb wsb">G. <span class="_ _0"> </span><span class="lsc wsc">Gray <span class="_ _2"> </span><span class="lsd wsd">and <span class="_ _0"> </span><span class="lse wse">David <span class="_ _6"> </span><span class="lsf wsf">R. </span></span></span></span></span></div><div class="t m2 x4 h4 y3 ff1 fs2 fc0 sc0 ls10 ws10">Cheriton </div><div class="t m1 x5 h3 y4 ff1 fs1 fc0 sc0 ls11 ws11">Computer <span class="_ _7"> </span><span class="ls12 ws12">Science <span class="_ _1"> </span><span class="ls13 ws13">Department </span></span></div><div class="t m1 x6 h3 y5 ff1 fs1 fc0 sc0 ls14 ws14">!3tanford <span class="_ _8"> </span><span class="ls15 ws15">University </span></div><div class="t m3 x7 h5 y6 ff1 fs3 fc0 sc0 ls16 ws16">Abstract </div><div class="t m1 x8 h3 y7 ff1 fs1 fc0 sc0 ls17 ws17">Caching <span class="_ _9"></span><span class="ls18 ws18">introduces <span class="_ _a"></span><span class="ls19 ws19">the <span class="_ _9"></span><span class="ls1a ws1a">overbead <span class="_ _b"></span><span class="lsd wsd">and <span class="_ _a"></span><span class="ls1b ws1b">complexity <span class="_"> </span><span class="ls1c ws1c">of <span class="_ _c"></span><span class="ls1d ws1d">ensur- </span></span></span></span></span></span></span></div><div class="t m1 x7 h3 y8 ff1 fs1 fc0 sc0 ls1e ws1e">ing <span class="_ _d"> </span><span class="ls1f ws1f">consistency, <span class="_ _9"></span><span class="ls20 ws20">reducing <span class="_ _e"></span><span class="ls21 ws21">some <span class="_ _a"></span><span class="ls1c ws1c">of <span class="_ _f"></span><span class="ls22 ws22">its <span class="_ _10"></span><span class="ls23 ws23">performance <span class="_ _10"></span><span class="ls24 ws24">bene- </span></span></span></span></span></span></span></div><div class="t m1 x7 h3 y9 ff1 fs1 fc0 sc0 ls25 ws25">fits. <span class="_ _11"> </span><span class="ls26 ws26">In <span class="_ _d"> </span><span class="ls27 ws27">a <span class="ls28 ws28">distributed <span class="_ _12"> </span><span class="ls29 ws29">system, <span class="_ _13"></span><span class="ls2a ws2a">caching <span class="_ _f"></span><span class="ls2b ws2b">must <span class="_ _10"></span><span class="ls2c ws2c">deal <span class="_ _f"></span><span class="ls2d ws2d">,wit.h <span class="_ _14"></span><span class="ls19 ws19">the </span></span></span></span></span></span></span></span></span></div><div class="t m1 x7 h3 ya ff1 fs1 fc0 sc0 ls2e ws2e">additional <span class="_ _d"> </span><span class="ls2f ws2f">complications <span class="_ _f"></span><span class="ls1c ws1c">of <span class="ls30 ws30">communication <span class="_ _d"> </span><span class="lsd wsd">and <span class="_ _c"></span><span class="ls2c ws31">host <span class="_ _13"></span><span class="ls31 ws32">fail- </span></span></span></span></span></span></div><div class="t m1 x7 h3 yb ff1 fs1 fc0 sc0 ls32 ws33">ures. </div><div class="t m3 x9 h6 yc ff1 fs4 fc0 sc0 ls33 ws34">Leases </div><div class="t m1 xa h3 yc ff1 fs1 fc0 sc0 ls34 ws35">are <span class="_ _15"></span><span class="ls35 ws36">proposed <span class="_ _13"></span><span class="lsb wsb">as <span class="_ _15"></span><span class="ls27 ws27">a <span class="_ _16"></span><span class="ls36 ws37">time-based <span class="_ _15"></span><span class="ls37 ws38">mechanism <span class="_ _f"></span><span class="ls38 ws39">that </span></span></span></span></span></span></div><div class="t m1 x7 h3 yd ff1 fs1 fc0 sc0 ls39 ws3a">provides <span class="_ _16"></span><span class="ls3a ws3b">efficient <span class="_ _17"> </span><span class="ls3b ws3c">consistent <span class="_ _c"></span><span class="ls3c ws3d">access <span class="_ _14"></span><span class="ls3d ws3e">to <span class="_ _15"></span><span class="ls3e ws3f">cached <span class="_ _c"></span><span class="ls3f ws40">data <span class="_ _c"></span><span class="ls40 ws41">in <span class="_ _e"></span><span class="ls41 ws42">dis- </span></span></span></span></span></span></span></span></div><div class="t m1 x7 h3 ye ff1 fs1 fc0 sc0 ls42 ws43">tributed <span class="_"> </span><span class="ls43 ws44">systems. <span class="_"> </span><span class="ls44 ws45">Non-Byzantine <span class="_ _18"> </span><span class="ls45 ws46">failures <span class="_"> </span><span class="ls46 ws47">affect <span class="_ _16"></span><span class="ls47 ws48">perfor- </span></span></span></span></span></div><div class="t m1 x7 h3 yf ff1 fs1 fc0 sc0 ls48 ws49">mance, <span class="_ _e"></span><span class="ls19 ws19">not <span class="_ _12"> </span><span class="ls49 ws4a">correctness, <span class="ls4a ws4b">with <span class="_ _0"> </span><span class="ls4b ws4c">their <span class="_ _0"> </span><span class="ls46 ws47">effect <span class="_ _e"> </span><span class="ls4c ws4d">minimized <span class="_ _18"> </span><span class="ls4d ws4e">by </span></span></span></span></span></span></span></div><div class="t m1 x7 h3 y10 ff1 fs1 fc0 sc0 ls32 ws33">short <span class="ls4e ws4f">leases. <span class="_ _19"></span><span class="ls4f ws50">An <span class="_ _12"> </span><span class="ls50 ws51">analytic <span class="_ _f"></span><span class="ls51 ws52">model <span class="_ _16"></span><span class="lsd wsd">and <span class="_ _9"></span><span class="ls52 ws53">an <span class="_ _9"></span><span class="ls53 ws54">evaluation <span class="_ _d"> </span><span class="ls54 ws55">for <span class="_ _16"></span><span class="ls55 ws1">file </span></span></span></span></span></span></span></span></span></div><div class="t m1 x8 h3 y11 ff1 fs1 fc0 sc0 ls3c ws3d">access <span class="_ _1a"></span><span class="ls40 ws41">in <span class="_ _12"> </span><span class="ls19 ws19">the <span class="_ _13"></span><span class="ls56 ws56">V <span class="_ _e"></span><span class="ls57 ws57">system <span class="_ _a"></span><span class="ls58 ws58">show <span class="ls38 ws39">that <span class="_ _9"></span><span class="ls34 ws35">leases <span class="_ _1b"></span><span class="ls1c ws1c">of <span class="_ _10"></span><span class="ls32 ws33">short <span class="_ _15"></span><span class="ls59 ws59">duration </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x7 h3 y12 ff1 fs1 fc0 sc0 ls5a ws5a">provide <span class="_ _12"> </span><span class="ls27 ws27">good <span class="_ _9"></span><span class="ls5b ws5b">performance. <span class="_ _12"> </span><span class="ls5c ws5c">The <span class="_ _15"></span><span class="ls5d ws5d">impact <span class="_ _e"> </span><span class="ls1c ws1c">of <span class="_ _15"></span><span class="ls34 ws35">leases <span class="_ _a"></span><span class="ls52 ws53">on <span class="_ _15"></span><span class="ls5e ws5e">per- </span></span></span></span></span></span></span></span></div><div class="t m1 x8 h3 y13 ff1 fs1 fc0 sc0 ls5f ws5f">formance <span class="_ _19"></span><span class="ls60 ws60">grows <span class="_ _19"></span><span class="ls61 ws61">more <span class="_ _a"></span><span class="ls62 ws62">significant <span class="_ _16"></span><span class="ls40 ws41">in <span class="_ _16"></span><span class="ls63 ws63">systems <span class="_ _1c"></span><span class="ls1c ws1c">of <span class="_ _19"></span><span class="ls64 ws64">lar;ger <span class="_ _1a"></span><span class="ls65 ws65">scale </span></span></span></span></span></span></span></span></div><div class="t m1 x8 h3 y14 ff1 fs1 fc0 sc0 lsd wsd">and <span class="_ _19"></span><span class="ls66 ws66">higher <span class="_ _10"></span><span class="ls67 ws67">processor <span class="_ _b"></span><span class="ls5b ws5b">performance. </span></span></span></div><div class="t m3 x8 h5 y15 ff1 fs3 fc0 sc0 ls68 ws68">1 <span class="_ _1d"> </span><span class="ls69 ws69">Introduction </span></div><div class="t m1 x8 h3 y16 ff1 fs1 fc0 sc0 ls17 ws17">Caching <span class="_ _f"></span><span class="ls18 ws18">introduces <span class="_ _15"></span><span class="ls19 ws19">the <span class="_ _15"></span><span class="ls6a ws6a">problem <span class="_ _e"></span><span class="ls1c ws1c">of <span class="_ _16"></span><span class="ls6b ws6b">ensuring <span class="_ _e"></span><span class="ls6c ws6c">consistency </span></span></span></span></span></span></div><div class="t m1 x7 h3 y17 ff1 fs1 fc0 sc0 ls6d ws6d">between <span class="ls19 ws19">the <span class="ls3e ws3f">cached <span class="_ _1b"></span><span class="ls3f ws40">data <span class="lsd wsd">and <span class="_ _c"></span><span class="ls22 ws22">its <span class="_ _15"></span><span class="ls6e ws6e">primary <span class="_"> </span><span class="ls6f ws6f">location <span class="_"> </span><span class="ls1c ws1c">of <span class="ls70 ws70">stor- </span></span></span></span></span></span></span></span></span></div><div class="t m1 x8 h3 y18 ff1 fs1 fc0 sc0 ls3f ws40">age. <span class="_ _12"> </span><span class="ls58 ws71">By </span></div><div class="t m3 xb h6 y18 ff1 fs4 fc0 sc0 ls71 ws72">consistent, </div><div class="t m1 xc h3 y18 ff1 fs1 fc0 sc0 ls72 ws73">we <span class="_ _16"></span><span class="ls73 ws74">mean <span class="ls38 ws39">that <span class="_ _10"></span><span class="ls19 ws19">the <span class="_ _15"></span><span class="ls20 ws20">behavior <span class="_ _12"> </span><span class="ls74 ws28">is <span class="_ _f"></span><span class="ls75 ws75">equiv- </span></span></span></span></span></span></div><div class="t m1 x8 h3 y19 ff1 fs1 fc0 sc0 ls76 ws76">alent <span class="_ _10"></span><span class="ls3d ws3e">to <span class="_ _10"></span><span class="ls77 ws77">there <span class="_ _13"></span><span class="ls78 ws78">being <span class="_ _10"></span><span class="ls79 ws79">only <span class="_"> </span><span class="ls27 ws27">a <span class="_ _9"></span><span class="ls7a ws7a">single <span class="_ _f"></span><span class="ls7b ws7b">(uncached) <span class="_ _10"></span><span class="ls7c ws7c">copy <span class="_ _e"></span><span class="ls1c ws1c">of <span class="_ _10"></span><span class="ls19 ws19">the </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x8 h3 y1a ff1 fs1 fc0 sc0 ls3f ws40">data <span class="_ _b"></span><span class="ls7d ws7d">except <span class="_ _13"></span><span class="ls54 ws55">for <span class="ls19 ws19">the <span class="_ _19"></span><span class="ls23 ws23">performance <span class="_ _19"></span><span class="ls7e ws7e">benefit <span class="ls1c ws1c">of <span class="_ _c"></span><span class="ls19 ws19">the <span class="ls7f ws7f">cache. <span class="_ _c"></span><span class="lsf ws80">With </span></span></span></span></span></span></span></span></span></div><div class="t m1 x7 h3 y1b ff1 fs1 fc0 sc0 ls32 ws33">large <span class="_ _f"></span><span class="ls80 ws81">caches, <span class="_ _a"></span><span class="ls19 ws19">the <span class="ls81 ws82">traffic <span class="_ _e"> </span><span class="ls82 ws83">required <span class="_ _e"></span><span class="ls3d ws3e">to <span class="_ _16"></span><span class="ls83 ws84">maintain <span class="_"> </span><span class="ls6c ws6c">consistency </span></span></span></span></span></span></span></div><div class="t m1 x8 h3 y1c ff1 fs1 fc0 sc0 ls84 ws85">can <span class="_ _13"></span><span class="ls27 ws27">be <span class="_ _19"></span><span class="ls19 ws19">the <span class="_ _13"></span><span class="ls85 ws86">dominant <span class="_ _16"></span><span class="ls86 ws87">factor <span class="ls40 ws41">in <span class="_ _e"></span><span class="ls87 ws88">cache <span class="_ _b"></span><span class="ls5b ws5b">performance. </span></span></span></span></span></span></span></div><div class="t m1 xd h3 y1d ff1 fs1 fc0 sc0 ls88 ws89">Cache <span class="_ _12"> </span><span class="ls6c ws6c">consistency <span class="_ _d"> </span><span class="ls89 ws8a">protocols <span class="_ _0"> </span><span class="ls8a ws8b">have <span class="_ _0"> </span><span class="ls8b ws8c">been <span class="_"> </span><span class="ls8c ws8d">extensively </span></span></span></span></span></div><div class="t m1 x8 h3 y1e ff1 fs1 fc0 sc0 ls8d ws8e">studied <span class="_ _e"></span><span class="ls40 ws41">in <span class="_ _0"> </span><span class="ls19 ws19">the <span class="_ _12"> </span><span class="ls8e ws8f">work <span class="_ _0"> </span><span class="ls52 ws53">on <span class="_"> </span><span class="ls8f ws90">shared <span class="_ _15"></span><span class="ls90 ws91">memory <span class="_ _3"> </span><span class="ls91 ws92">multiprocessor </span></span></span></span></span></span></span></div><div class="t m4 xe h7 y1f ff1 fs5 fc0 sc0 ls92 ws93">This <span class="_ _18"> </span><span class="ls93 ws94">work <span class="_ _1e"> </span><span class="ls94 ws95">was </span></span></div><div class="t m1 xf h3 y1f ff1 fs1 fc0 sc0 ls95 ws96">supported </div><div class="t m4 x10 h7 y1f ff1 fs5 fc0 sc0 ls96 ws97">in <span class="_ _3"> </span><span class="ls97 ws98">part <span class="_ _0"> </span><span class="lsa ws99">by <span class="_ _0"> </span><span class="ls98 ws9a">the <span class="_ _d"> </span><span class="ls99 ws9b">Defense <span class="_ _1e"> </span><span class="ls9a ws9c">Advanced <span class="_ _8"> </span><span class="ls9b ws9d">Re- </span></span></span></span></span></span></div><div class="t m4 x8 h7 y20 ff1 fs5 fc0 sc0 ls9c ws9e">search <span class="_ _12"> </span><span class="ls9d ws9f">Projects <span class="_ _0"> </span><span class="ls9e wsa0">Agency <span class="_ _1e"> </span><span class="ls9f wsa1">under <span class="_"> </span><span class="lsa0 wsa2">contract <span class="_ _0"> </span><span class="lsa1 wsa3">NOO039-84-C-02 <span class="_ _5"> </span><span class="lsa2 wsa4">11, <span class="_ _13"></span><span class="lsa ws99">by <span class="_ _17"> </span><span class="ls98 ws9a">the <span class="_"> </span><span class="ls9b ws9d">Na- </span></span></span></span></span></span></span></span></span></div><div class="t m4 x8 h7 y21 ff1 fs5 fc0 sc0 lsa3 wsa5">tional <span class="_ _5"> </span><span class="lsa4 wsa6">Science <span class="_ _12"> </span><span class="lsa5 wsa7">Foundation <span class="_ _5"> </span><span class="lsa6 ws89">Grant <span class="_ _3"> </span><span class="lsa7 ws49">DCR-83-52048, <span class="_ _6"> </span><span class="lsa8 wsa8">and <span class="_ _16"></span><span class="lsa ws99">by <span class="_"> </span><span class="lsa9 wsa9">Digital <span class="_ _2"> </span><span class="lsaa wsaa">Equip- </span></span></span></span></span></span></span></span></div><div class="t m4 x8 h7 y22 ff1 fs5 fc0 sc0 lsab wsab">ment <span class="_ _12"> </span><span class="ls49 wsac">Corporation. </span></div><div class="t m4 x11 h7 y23 ff1 fs5 fc0 sc0 lsac wsad">Permission <span class="_ _1b"></span><span class="lsad wsae">to <span class="_ _f"> </span><span class="lsa ws99">copy <span class="_ _15"></span><span class="lsae wsaf">without <span class="_ _17"> </span><span class="lsaf wsb0">fee <span class="_ _c"></span><span class="lsb0 wsb1">all <span class="_ _16"></span><span class="lsb1 wsb2">or <span class="_ _f"></span><span class="ls97 ws98">part <span class="_ _10"></span><span class="lsb2 wsb3">of <span class="_ _16"></span><span class="ls96 ws97">this <span class="_ _15"></span><span class="lsb3 wsb4">material <span class="_ _10"></span><span class="lsb4 wsb5">is <span class="_ _9"></span><span class="lsb5 wsb6">granted <span class="lsb6 wsb7">provided </span></span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m4 x11 h7 y24 ff1 fs5 fc0 sc0 lsb7 wsb8">that <span class="_ _15"></span><span class="ls98 ws9a">the <span class="_ _15"></span><span class="lsb8 wsb9">copies <span class="_ _19"></span><span class="lsb9 wsba">are <span class="ls98 wsbb">not <span class="_ _10"></span><span class="lsba wsbc">made <span class="_ _9"></span><span class="lsb1 wsb2">or <span class="_ _16"></span><span class="lsbb wsbd">distributed <span class="_ _16"></span><span class="lsbc wsbe">for <span class="_ _e"> </span><span class="lsbd wsbf">direct <span class="lsbe wsc0">commercial <span class="_ _10"></span><span class="lsbf wsc1">advantage, </span></span></span></span></span></span></span></span></span></span></span></div><div class="t m4 x11 h7 y25 ff1 fs5 fc0 sc0 ls98 ws9a">the <span class="lsc0 wsc2">ACM <span class="_ _d"> </span><span class="lsc1 ws62">copyright <span class="_ _10"></span><span class="lsc2 wsc3">notice <span class="_ _10"></span><span class="lsa8 wsa8">and </span></span></span></span>the <span class="lsc3 wsc4">title <span class="_ _e"> </span><span class="lsb2 wsb3">of <span class="_ _16"></span></span></span>the <span class="ls21 wsc5">publication <span class="_ _e"> </span><span class="lsa8 wsa8">and <span class="lsc4 wsc6">its <span class="lsc5 wsc">date <span class="lsc6 ws45">appear, </span></span></span></span></span></div><div class="t m4 x11 h7 y26 ff1 fs5 fc0 sc0 lsa8 wsa8">and <span class="lsc2 wsc3">notice <span class="_ _10"></span><span class="lsb4 wsb5">is <span class="_ _9"></span><span class="lsc7 wsc7">given <span class="_ _15"></span><span class="lsb7 wsb8">that <span class="_ _15"></span><span class="ls5d wsc8">copying <span class="lsb4 wsb5">is <span class="_ _13"></span><span class="lsa ws99">by <span class="_ _10"></span><span class="lsc8 wsc9">permission <span class="_ _13"></span><span class="lsb2 wsb3">of <span class="_ _16"></span><span class="ls98 ws9a">the <span class="_ _10"></span><span class="lsc9 wsca">Association <span class="lsbc wsbe">for </span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m4 x11 h7 y27 ff1 fs5 fc0 sc0 lsca wscb">Computing <span class="_ _f"></span><span class="lscb wscc">Machinery. <span class="_ _f"></span><span class="lscc wscd">To <span class="_ _f"></span><span class="lsa ws99">copy <span class="_ _10"></span><span class="lscd wsce">otherwise, <span class="_ _9"></span><span class="lsb1 wsb2">or <span class="_ _e"> </span><span class="lsad wsae">to <span class="_ _10"></span><span class="lsce wscf">republish, <span class="lscf wsd0">requires <span class="_ _c"></span><span class="lsd0 wsd1">a <span class="_ _15"></span><span class="lsaf wsb0">fee </span></span></span></span></span></span></span></span></span></span></div><div class="t m4 x11 h7 y28 ff1 fs5 fc0 sc0 lsd1 wsd2">and/or <span class="_"> </span><span class="lsd2 wsd3">specific <span class="lsd3 wsd4">permission. </span></span></div><div class="t m4 x11 h7 y29 ff1 fs5 fc0 sc0 lsd4 wsd5">0 </div><div class="t m5 x12 h8 y29 ff1 fs6 fc0 sc0 lsd5 wsd6">1989 <span class="_ _12"> </span><span class="lsd6 wsd7">ACM089791-338-3/89/0012/0202 </span></div><div class="t m4 x13 h7 y29 ff1 fs5 fc0 sc0 lsd7 wsd8">$1.50 </div><div class="t m1 x14 h3 y6 ff1 fs1 fc0 sc0 lsd8 wsd9">architectures; <span class="_ _17"> </span><span class="ls4b ws4c">this <span class="_"> </span><span class="ls8e ws8f">work <span class="_"> </span><span class="lsd9 wsda">relies <span class="_ _d"> </span><span class="ls52 ws53">on <span class="_ _e"> </span><span class="lsda wsb4">reliable, <span class="_ _5"> </span><span class="lsdb wsdb">synchronous </span></span></span></span></span></span></div><div class="t m1 x14 h3 y2a ff1 fs1 fc0 sc0 lsdc wsdc">broadcast <span class="_ _19"></span><span class="ls30 ws30">communication <span class="_ _d"> </span><span class="lsb wsb">as <span class="_ _1b"></span><span class="lsdd wsdd">provided <span class="_ _f"></span><span class="ls4d ws4e">by <span class="_ _10"></span><span class="ls19 ws19">the <span class="_ _15"></span><span class="ls57 ws57">system <span class="_ _1b"></span><span class="ls2c ws31">bus. </span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y2b ff1 fs1 fc0 sc0 ls56 ws56">A <span class="_ _16"></span><span class="ls28 ws28">distributed <span class="_ _10"></span><span class="ls29 ws29">system, <span class="_ _b"></span><span class="lsde wsde">however, <span class="_ _13"></span><span class="ls84 ws85">can <span class="_ _19"></span><span class="lsdf wsdf">experience <span class="_ _19"></span><span class="lse0 wse0">partial <span class="_ _f"></span><span class="ls31 ws32">fail- </span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y2c ff1 fs1 fc0 sc0 ls32 ws33">ures: <span class="_ _f"></span><span class="ls27 ws27">a <span class="_ _19"></span><span class="ls2c ws31">host <span class="_ _9"></span><span class="lse1 wse1">may <span class="_ _f"></span><span class="lse2 wse2">crash <span class="_ _9"></span><span class="ls5e ws5e">or <span class="lse3 wse3">messages <span class="_ _1f"></span><span class="lse1 wse1">may <span class="_ _15"></span><span class="ls27 ws27">be <span class="_ _c"></span><span class="lse4 wse4">lost. <span class="_ _e"></span><span class="lse5 wse5">Existing </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y2d ff1 fs1 fc0 sc0 lse6 wse6">approaches <span class="_ _14"></span><span class="ls3d ws3e">to <span class="_ _15"></span><span class="ls6c ws6c">consistency <span class="_ _9"></span><span class="ls54 ws55">for <span class="_ _15"></span><span class="ls55 ws1">file <span class="_ _e"> </span><span class="lse7 wse7">caches <span class="_ _1c"></span><span class="ls55 wse8">fall <span class="_ _12"> </span><span class="lse8 wse9">into <span class="ls3c ws3d">two <span class="_ _16"></span><span class="lse9 wsea">cat- </span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y2e ff1 fs1 fc0 sc0 lsea wseb">egories: <span class="_ _17"> </span><span class="lseb wsec">those <span class="_ _13"></span><span class="ls38 ws39">that <span class="_ _16"></span><span class="lsec wsed">assume <span class="_ _1b"></span><span class="lsed wsee">reliable <span class="_ _d"> </span><span class="lsee wsef">broadcast, <span class="_ _9"></span><span class="lsd wsd">and <span class="lsb wsb">so <span class="ls27 ws27">do </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y2f ff1 fs1 fc0 sc0 ls19 ws19">not <span class="_ _9"></span><span class="lsef wsf0">tolerate <span class="_ _9"></span><span class="ls30 ws30">communication <span class="_ _e"></span><span class="lsf0 wsa8">failures, <span class="_ _10"></span><span class="lsd wsd">and <span class="_ _b"></span><span class="lseb wsec">those <span class="_ _b"></span><span class="ls38 ws39">that <span class="_ _19"></span><span class="lsf1 wsf1">require </span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y30 ff1 fs1 fc0 sc0 ls27 ws27">a <span class="ls6c ws6c">consistency <span class="_ _10"></span><span class="lsf2 wsf2">check <span class="_ _10"></span><span class="ls54 ws55">for <span class="_ _f"></span><span class="lsf3 wsf3">every <span class="_ _f"></span><span class="lsf4 wsf4">read, </span></span></span></span></span></div><div class="t m3 x15 h6 y30 ff1 fs4 fc0 sc0 lsf5 wsf5">and </div><div class="t m1 x16 h3 y30 ff1 fs1 fc0 sc0 lsb wsb">so <span class="_ _13"></span><span class="ls55 wse8">fail <span class="_"> </span><span class="ls3d ws3e">to <span class="lsf6 wsf6">deliver </span></span></span></div><div class="t m1 x14 h3 y31 ff1 fs1 fc0 sc0 ls27 ws27">good <span class="_ _c"></span><span class="ls5b ws5b">performance. </span></div><div class="t m1 x17 h3 y32 ff1 fs1 fc0 sc0 ls26 ws26">In <span class="_ _12"> </span><span class="ls4b ws4c">this <span class="lsf7 wsf7">paper, <span class="_ _13"></span><span class="ls34 ws35">leases <span class="_ _1c"></span>are <span class="_ _19"></span><span class="ls35 ws36">proposed <span class="_ _a"></span><span class="lsb wsb">as <span class="_ _c"></span><span class="ls27 ws27">a <span class="_ _9"></span><span class="ls6c ws6c">consistency <span class="_ _9"></span><span class="ls5e ws5e">pro- </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y33 ff1 fs1 fc0 sc0 lsea wsf8">tocol <span class="_ _3"> </span><span class="ls38 ws39">that <span class="_ _12"> </span><span class="lsf8 wsf9">handles <span class="_ _16"></span><span class="ls2c ws31">host <span class="_ _e"> </span><span class="lsd wsd">and <span class="_ _e"></span><span class="ls30 ws30">communication <span class="_ _0"> </span><span class="ls45 ws46">failures <span class="_ _d"> </span><span class="lsf9 wsfa">us- </span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y34 ff1 fs1 fc0 sc0 ls1e ws1e">ing <span class="_ _12"> </span><span class="lsfa wsfb">physical <span class="_ _0"> </span><span class="lsfb wsfc">clocks. <span class="_ _4"> </span><span class="ls4f ws50">An <span class="_ _3"> </span><span class="ls50 ws51">analytic <span class="_"> </span><span class="ls51 ws52">model <span class="_ _12"> </span><span class="lsd wsd">and <span class="_ _10"></span><span class="ls52 ws53">an <span class="_ _16"></span><span class="lsfc wsfd">evalua- </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y35 ff1 fs1 fc0 sc0 lse8 wsfe">tion <span class="_ _e"></span><span class="lsfd wsff">using <span class="_ _13"></span><span class="ls55 ws1">file <span class="_ _f"></span><span class="ls3c ws3d">access <span class="_ _14"></span><span class="lsfe ws100">characteristics <span class="_ _9"></span><span class="ls1c ws1c">of <span class="_ _15"></span><span class="ls19 ws19">the <span class="_ _19"></span><span class="ls56 ws56">V <span class="_ _10"></span><span class="ls57 ws57">system <span class="_ _b"></span><span class="ls58 ws58">show </span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y36 ff1 fs1 fc0 sc0 ls38 ws39">that <span class="_ _10"></span><span class="lsff ws101">short-term <span class="ls34 ws35">leases <span class="_ _1b"></span><span class="ls5a ws5a">provide <span class="_ _e"></span><span class="ls100 ws102">near <span class="ls101 ws103">optimal <span class="_ _e"></span><span class="ls35 ws104">efficiency <span class="_ _d"> </span><span class="ls54 ws55">for </span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y37 ff1 fs1 fc0 sc0 ls27 ws27">a <span class="_ _c"></span><span class="ls32 ws33">large <span class="lsff ws105">class <span class="_ _19"></span><span class="ls1c ws1c">of <span class="_ _9"></span><span class="ls63 ws63">systems <span class="_ _b"></span><span class="ls40 ws41">in <span class="_ _e"></span><span class="lsea wseb">spite <span class="_ _9"></span><span class="ls1c ws1c">of <span class="_ _9"></span><span class="ls19 ws19">the <span class="ls102 ws106">fault-tolerance <span class="_ _15"></span><span class="ls5e ws5e">pro- </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y38 ff1 fs1 fc0 sc0 ls103 wsf6">visions. <span class="_ _11"> </span><span class="ls104 ws107">We <span class="ls24 ws24">argue <span class="_ _13"></span><span class="ls38 ws39">that <span class="_ _16"></span><span class="ls34 ws35">leases <span class="_ _19"></span>are <span class="_ _13"></span><span class="ls1c ws1c">of <span class="_ _16"></span><span class="ls105 ws108">increased <span class="_ _9"></span><span class="ls7e ws7e">benefit <span class="_ _16"></span><span class="ls40 ws41">in </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y39 ff1 fs1 fc0 sc0 ls106 ws109">future <span class="_ _16"></span><span class="ls28 ws28">distributed <span class="_ _e"></span><span class="ls63 ws63">systems <span class="_ _1b"></span><span class="ls1c ws1c">of <span class="_ _13"></span><span class="ls107 ws10a">larger <span class="_ _10"></span><span class="ls65 ws65">scale <span class="_ _a"></span><span class="ls4a ws4b">with <span class="_ _d"> </span><span class="ls4b ws4c">their <span class="_ _10"></span><span class="ls107 ws10a">larger </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y3a ff1 fs1 fc0 sc0 ls108 ws10b">ratio <span class="_ _12"> </span><span class="ls1c ws1c">of <span class="_ _10"></span><span class="ls67 ws67">processor <span class="_ _9"></span><span class="ls109 ws10c">speed <span class="_ _a"></span><span class="ls3d ws3e">to <span class="_ _f"></span><span class="ls10a ws10d">network <span class="_ _12"> </span><span class="ls10b ws10e">delay <span class="_ _f"></span><span class="lsd wsd">and <span class="ls107 ws10a">larger <span class="_ _f"></span><span class="ls34 ws35">ag- </span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y3b ff1 fs1 fc0 sc0 ls10c ws10f">gregate <span class="_ _a"></span><span class="ls10d ws110">rate <span class="_ _13"></span><span class="ls1c ws1c">of <span class="ls10e ws111">failure. </span></span></span></div><div class="t m1 x17 h3 y3c ff1 fs1 fc0 sc0 ls5c ws5c">The <span class="ls10f ws112">next <span class="_ _15"></span><span class="ls110 ws113">section <span class="_ _9"></span><span class="lsb6 ws114">describes <span class="_ _b"></span><span class="ls34 ws35">leases <span class="_ _1a"></span><span class="lsd wsd">and <span class="_ _1b"></span><span class="ls10b ws115">how <span class="ls111 ws116">they <span class="_ _10"></span><span class="ls34 ws35">are <span class="_ _b"></span><span class="ls112 ws117">used </span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y3d ff1 fs1 fc0 sc0 ls3d ws3e">to <span class="_ _12"> </span><span class="ls113 ws118">implement <span class="_"> </span><span class="ls87 ws88">cache <span class="ls1f ws1f">consistency. <span class="_ _1e"> </span><span class="ls114 ws119">Section <span class="_ _f"></span><span class="ls27 ws27">3 <span class="_ _e"></span><span class="ls115 ws11a">derives <span class="_ _16"></span><span class="ls116 ws11b">our </span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y3e ff1 fs1 fc0 sc0 ls117 ws11c">simple <span class="ls50 ws51">analytic <span class="_ _15"></span><span class="ls51 ws52">model <span class="_ _15"></span><span class="ls54 ws55">for <span class="_ _13"></span><span class="lsf1 wsf1">picking <span class="_ _16"></span><span class="ls118 ws11d">lease <span class="_ _b"></span><span class="lsf wsf">terms <span class="_ _19"></span><span class="lsd wsd">and <span class="_ _1c"></span><span class="ls83 ws11e">explores </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y3f ff1 fs1 fc0 sc0 ls4b ws4c">their <span class="_"> </span><span class="ls119 ws11f">application <span class="_ _0"> </span><span class="lsfd wsff">using <span class="_ _12"> </span><span class="ls3f ws40">data <span class="_ _15"></span><span class="ls11a ws120">from <span class="_ _12"> </span><span class="ls19 ws19">the <span class="_ _e"></span><span class="ls56 ws56">V <span class="_ _12"> </span><span class="ls28 ws28">distributed <span class="_ _d"> </span><span class="ls11b ws121">sys- </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y40 ff1 fs1 fc0 sc0 ls11c ws122">tem <span class="_ _16"></span><span class="ls11d ws123">[4]. <span class="_ _0"> </span><span class="ls114 ws119">Section <span class="_ _10"></span><span class="ls27 ws27">4 <span class="_ _15"></span><span class="lsb6 ws114">describes <span class="_ _19"></span><span class="ls21 ws21">some <span class="_ _c"></span><span class="ls11e ws124">optimizations <span class="_ _e"> </span><span class="ls40 ws41">in <span class="_ _12"> </span><span class="ls118 ws11d">lease </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y41 ff1 fs1 fc0 sc0 ls11f ws125">management. <span class="_ _0"> </span><span class="ls114 ws119">Section <span class="_ _16"></span><span class="ls27 ws27">5 <span class="_ _f"></span><span class="ls120 ws9e">examines <span class="_ _f"></span><span class="ls19 ws19">the <span class="_ _f"></span><span class="ls102 ws106">fault-tolerance <span class="_ _12"> </span><span class="ls1c ws1c">of </span></span></span></span></span></span></div><div class="t m1 x14 h3 y42 ff1 fs1 fc0 sc0 ls6f ws126">leasing. <span class="_ _1e"> </span><span class="ls114 ws119">Section <span class="_ _e"> </span><span class="ls27 ws27">6 <span class="_ _e"></span><span class="ls121 ws127">compares <span class="_ _9"></span><span class="ls34 ws35">leases <span class="_ _19"></span><span class="ls4a ws4b">with <span class="_ _0"> </span><span class="ls77 ws77">other <span class="_ _f"></span><span class="ls8e ws8f">work <span class="_"> </span><span class="ls52 ws53">on </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y43 ff1 fs1 fc0 sc0 ls28 ws28">distributed <span class="_ _12"> </span><span class="ls87 ws88">cache <span class="_ _13"></span><span class="ls6c ws6c">consistency <span class="_ _16"></span><span class="lsd wsd">and <span class="ls122 ws128">related <span class="_ _13"></span><span class="ls67 ws67">problems. <span class="_"> </span><span class="ls5c ws5c">The </span></span></span></span></span></span></div><div class="t m1 x14 h3 y44 ff1 fs1 fc0 sc0 ls123 ws129">concluding <span class="_ _12"> </span><span class="ls110 ws113">section <span class="ls124 ws12a">summarizes <span class="_ _19"></span><span class="ls116 ws11b">our <span class="_ _13"></span><span class="ls125 ws12b">results <span class="_ _9"></span><span class="lsd wsd">and <span class="_ _c"></span><span class="ls118 ws11d">speculates </span></span></span></span></span></span></div><div class="t m1 x14 h3 y45 ff1 fs1 fc0 sc0 ls52 ws53">on <span class="_ _f"></span><span class="ls126 ws12c">further <span class="_ _e"></span><span class="ls127 ws12d">applications <span class="_ _16"></span><span class="ls1c ws1c">of <span class="_ _10"></span><span class="ls34 ws35">leases <span class="_ _b"></span><span class="lsd wsd">and <span class="ls128 ws12e">directions <span class="_ _f"></span><span class="ls54 ws55">for <span class="_ _16"></span><span class="ls106 ws109">future </span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y46 ff1 fs1 fc0 sc0 ls129 ws12f">research. </div><div class="t m3 x14 h5 y47 ff1 fs3 fc0 sc0 ls68 ws68">2 <span class="_ _20"> </span><span class="ls12a wse4">Leases <span class="_ _1c"></span><span class="ls68 ws68">and <span class="_ _e"></span><span class="ls12b ws130">Cache <span class="_ _15"></span><span class="ls12c ws131">Consistency </span></span></span></span></div><div class="t m1 x14 h3 y48 ff1 fs1 fc0 sc0 ls56 ws56">A <span class="_ _12"> </span><span class="ls118 ws11d">lease <span class="_ _c"></span><span class="ls74 ws28">is <span class="_ _16"></span><span class="ls27 ws27">a <span class="lsea wseb">contract <span class="_ _15"></span><span class="ls38 ws39">that <span class="_ _10"></span><span class="ls12d ws132">gives <span class="_ _10"></span><span class="ls22 ws22">its <span class="_ _16"></span><span class="ls12e ws133">holder <span class="_ _f"></span><span class="ls12f ws134">specified <span class="_ _10"></span><span class="ls130 ws135">rights </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y49 ff1 fs1 fc0 sc0 ls131 ws136">over <span class="_ _10"></span><span class="ls6e ws137">property <span class="_ _12"> </span><span class="ls54 ws55">for <span class="_ _f"></span><span class="ls27 ws27">a <span class="_ _c"></span><span class="ls132 ws138">limited <span class="_"> </span><span class="ls133 ws139">period <span class="_ _f"></span><span class="ls1c ws1c">of <span class="_ _10"></span><span class="ls134 ws13a">time. <span class="_ _d"> </span><span class="ls26 ws26">In <span class="_ _e"> </span><span class="ls19 ws19">the <span class="_ _15"></span><span class="ls135 ws1d">context </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x18 h3 y4a ff1 fs1 fc0 sc0 ls1c ws1c">of <span class="_ _15"></span><span class="ls136 ws13b">caching, <span class="_ _16"></span><span class="ls27 ws27">a <span class="_ _19"></span><span class="ls118 ws11d">lease <span class="_ _c"></span><span class="ls133 ws139">grants <span class="_ _19"></span><span class="ls3d ws3e">to <span class="_ _10"></span><span class="ls22 ws22">its <span class="ls12e ws133">holder <span class="_ _f"></span><span class="ls137 ws13c">control <span class="_ _e"></span><span class="ls131 ws136">over <span class="ls138 ws13d">writes </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y4b ff1 fs1 fc0 sc0 ls3d ws3e">to <span class="_ _c"></span><span class="ls19 ws19">the <span class="_ _9"></span><span class="ls12 ws12">covered <span class="_ _a"></span><span class="ls139 ws13e">datum <span class="_ _1b"></span><span class="ls66 ws66">during <span class="_ _f"></span><span class="ls19 ws19">the <span class="_ _a"></span><span class="lsf ws13f">term <span class="_ _c"></span><span class="ls1c ws1c">of <span class="_ _c"></span><span class="ls19 ws19">the <span class="_ _a"></span><span class="ls80 ws81">lease, <span class="_ _b"></span><span class="ls4d ws4e">such <span class="_ _a"></span><span class="ls38 ws39">that </span></span></span></span></span></span></span></span></span></span></span></div><div class="t m1 x14 h3 y4c ff1 fs1 fc0 sc0 ls19 ws19">the <span class="ls13a ws140">server <span class="_ _9"></span><span class="ls2b ws2b">must <span class="ls13b ws141">obtain <span class="ls19 ws19">the <span class="_ _10"></span><span class="lsdd ws142">approval <span class="_ _10"></span><span class="ls1c ws1c">of </span></span>the <span class="_ _9"></span><span class="ls13c ws143">leaseholder <span class="_ _a"></span><span class="ls34 ws35">be- </span></span></span></span></span></span></div><div class="t m1 x18 h3 y4d ff1 fs1 fc0 sc0 ls7 ws144">fore <span class="_ _13"></span><span class="ls19 ws19">the <span class="_ _9"></span><span class="ls139 ws13e">datum <span class="_ _19"></span><span class="lse1 wse1">may <span class="ls27 ws27">be <span class="_ _19"></span><span class="ls45 ws46">written. <span class="_"> </span><span class="ls13d ws145">When <span class="ls27 ws27">a <span class="_ _19"></span><span class="ls13c ws143">leaseholder <span class="_ _1b"></span><span class="ls133 ws139">grants </span></span></span></span></span></span></span></span></span></div><div class="t m1 x18 h3 y29 ff1 fs1 fc0 sc0 lsdd ws142">approval <span class="_ _16"></span><span class="ls54 ws55">for <span class="_ _10"></span><span class="ls27 ws27">a <span class="_ _19"></span><span class="lsb8 ws146">write, <span class="_ _e"></span><span class="ls13e ws147">it <span class="_ _16"></span><span class="ls13f ws148">invalidates <span class="_ _f"></span><span class="ls22 ws22">its <span class="ls140 ws149">local <span class="_ _f"></span><span class="ls7c ws7c">copy <span class="_ _15"></span><span class="ls1c ws1c">of <span class="ls19 ws19">the <span class="_ _19"></span><span class="ls34 ws35">da- </span></span></span></span></span></span></span></span></span></span></span></div><div class="t m3 x19 h6 y4e ff1 fs4 fc0 sc0 ls141 ws14a">202 </div></div><div class="pi" data-data='{"ctm":[1.566069,0.000000,0.000000,1.566069,0.000000,0.000000]}'></div></div> </body> </html>
评论
    相关推荐