Publication

Probabilistic Guarantees on the Termination Time of a Consensus Algorithm in Asynchronous Systems

1997
Conference Papers

Abstract

Probabilistic Guarantees on the Termination Time of a Consensus Algorithm in Asynchronous Systems N. Sergent This paper is concerned with an application of Hierarchical Coloured Timed Petri Nets to the modelling and the performance evaluation of a distributed consensus algorithm. The asynchronous system model is augmented with Failure Suspectors, which allow to overcome the impossibility of reaching consensus in the presence of crash failures. We have used a top down modular approach to manage the complexity of the considered protocols. The termination time of the consensus algorithm is determined by the communications cost, i.e. by the timing characteristics of the network used for exchanging messages. Our model establishes a strong interdependence between the end-to-end delays and the amount of traffic on the network. As a network protocol we have considered UDP/IP. Simulating the consensus Petri net model, it is possible to obtain optimal values for the Failure Suspectors parameters. Probabilistic guarantees on the termination time of consensus are provided.

Official source

https://infoscience.epfl.ch/entities/publication/1b8986a4-14f6-4bb8-968e-385d279bc45e

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

1997
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/1b8986a4-14f6-4bb8-968e-385d279bc45e

About this result

Related concepts (32)

Internet protocol suite

The Internet protocol suite, commonly known as TCP/IP, is a framework for organizing the set of communication protocols used in the Internet and similar computer networks according to functional criteria. The foundational protocols in the suite are the Transmission Control Protocol (TCP), the User Datagram Protocol (UDP), and the Internet Protocol (IP). Early versions of this networking model were known as the Department of Defense (DoD) model because the research and development were funded by the United States Department of Defense through DARPA.

Communication protocol

A communication protocol is a system of rules that allows two or more entities of a communications system to transmit information via any variation of a physical quantity. The protocol defines the rules, syntax, semantics, and synchronization of communication and possible error recovery methods. Protocols may be implemented by hardware, software, or a combination of both. Communicating systems use well-defined formats for exchanging various messages.

Consensus (computer science)

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts.