TY - JOUR A1 - Skrzypczak, Jan A1 - Schintke, Florian A1 - Schütt, Thorsten T1 - Linearizable State Machine Replication of State-Based CRDTs without Logs JF - arXiv N2 - General solutions of state machine replication have to ensure that all replicas apply the same commands in the same order, even in the presence of failures. Such strict ordering incurs high synchronization costs caused by distributed consensus or by the use of a leader. This paper presents a protocol for linearizable state machine replication of conflict-free replicated data types (CRDTs) that neither requires consensus nor a leader. By leveraging the properties of state-based CRDTs - in particular the monotonic growth of a join semilattice - synchronization overhead is greatly reduced. In addition, updates just need a single round trip and modify the state `in-place' without the need for a log. Furthermore, the message size overhead for coordination consists of a single counter per message. While reads in the presence of concurrent updates are not wait-free without a coordinator, we show that more than 97% of reads can be handled in one or two round trips under highly concurrent accesses. Our protocol achieves high throughput without auxiliary processes like command log management or leader election. It is well suited for all practical scenarios that need linearizable access on CRDT data on a fine-granular scale. Y1 - 2019 ER - TY - CHAP A1 - Schintke, Florian A1 - Reinefeld, Alexander A1 - Haridi, Seif A1 - Schütt, Thorsten T1 - Enhanced Paxos Commit for Transactions on DHTs T2 - CCGRID Y1 - 2010 U6 - https://doi.org/10.1109/CCGRID.2010.41 SP - 448 EP - 454 PB - IEEE ER - TY - CHAP A1 - Reinefeld, Alexander A1 - Schütt, Thorsten T1 - Out-of-Core Parallel Frontier Search with MapReduce T2 - HPCS Y1 - 2009 U6 - https://doi.org/10.1007/978-3-642-12659-8_24 VL - 5976 SP - 323 EP - 336 PB - Springer ER - TY - CHAP A1 - Schütt, Thorsten A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Hennig, C. T1 - Self-Adaptation in Large-Scale Systems: A Study on Structured Overlays Across Multiple Datacenters T2 - Architectures and Languages for Self-Managing Distributed Systems (SelfMan@SASO) Y1 - 2009 U6 - https://doi.org/10.1109/SASOW.2010.65 ER - TY - CHAP A1 - Schütt, Thorsten A1 - Moser, Monika A1 - Plantikow, Stefan A1 - Schintke, Florian A1 - Reinefeld, Alexander T1 - A Transactional Scalable Distributed Data Store T2 - 1st IEEE International Scalable Computing Challenge, co-located with CCGrid’08 Y1 - 2008 ER - TY - GEN A1 - Andrzejak, Artur A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten A1 - Mastroianni, Carlo A1 - Fragopoulou, Paraskevi A1 - Kondo, Derrick A1 - Malecot, Paul A1 - Cosmin Silaghi, Gheorghe A1 - Moura Silva, Luis A1 - Trunfio, Paolo A1 - Zeinalipour-Yazti, Demetris A1 - Zimeo, Eugenio T1 - Grid Architectural Issues: State-of-the-art and Future Trends Y1 - 2008 UR - http://coregrid.ercim.eu//mambo/images/stories/WhitePapers/whp-0004.pdf IS - WHP-0004 PB - Institute on Architectural Issues: Scalability, Dependability, Adaptability, CoreGRID - Network of Excellence ER - TY - CHAP A1 - Shafaat, Tallat A1 - Moser, Monika A1 - Ghodsi, Ali A1 - Schütt, Thorsten A1 - Haridi, Seif A1 - Reinefeld, Alexander T1 - Key-Based Consistency and Availability in Structured Overlay Networks T2 - International ICST Conference on Scalable Information Systems Y1 - 2008 ER - TY - THES A1 - Schütt, Thorsten T1 - Range queries in distributed hash tables Y1 - 2010 UR - http://www.dr.hut-verlag.de/978-3-86853-370-5.html ER - TY - CHAP A1 - Reinefeld, Alexander A1 - Schütt, Thorsten A1 - Döbbelin, Robert ED - Hariri, Salim ED - Keahey, Kate T1 - Very large pattern databases for heuristic search T2 - HPDC Y1 - 2010 U6 - https://doi.org/10.1145/1851476.1851592 SP - 803 EP - 809 PB - ACM ER - TY - CHAP A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten A1 - Haridi, Seif ED - Tselentis, G. ED - Domingue, J. ED - Galis, A. ED - Gavras, A. ED - Hausheer, D. ED - Krco, S. ED - Lotz, V. ED - Zahariadis, T. T1 - A Scalable, Transactional Data Store for Future Internet Services T2 - Towards the Future Internet - A European Research Perspective Y1 - 2009 U6 - https://doi.org/10.3233/978-1-60750-007-0-148 SP - 148 EP - 159 PB - IOS Press ER -