1<!DOCTYPE html> 2<html lang="en"> 3<head> 4 <title>L2AW theorem</title> 5 6 <!-- Google Tag Manager --> 7
7<script>
vendor: 486 bytes, lines 7-19
7(function (w, d, s, l, i) { 8 w[l] = w[l] || []; 9 w[l].push({ 10 'gtm.start': 11 new Date().getTime(), event: 'gtm.js' 12 }); 13 var f = d.getElementsByTagName(s)[0], 14 j = d.createElement(s), dl = l != 'dataLayer' ? '&l=' + l : ''; 15 j.async = true; 16 j.src = 17 'https://www.googletagmanager.com/gtm.js?id=' + i + dl; 18 f.parentNode.insertBefore(j, f); 19 })(window, document, 'script', 'dataLayer', '
19GTM-PQ8H594
vendor: 3 bytes, line 19
19');
19</script>
19 20 <!-- End Google Tag Manager --> 21 22 <!-- Meta --> 23 <meta charset="utf-8"> 24 <meta http-equiv="X-UA-Compatible" content="IE=edge"> 25 <meta name="viewport" content="width=device-width, initial-scale=1.0"> 26 <meta name="description" content=""> 27 <meta name="author" content=""> 28 <link rel="shortcut icon" href="favicon.ico"> 29 <link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png"> 30 <link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png"> 31 <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png"> 32 <link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5"> 33 <meta name="msapplication-TileColor" content="#da532c"> 34 <meta name="theme-color" content="#ffffff"> 35 <link href='https://fonts.googleapis.com/css?family=Lato:300,400,300italic,400italic' rel='stylesheet' 36 type='text/css'> 37 <link href='https://fonts.googleapis.com/css?family=Montserrat:400,700' rel='stylesheet' type='text/css'> 38 <!-- FontAwesome JS --> 39
39<script defer src="https://use.fontawesome.com/releases/v5.1.0/js/all.js" 40 integrity="sha384-3LK/3kTpDE/Pkp8gTNp2gR/2gOiwQ6QaO7Td0zV76UFJVhqLl4Vl3KL1We6q6wR9" 41 crossorigin="anonymous"></script>
41 42 <!-- Global CSS --> 43 <link rel="stylesheet" href="assets/plugins/bootstrap/css/bootstrap.min.css"> 44 <!-- Plugins CSS --> 45 <link rel="stylesheet" href="assets/plugins/prism/prism.css"> 46 <!-- Theme CSS --> 47<!-- <link id="theme-style" rel="stylesheet" href="assets/css/theme-1.css">--> 48 <link id="theme-style" rel="stylesheet" href="assets/css/theme-2.css"> 49<!-- <link id="theme-style" rel="stylesheet" href="assets/css/theme-3.css">--> 50<!-- <link id="theme-style" rel="stylesheet" href="assets/css/theme-4.css">--> 51 <!-- GitHub Button --> 52
52<script async defer src="https://buttons.github.io/buttons.js"></script>
52 53 54 <!-- Greek Fonts --> 55 <link rel="stylesheet" href="fonts/stylesheet.css" type="text/css" charset="utf-8"/> 56 57 <style> 58 h2.greek { 59 font-family: 'dalekregular'; 60 } 61 62 h3.greek { 63 font-family: 'dalekregular'; 64 } 65 66 h4.greek { 67 font-family: 'dalekregular'; 68 } 69 70 h5.greek { 71 font-family: 'dalekregular'; 72 } 73 74 span.greek { 75 font-family: 'dalekregular'; 76 } 77 78 .responsive { 79 width: 100%; 80 max-width: 400px; 81 height: auto; 82 } 83 84 .center { 85 display: block; 86 margin-left: auto; 87 margin-right: auto; 88 width: 75%; 89 } 90 91 .embed-responsive-1by2::before{padding-top:152%} 92 </style> 93</head> 94 95<body data-spy="scroll"> 96 97<!-- Google Tag Manager (noscript) -->
vendor: 73 bytes, lines 97-99
97 98<noscript> 99 <iframe src="https://www.googletagmanager.com/ns.html?id=
99GTM-PQ8H594
vendor: 96 bytes, lines 99-101
99" 100 height="0" width="0" style="display:none;visibility:hidden"></iframe> 101</noscript>
102<!-- End Google Tag Manager (noscript) --> 103 104 105<!---//Facebook button code--> 106<div id="fb-root"></div>
107<script>(function (d, s, id) { 108 var js, fjs = d.getElementsByTagName(s)[0]; 109 if (d.getElementById(id)) return; 110 js = d.createElement(s); 111 js.id = id; 112 js.src = "//connect.facebook.net/en_US/sdk.js#xfbml=1&version=v2.0"; 113 fjs.parentNode.insertBefore(js, fjs); 114}(document, 'script', 'facebook-jssdk'));</script>
114 115 116<!-- ******HEADER****** --> 117<header id="header" class="header"> 118 <div class="container"> 119 <h1 class="logo float-left"> 120 <a class="scrollto" href="#promo"> 121 <span class="logo-title greek">L<sup>2</sup>AW</span> 122 </a> 123 </h1><!--//logo--> 124 <nav id="main-nav" class="main-nav navbar-expand-md float-right" role="navigation"> 125 126 <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbar-collapse"> 127 <span class="sr-only">Toggle navigation</span> 128 <span class="icon-bar"></span> 129 <span class="icon-bar"></span> 130 <span class="icon-bar"></span> 131 </button><!--//nav-toggle--> 132 133 <div class="navbar-collapse collapse" id="navbar-collapse"> 134 <ul class="nav navbar-nav"> 135 <li class="nav-item sr-only"><a class="nav-link scrollto" href="#promo">Home</a></li> 136 <li class="nav-item"><a class="nav-link scrollto" href="#about">L<sup>2</sup>AW theorem</a></li> 137 <li class="nav-item"><a class="nav-link scrollto" href="#alrs">Almost Local Reads</a></li> 138 <!-- <li class="nav-item"><a class="nav-link scrollto" href="#features">Features</a></li>--> 139 <li class="nav-item"><a class="nav-link scrollto" href="#poster">Poster</a></li> 140 <!-- <li class="nav-item"><a class="nav-link scrollto" href="#qna">Q & A</a></li>--> 141 <li class="nav-item last"><a class="nav-link scrollto" href="#contact">Contact</a></li> 142 </ul><!--//nav--> 143 </div><!--//navabr-collapse--> 144 </nav><!--//main-nav--> 145 </div> 146</header><!--//header--> 147 148<!-- ******PROMO****** --> 149<section id="promo" class="promo section offset-header"> 150 <div class="container text-center"> 151 <h3 class="title greek" style="color: white"> 152 <img height="120" src="assets/images/themis.png"> 153 L<sup>2</sup>AW theorem 154 </h3> 155 <p class="intro" style="color: #2a435c;"> Local Reads and Linearizable Asynchronous Replication</p> 156 <div class="btns"> 157 <!-- <a class="btn btn-cta-secondary" href="https://dl.acm.org/doi/10.1145/3447786.3456234" target="_blank">Paper</a>--> 158 <a class="btn btn-cta-secondary" href="https://2025.eurosys.org/posters/eurosys25posters-paper16.pdf" 159 target="_blank">Short Paper</a> 160 <a class="btn btn-cta-primary" href="https://www.slideshare.net/AntoniosKatsarakis/the-l2aw-theorem" 161 target="_blank">Poster</a> 162 <a class="btn btn-cta-primary" href="https://www.vldb.org/pvldb/vol18/p2831-giortamis.pdf">Full Paper (VLDB'25)</a> 163 <a class="btn btn-cta-primary" href="artifact.pdf" target="_blank">Artifact</a> 164 </div> 165 <ul class="meta list-inline"></ul> 166 </div><!--//container--> 167 <div class="social-media"> 168 <div class="social-media-inner container text-center"> 169 <ul class="list-inline mb-2"> 170 <li class="list-inline-item github-follow"><!-- Place this tag where you want the button to render. --> 171 <a class="github-button" href="https://github.com/akatsarakis" 172 aria-label="Follow @akatsarakis on GitHub">Follow @akatsarakis</a> 173 </ul> 174 </div> 175 </div> 176</section><!--//promo--> 177 178<!-- ******ABOUT****** --> 179<section id="about" class="docs section"> 180 <div class="container"> 181 <div class="docs-inner"> 182 <h2 class="title text-center">What is the <span class="greek">L<sup>2</sup>AW theorem</span> ?</h2> 183 184 <p class="intro"> 185 Ideally crash-tolerant replication protocols, 186 which are at the heart of read-intensive reliable datastores, must offer: 187 1) <i>local reads</i> (for performance), 188 2) <i>linearizability</i> (i.e., strong consistency), and 189 3) ensure safety under <i>asynchrony</i>. 190 <br><br> 191 However, existing crash-tolerant replication protocols provide up to two of the three above features: 192 <br><br> 193 <img src="assets/images/read-features.png" class="responsive; center"> 194 <br> 195 196 </p> 197 <div class="row"> 198 <div class="item col-lg-4 col-md-6 col-12"> 199 <div class="content"> 200 <h3 class="sub-title">1. RC protocols</h3>
201 May provide Asynchronous and Local Reads but can return stale values thus 202 relax consistency. 203 </div><!--//content--> 204 </div><!--//item--> 205 <div class="item col-lg-4 col-md-6 col-12"> 206 <div class="content"> 207 <h3 class="sub-title">1. LS protocols</h3> 208 Come with Linearizable and Local reads but cannot tolerate Asynchrony. 209 </div><!--//content--> 210 </div><!--//item--> 211 <div class="item col-lg-4 col-md-6 col-12"> 212 <div class="content"> 213 <h3 class="sub-title">2. RA protocols</h3> 214 Ensure Linearizability under Asynchrony but have costly reads involving multiple replicas. 215 </div><!--//content--> 216 </div><!--//item--> 217 </div><!--//row--> 218 219 <p class="theorem"> 220 <br> 221 This hints a fundamental tradeoff between consistency, asynchrony, and performance in crash-tolerant 222 protocols. 223 Inspired by the above we introduce and prove the L<sup>2</sup>AW impossibility which asserts that: <i>any 224 <b>L</b>inearizable <b>A</b>synchronous read/write register protocol that tolerates a crash (<b>W</b>ithout 225 blocking reads or writes), has no <b>L</b>ocal reads</i>. 226 </p> 227 </div><!--//docs-inner--> 228 </div><!--//container--> 229</section><!--//about--> 230 231<section id="alrs" class="docs section"> 232 <div class="container"> 233 <div class="docs-inner"> 234 <h2 class="title text-center">Almost Local Reads (ALRs)</h2> 235 <p class="alrs"> 236 Guided by the L<sup>2</sup>AW impossibility, we introduce the idea of <i>almost-local reads</i> (ALRs), 237 which can be implemented in a crash-tolerant and linearizable manner under asynchrony. ALRs inevitably have 238 higher latency than local (single-node) reads, but they are very lightweight, with computation and network 239 costs close to local reads. 240 <br><br> 241 242 <img src="assets/images/alrs.png" class="responsive; center"> 243 <br> 244 When applied to the protocols in all three corners of the 245 design space (i.e., RA, RC, LS), ALRs add the missing piece: 246 1) they improve the throughput for RA protocols 247 2) ensure linearizability for RC protocols and 248 3) allow LS protocols to safely operate under asynchrony. 249 </p> 250 </div><!--//docs-inner--> 251 </div><!--//container--> 252</section><!--//about--> 253 254 255<!-- ******Poster****** --> 256<section id="poster" class="docs section"> 257 <div class="container"> 258 <div class="docs-inner"> 259 <h2 class="title text-center">Eurosys '25 - best poster nominee ð</h2> 260<!-- <div class="embed-responsive embed-responsive-1by1" style="text-align: center;">--> 261 <div class="embed-responsive embed-responsive-1by2" style="text-align: center;"> 262<!-- <div class="embed-responsive embed-responsive-1by2" style="text-align: center;">--> 263 <iframe src="https://www.slideshare.net/slideshow/embed_code/key/LhYTZqDesaRCNk?hostedIn=slideshare&page=upload" 264 frameborder="0" marginwidth="0" marginheight="0" scrolling="no"></iframe> 265 </div> 266 </div><!--//docs-inner--> 267 </div><!--//container--> 268</section><!--//features--> 269 270 271<!-- ******Q & A****** --> 272<section id="qna" class="docs section"> 273 <div class="container"> 274 <div class="docs-inner"> 275 <h2 class="title text-center">Related Projects </span> 276 </h2> 277 <p> 278 <a href="https://hermes-protocol.com/" target="_blank"> 279 <img align="left" height="50" src="assets/images/hermes.png" style="margin-right: 5px;"> 280 </a> 281 </br> 282 <span class="greek"><a href="https://hermes-protocol.com/" target="_blank"> HERMES</a></span>: a 283 high-performance single-key fault-tolerant and strongly consistent replication protocol. 284 </br></br> 285 286 <a href="https://zeus-protocol.com/" target="_blank"> 287 <img align="left" height="50" src="assets/images/zeus.png" style="margin-right: 8px;"> 288 </a> 289 </br>
290 <span class="greek"><a href="https://zeus-protocol.com/" target="_blank"> ZEUS</a></span>: 291 locality-aware distributed (multi-key) transactions with high performance and reliability. 292 </p> 293 294 <br> 295 <br> 296 <h2 class="title text-center">License</h2> 297 <div class="info"> 298 <p> 299 The code and accompanied materials are freely distributed to the public under the <a 300 href="https://www.apache.org/licenses/LICENSE-2.0" target="_blank"> Apache 2.0 License</a>. 301 </p> 302 </div><!--//info--> 303 </div><!--//license-inner--> 304 </div><!--//container--> 305</section><!--//features--> 306 307 308<!-- ******CONTACT****** --> 309<section id="contact" class="contact section has-pattern"> 310 <div class="container"> 311 <div class="contact-inner"> 312 <h2 class="title text-center">Contact</h2> 313 <p class="intro text-center"> 314 If you have any questions regarding the <i>L<sup>2</sup>AW theorem</i> or <i>ALRs</i> do not 315 hesitate </br> 316 to contact Antonis Katsarakis ( antonios.katsarakis {at} huawei.com ).</p> 317 <div class="clearfix"></div> 318 319 </div><!--//contact-inner--> 320 </div><!--//container--> 321</section><!--//contact--> 322 323<!-- ******FOOTER****** --> 324<footer class="footer"> 325 <div class="container text-center"> 326 <!--/* This template is released under the Creative Commons Attribution 3.0 License. Please keep the attribution link below when using for your own project. Thank you for your support. :) If you'd like to use the template without the attribution, you can buy the commercial license via our website: themes.3rdwavemedia.com */--> 327 <!--<small class="copyright">Designed with <i class="fas fa-heart"></i> by <a href="https://themes.3rdwavemedia.com" target="_blank">Xiaoying Riley</a> for developers</small>--> 328 </div><!--//container--> 329</footer><!--//footer--> 330 331<!-- Javascript -->
332<script type="text/javascript" src="assets/plugins/jquery-3.3.1.min.js"></script>
vendor: 1 bytes, line 332
332
333<script type="text/javascript" src="assets/plugins/jquery.easing.1.3.js"></script>
vendor: 1 bytes, line 333
333
334<script type="text/javascript" src="assets/plugins/bootstrap/js/bootstrap.min.js"></script>
vendor: 1 bytes, line 334
334
335<script type="text/javascript" src="assets/plugins/jquery-scrollTo/jquery.scrollTo.min.js"></script>
vendor: 1 bytes, line 335
335
336<script type="text/javascript" src="assets/plugins/prism/prism.js"></script>
vendor: 1 bytes, line 336
336
337<script type="text/javascript" src="assets/js/main.js"></script>
337 338 339 340</body> 341</html> 342
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.