Total Order Communications Over Asynchronous Distributed Systems: Specifications And Implementations

During the last two decades the design and development of total order (TO) communications has been one of the main research topics in dependable distributed computing. The huge amount of researchwork has produced several TO specifications and a wide variety of TO implementations with different guarantees whose differences are often left hidden or unclear. This paper presents a systematic classification of six distinct TO specifications based on a well-defined formal framework.The classification allows us (i) to define in a formal way the differences among the behaviors of faulty and correct processes admitted by each specification, and (ii) to derive a methodology that enables the classification of TO implementations with respect to their enforced specification. The paper also discusses the impact of TO specifications on the design of application logics. The methodology is then usedto formally study the properties of eight variations of TO implementations based on a fixed sequencer given in a well-known context, namely primary component group communication systems