PDF Publication Title:
Text from PDF Page: 014
[12] Jeffrey Dean and Sanjay Ghemawat. “MapReduce: a flexible data processing tool”. CACM 53.1 (Jan. 2010), pp. 72–77. [13] John Douceur and Jon Howell. Scalable Byzantine-Fault- Quantifying Clock Synchronization. Tech. rep. MSR-TR-2003- 67. MS Research, 2003. [14] John R. Douceur and Jon Howell. “Distributed directory service in the Farsite file system”. Proc. of OSDI. 2006, pp. 321–334. [15] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. “The Google file system”. Proc. of SOSP. Dec. 2003, pp. 29–43. [16] David K. Gifford. Information Storage in a Decentralized Com- puter System. Tech. rep. CSL-81-8. PhD dissertation. Xerox PARC, July 1982. [17] Lisa Glendenning et al. “Scalable consistency in Scatter”. Proc. of SOSP. 2011. [18] Jim Gray and Leslie Lamport. “Consensus on transaction com- mit”. ACM TODS 31.1 (Mar. 2006), pp. 133–160. [19] Pat Helland. “Life beyond Distributed Transactions: an Apos- tate’s Opinion”. Proc. of CIDR. 2007, pp. 132–141. [20] Maurice P. Herlihy and Jeannette M. Wing. “Linearizability: a correctness condition for concurrent objects”. ACM TOPLAS 12.3 (July 1990), pp. 463–492. [21] Leslie Lamport. “The part-time parliament”. ACM TOCS 16.2 (May 1998), pp. 133–169. [22] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. “Reconfigur- ing a state machine”. SIGACT News 41.1 (Mar. 2010), pp. 63– 73. [23] Barbara Liskov. “Practical uses of synchronized clocks in dis- tributed systems”. Distrib. Comput. 6.4 (July 1993), pp. 211– 219. [24] David B. Lomet and Feifei Li. “Improving Transaction-Time DBMS Performance and Functionality”. Proc. of ICDE (2009), pp. 581–591. [25] Jacob R. Lorch et al. “The SMART way to migrate replicated stateful services”. Proc. of EuroSys. 2006, pp. 103–115. [26] MarkLogic. MarkLogic 5 Product Documentation. 2012. [27] Keith Marzullo and Susan Owicki. “Maintaining the time in a distributed system”. Proc. of PODC. 1983, pp. 295–305. [28] Sergey Melnik et al. “Dremel: Interactive Analysis of Web- Scale Datasets”. Proc. of VLDB. 2010, pp. 330–339. [29] D.L. Mills. Time synchronization in DCNET hosts. Internet Project Report IEN–173. COMSAT Laboratories, Feb. 1981. [30] Oracle. Oracle Total Recall. 2012. [31] Andrew Pavlo et al. “A comparison of approaches to large-scale data analysis”. Proc. of SIGMOD. 2009, pp. 165–178. [32] Daniel Peng and Frank Dabek. “Large-scale incremental pro- cessing using distributed transactions and notifications”. Proc. of OSDI. 2010, pp. 1–15. [33] Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis II. “System level concurrency control for distributed database systems”. ACM TODS 3.2 (June 1978), pp. 178–198. [34] Alexander Shraer et al. “Dynamic Reconfiguration of Pri- mary/Backup Clusters”. Proc. of USENIX ATC. 2012, pp. 425– 438. [35] Jeff Shute et al. “F1 — The Fault-Tolerant Distributed RDBMS Supporting Google’s Ad Business”. Proc. of SIGMOD. May 2012, pp. 777–778. [36] Yair Sovran et al. “Transactional storage for geo-replicated sys- tems”. Proc. of SOSP. 2011, pp. 385–400. [37] Michael Stonebraker. Why Enterprises Are Uninterested in NoSQL. 2010. [38] Michael Stonebraker. Six SQL Urban Myths. 2010. [39] Michael Stonebraker et al. “The end of an architectural era: (it’s time for a complete rewrite)”. Proc. of VLDB. 2007, pp. 1150– 1160. [40] Alexander Thomson et al. “Calvin: Fast Distributed Transac- tions for Partitioned Database Systems”. Proc. of SIGMOD. 2012, pp. 1–12. [41] Ashish Thusoo et al. “Hive — A Petabyte Scale Data Ware- house Using Hadoop”. Proc. of ICDE. 2010, pp. 996–1005. [42] VoltDB. VoltDB Resources. 2012. A Paxos Leader-Lease Management The simplest means to ensure the disjointness of Paxos- leader-lease intervals would be for a leader to issue a syn- chronous Paxos write of the lease interval, whenever it would be extended. A subsequent leader would read the interval and wait until that interval has passed. TrueTime can be used to ensure disjointness without these extra log writes. The potential ith leader keeps a lower bound on the start of a lease vote from replica r as vleader = TT.now().earliest, computed before esend (de- i,r i,r fined as when the lease request is sent by the leader). Each replica r grants a lease at lease egrant, which hap- pens after ereceive (when the replica receives a lease re- i,r quest); the lease ends at tend = TT.now().latest + 10, i,r computed after ereceive. A replica r obeys the single- i,r vote rule: it will not grant another lease vote until TT.after(tend) is true. To enforce this rule across different incarnations of r, Spanner logs a lease vote at the grant- ing replica before granting the lease; this log write can be piggybacked upon existing Paxos-protocol log writes. Published in the Proceedings of OSDI 2012 14 i,r When the ith leader receives a quorum of votes (event equorum), it computes its lease interval as i leader leasei = [TT.now().latest, minr (vi,r ) + 10]. The lease is deemed to have expired at the leader when TT.before(min (vleader) + 10) is false. To prove disjoint- r i,r ness, we make use of the fact that the ith and (i + 1)th leaders must have one replica in common in their quo- rums. Call that replica r0. Proof: lease .end = min (vleader) + 10 i ri,r (by definition) (min) (by definition) (causality) (by definition) (single-vote) (causality) (by definition) minr(vleader) + 10 i,r ≤ vleader + 10 i,r0 send ≤ tabs(ei,r0) + 10 leader + 10 + 10 + 10 tend i,r0 vi,r0 tabs (esend ) i,r0 tabs (ereceive ) i,r0 ≤ tabs (ereceive ) + i,r0 ≤ tend i,r0 < tabs (egrant ) i+1,r0 ≤ tabs (equorum ) i+1 ≤ leasei+1 .start 10 tabs (egrant ) i+1,r0 tabs (equorum ) i+1 i,rPDF Image | Google Globally-Distributed Database
PDF Search Title:
Google Globally-Distributed DatabaseOriginal File Name Searched:
spanner-osdi2012.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |