@article{SkrzypczakSchintkeSchuett2019, author = {Skrzypczak, Jan and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {Linearizable State Machine Replication of State-Based CRDTs without Logs}, journal = {arXiv}, arxiv = {http://arxiv.org/abs/1905.08733v1}, year = {2019}, abstract = {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.}, language = {en} } @inproceedings{SchintkeReinefeldHaridietal.2010, author = {Schintke, Florian and Reinefeld, Alexander and Haridi, Seif and Sch{\"u}tt, Thorsten}, title = {Enhanced Paxos Commit for Transactions on DHTs}, booktitle = {CCGRID}, publisher = {IEEE}, doi = {10.1109/CCGRID.2010.41}, pages = {448 -- 454}, year = {2010}, language = {en} } @inproceedings{ReinefeldSchuett2009, author = {Reinefeld, Alexander and Sch{\"u}tt, Thorsten}, title = {Out-of-Core Parallel Frontier Search with MapReduce}, volume = {5976}, booktitle = {HPCS}, publisher = {Springer}, doi = {10.1007/978-3-642-12659-8_24}, pages = {323 -- 336}, year = {2009}, language = {en} } @inproceedings{SchuettReinefeldSchintkeetal.2009, author = {Sch{\"u}tt, Thorsten and Reinefeld, Alexander and Schintke, Florian and Hennig, C.}, title = {Self-Adaptation in Large-Scale Systems: A Study on Structured Overlays Across Multiple Datacenters}, booktitle = {Architectures and Languages for Self-Managing Distributed Systems (SelfMan@SASO)}, doi = {10.1109/SASOW.2010.65}, year = {2009}, language = {en} } @inproceedings{SchuettMoserPlantikowetal.2008, author = {Sch{\"u}tt, Thorsten and Moser, Monika and Plantikow, Stefan and Schintke, Florian and Reinefeld, Alexander}, title = {A Transactional Scalable Distributed Data Store}, booktitle = {1st IEEE International Scalable Computing Challenge, co-located with CCGrid'08}, year = {2008}, language = {en} } @misc{AndrzejakReinefeldSchintkeetal.2008, author = {Andrzejak, Artur and Reinefeld, Alexander and Schintke, Florian and Sch{\"u}tt, Thorsten and Mastroianni, Carlo and Fragopoulou, Paraskevi and Kondo, Derrick and Malecot, Paul and Cosmin Silaghi, Gheorghe and Moura Silva, Luis and Trunfio, Paolo and Zeinalipour-Yazti, Demetris and Zimeo, Eugenio}, title = {Grid Architectural Issues: State-of-the-art and Future Trends}, number = {WHP-0004}, publisher = {Institute on Architectural Issues: Scalability, Dependability, Adaptability, CoreGRID - Network of Excellence}, year = {2008}, language = {en} } @inproceedings{ShafaatMoserGhodsietal.2008, author = {Shafaat, Tallat and Moser, Monika and Ghodsi, Ali and Sch{\"u}tt, Thorsten and Haridi, Seif and Reinefeld, Alexander}, title = {Key-Based Consistency and Availability in Structured Overlay Networks}, booktitle = {International ICST Conference on Scalable Information Systems}, year = {2008}, language = {en} } @phdthesis{Schuett2010, author = {Sch{\"u}tt, Thorsten}, title = {Range queries in distributed hash tables}, year = {2010}, language = {en} } @inproceedings{ReinefeldSchuettDoebbelin2010, author = {Reinefeld, Alexander and Sch{\"u}tt, Thorsten and D{\"o}bbelin, Robert}, title = {Very large pattern databases for heuristic search}, booktitle = {HPDC}, editor = {Hariri, Salim and Keahey, Kate}, publisher = {ACM}, doi = {10.1145/1851476.1851592}, pages = {803 -- 809}, year = {2010}, language = {en} } @incollection{ReinefeldSchintkeSchuettetal.2009, author = {Reinefeld, Alexander and Schintke, Florian and Sch{\"u}tt, Thorsten and Haridi, Seif}, title = {A Scalable, Transactional Data Store for Future Internet Services}, booktitle = {Towards the Future Internet - A European Research Perspective}, editor = {Tselentis, G. and Domingue, J. and Galis, A. and Gavras, A. and Hausheer, D. and Krco, S. and Lotz, V. and Zahariadis, T.}, publisher = {IOS Press}, doi = {10.3233/978-1-60750-007-0-148}, pages = {148 -- 159}, year = {2009}, language = {en} }