Packing messages as a tool for boosting the performance of total ordering protocols
Published 22 November 2002
Roy Friedman, Robbert van Renesse
Citations82
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The main conclusion of this comparison is that message packing influences the performance of total ordering protocols under high load overwhelmingly more than any other optimization that was checked in this paper, both in terms of throughput and latency.
Abstract
This paper compares the throughput and latency of four protocols that provide total ordering. Two of these protocols are measured with and without message packing. We used a technique that buffers application messages for a short period of time before sending them, so more messages are packed together. The main conclusion of this comparison is that message packing influences the performance of total ordering protocols under high load overwhelmingly more than any other optimization that was checked in this paper, both in terms of throughput and latency. This improved performance is attributed to the fact that packing messages reduces the header overhead for messages, the contention on the network, and the load on the receiving CPUs.
Keywords
Computer Science
Communications of the ACMTime, clocks, and the ordering of events in a distributed system
8,437 Citations1978Leslie Lamport
A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events, and a bound is derived on how far out of synchrony the clocks can become.
Association for Computing Machinery eBooksTime, clocks, and the ordering of events in a distributed system
1,969 Citations2019Leslie Lamport
ACM Transactions on Computer SystemsReliable communication in the presence of failures
996 Citations1987Ken Birman, Thomas Joseph
A review of several uses for the protocols in the ISIS system, which supports fault-tolerant resilient objects and bulletin boards, illustrates the significant simplification of higher level algorithms made possible by the approach.
U-Net
719 Citations1995Thorsten von Eicken, Anindya Basu +2 more
The U-Net communication architecture provides processes with a virtual view of a network interface to enable userlevel access to high-speed communication devices and achieves TCP performance at maximum network bandwidth and demonstrates performance equivalent to Meiko CS-2 and TMC CM-5 supercomputers on a set of Split-C benchmarks.
ACM Transactions on Computer SystemsReliable broadcast protocols
676 Citations1984Jo-Mei Chang, N.F. Maxemchuk
Communications of the ACMHorus
626 Citations1996Robbert van Renesse, Ken Birman +1 more
The Horus system offers flexible group communication support for distributed applications, allowing applications to only pay for services they use, and for groups with different communication needs to coexist in a single system.
ACM SIGOPS Operating Systems ReviewExploiting virtual synchrony in distributed systems
606 Citations1987Ken Birman, Thomas Joseph
IEEE Transactions on Software EngineeringOrca: a language for parallel programming of distributed systems
393 Citations1992Henri E. Bal, M. Frans Kaashoek +1 more
Three example parallel applications in Orca, one of which is described in detail, are discussed, and one of the existing implementations, which is based on reliable broadcasting, is described.
Fbufs: a high-bandwidth cross-domain transfer facility
333 Citations1993Peter Druschel, Larry Peterson
The requirements for a cross-domain transfer facility are outlined, the design of the fbuf mechanism that meets these requirements are described, and the impact of fbufs on network performance is experimentally quantified.
ACM Transactions on Computer SystemsSequential consistency versus linearizability
269 Citations1994Hagit Attiya, Jennifer L. Welch
It is shown that, for all three data types, the worst-case response time is very sensitive to the assumptions that are made about the timing information available to the system, and that linearizability is more expensive than sequential consistency.
Exploiting virtual synchrony in distributed systems
262 Citations1987Ken Birman, Thomas Joseph
It is argued that this approach to building distributed and fault-tolerant software is more straightforward, more flexible, and more likely to yield correct solutions than alternative approaches.
ACM SIGOPS Operating Systems ReviewAn efficient reliable broadcast protocol
203 Citations1989M. Frans Kaashoek, Andrew S. Tanenbaum +1 more
This paper presents a (software) protocol that simulates reliable broadcast, even on an unreliable network, and is more efficient than previously published reliable broadcast protocols.
A framework for protocol composition in Horus
122 Citations1995Robbert van Renesse, Ken Birman +3 more
The work contributes a standard framework for protocol development and experimentation, provides a high performance implementation of the virtual synchrony model, and introduces a methodology for increasing the robustness of the protocol development process.
Strong and weak virtual synchrony in Horus
119 Citations2002Roy Friedman, Robbert van Renesse
This paper presents two variants of virtual synchrony, which are supported by Horus, and shows that in order to support this property, the application program has to block messages during view changes.
U-Net: A User-Level Network Interface for Parallel and Distributed Computing
104 Citations1997Abhik Basu
Fast message ordering and membership using a logical token-passing ring
93 Citations2002Yair Amir, L.E. Moser +3 more
The Totem protocol supports consistent concurrent operations by placing a total order on broadcast messages by including a sequence number in a token circulated around a logical ring that is imposed on a set of processors in a broadcast domain.
SIAM Journal on ComputingA Correctness Condition for High-Performance Multiprocessors
57 Citations1998Hagit Attiya, Roy Friedman
A formal and precise definition of this condition is given and an algorithm for providing hybrid consistency on distributed memory machines is presented and the response time is proved to be within a constant multiplicative factor of the (theoretical) optimal time bounds.
The Totem system
51 Citations2002L.E. Moser, P. M. Melliar‐Smith +4 more
The Totem system supports fault-tolerant applications in which distributed processes cooperate to perform a common task and in which replicated data must be updated consistently in the presence of asynchrony and faults.
The pinwheel asynchronous atomic broadcast protocols
46 Citations2002Flaviu Cristian, S. Mishra
Two asynchronous atomic broadcast protocols are discussed that provide fast delivery and stability times, use a small number of messages to accomplish a broadcast, distribute evenly the processing load, use efficient flow control techniques, and provide gracefully degraded performance in the presence of communication failures.
Distributed Systems EngineeringA performance comparison of asynchronous atomic broadcast protocols
42 Citations1994Flaviu Cristian, Richard Beijer +1 more
This paper reports discrete event simulation results that compare the performance of four asynchronous atomic broadcast protocols and shows that there is no overall best protocol.