@misc{Skrzypczak, author = {Skrzypczak, Jan}, title = {Weakening Paxos Consensus Sequences for Commutative Commands}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65741}, abstract = {Consensus (agreement on a value) is regarded as a fundamental primitive in the design of fault tolerant distributed systems. A well-known solution to the consensus problem is Paxos. Extensions of the Paxos algorithm make it possible to reach agreement on a sequence of commands which can then be applied on a replicated state. However, concurrently proposed commands can create conflicts that must be resolved by ordering them. This thesis delivers an in-depth description of a Paxos-based algorithm to establish such command sequences, called Paxos Round Based Register (PRBR). In contrast to conventional approaches like Multi-Paxos, PRBR can manage multiple command sequences independently. Furthermore, each sequence is established in-place, which eliminates the need for managing multiple Paxos instances. PRBR is extended as part of this thesis to exploit the commutativity of concurrently proposed commands. As a result, conflict potential can be greatly reduced which increases the number of commands that can be handled by PRBR. This is shown for a number of workloads in an experimental evaluation.}, language = {en} } @misc{Skrzypczak, type = {Master Thesis}, author = {Skrzypczak, Jan}, title = {Weakening Paxos Consensus Sequences for Commutative Commands}, abstract = {Consensus (agreement on a value) is regarded as a fundamental primitive in the design of fault tolerant distributed systems. A well-known solution to the consensus problem is Paxos. Extensions of the Paxos algorithm make it possible to reach agreement on a sequence of commands which can then be applied on a replicated state. However, concurrently proposed commands can create conflicts that must be resolved by ordering them. This thesis delivers an in-depth description of a Paxos-based algorithm to establish such command sequences, called Paxos Round Based Register (PRBR). In contrast to conventional approaches like Multi-Paxos, PRBR can manage multiple command sequences independently. Furthermore, each sequence is established in-place, which eliminates the need for managing multiple Paxos instances. PRBR is extended as part of this thesis to exploit the commutativity of concurrently proposed commands. As a result, conflict potential can be greatly reduced which increases the number of commands that can be handled by PRBR. This is shown for a number of workloads in an experimental evaluation.}, language = {en} } @inproceedings{SkrzypczakSchintkeSchuett, author = {Skrzypczak, Jan and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {Linearizable State Machine Replication of State-Based CRDTs without Logs}, series = {Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019}, booktitle = {Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019}, doi = {10.1145/3293611.3331568}, pages = {455 -- 457}, 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 due to the use of distributed consensus or 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 such as 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} } @article{SkrzypczakSchintkeSchuett, author = {Skrzypczak, Jan and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {RMWPaxos: Fault-Tolerant In-Place Consensus Sequences}, series = {IEEE Transactions on Parallel and Distributed Systems}, volume = {31}, journal = {IEEE Transactions on Parallel and Distributed Systems}, number = {10}, issn = {1045-9219}, doi = {10.1109/TPDS.2020.2981891}, pages = {2392 -- 2405}, language = {en} } @inproceedings{ThostrupSkrzypczakJasnyetal., author = {Thostrup, Lasse and Skrzypczak, Jan and Jasny, Matthias and Ziegler, Tobias and Binnig, Carsten}, title = {DFI: The Data Flow Interface for High-Speed Networks}, series = {SIGMOD '21: International Conference on Management of Data}, booktitle = {SIGMOD '21: International Conference on Management of Data}, publisher = {ACM}, doi = {10.1145/3448016.3452816}, pages = {1825 -- 1837}, language = {en} } @article{SkrzypczakSchintke, author = {Skrzypczak, Jan and Schintke, Florian}, title = {Towards Log-Less, Fine-Granular State Machine Replication}, series = {Datenbank Spektrum}, volume = {20}, journal = {Datenbank Spektrum}, number = {3}, doi = {10.1007/s13222-020-00358-4}, pages = {231 -- 241}, language = {en} } @inproceedings{AlonsoBinnigPandisetal., author = {Alonso, Gustavo and Binnig, Carsten and Pandis, Ippokratis and Salem, Kenneth and Skrzypczak, Jan and Stutsman, Ryan and Thostrup, Lasse and Wang, Tianzheng and Wang, Zeke and Ziegler, Tobias}, title = {DPI: The Data Processing Interface for Modern Networks}, series = {9th Biennial Conference on Innovative Data Systems Research}, booktitle = {9th Biennial Conference on Innovative Data Systems Research}, abstract = {As data processing evolves towards large scale, distributed platforms, the network will necessarily play a substantial role in achieving efficiency and performance. Increasingly, switches, network cards, and protocols are becoming more flexible while programmability at all levels (aka, software defined networks) opens up many possibilities to tailor the network to data processing applications and to push processing down to the network elements. In this paper, we propose DPI, an interface providing a set of simple yet powerful abstractions flexible enough to exploit features of modern networks (e.g., RDMA or in-network processing) suitable for data processing. Mirroring the concept behind the Message Passing Interface (MPI) used extensively in high-performance computing, DPI is an interface definition rather than an implementation so as to be able to bridge different networking technologies and to evolve with them. In the paper we motivate and discuss key primitives of the interface and present a number of use cases that show the potential of DPI for data-intensive applications, such as analytic engines and distributed database systems.}, language = {en} } @article{SkrzypczakSchintkeSchuett, author = {Skrzypczak, Jan and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {Linearizable State Machine Replication of State-Based CRDTs without Logs}, series = {arXiv}, journal = {arXiv}, 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} } @article{SchuettSchintkeSkrzypczak, author = {Sch{\"u}tt, Thorsten and Schintke, Florian and Skrzypczak, Jan}, title = {Transactions on Red-black and AVL trees in NVRAM}, series = {arXiv}, journal = {arXiv}, language = {en} }