Analysing Randomized Distributed Algorithms
Identifieur interne : 002216 ( Istex/Corpus ); précédent : 002215; suivant : 002217Analysing Randomized Distributed Algorithms
Auteurs : Gethin NormanSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2004.
Abstract
Abstract: Randomization is of paramount importance in practical applications and randomized algorithms are used widely, for example in co-ordinating distributed computer networks, message routing and cache management. The appeal of randomized algorithms is their simplicity and elegance. However, this comes at a cost: the analysis of such systems become very complex, particularly in the context of distributed computation. This arises through the interplay between probability and nondeterminism. To prove a randomized distributed algorithm correct one usually involves two levels: classical, assertion-based reasoning, and a probabilistic analysis based on a suitable probability space on computations. In this paper we describe a number of approaches which allows us to verify the correctness of randomized distributed algorithms.
Url:
DOI: 10.1007/978-3-540-24611-4_11
Links to Exploration step
ISTEX:F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Analysing Randomized Distributed Algorithms</title><author><name sortKey="Norman, Gethin" sort="Norman, Gethin" uniqKey="Norman G" first="Gethin" last="Norman">Gethin Norman</name><affiliation><mods:affiliation>School of Computer Science, University of Birmingham, B15 2TT, Birmingham, United Kingdom</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: G.Norman@cs.bham.ac.uk</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-24611-4_11</idno><idno type="url">https://api.istex.fr/document/F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">002216</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002216</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Analysing Randomized Distributed Algorithms</title><author><name sortKey="Norman, Gethin" sort="Norman, Gethin" uniqKey="Norman G" first="Gethin" last="Norman">Gethin Norman</name><affiliation><mods:affiliation>School of Computer Science, University of Birmingham, B15 2TT, Birmingham, United Kingdom</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: G.Norman@cs.bham.ac.uk</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2004</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4</idno><idno type="DOI">10.1007/978-3-540-24611-4_11</idno><idno type="ChapterID">11</idno><idno type="ChapterID">Chap11</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Randomization is of paramount importance in practical applications and randomized algorithms are used widely, for example in co-ordinating distributed computer networks, message routing and cache management. The appeal of randomized algorithms is their simplicity and elegance. However, this comes at a cost: the analysis of such systems become very complex, particularly in the context of distributed computation. This arises through the interplay between probability and nondeterminism. To prove a randomized distributed algorithm correct one usually involves two levels: classical, assertion-based reasoning, and a probabilistic analysis based on a suitable probability space on computations. In this paper we describe a number of approaches which allows us to verify the correctness of randomized distributed algorithms.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Gethin Norman</name><affiliations><json:string>School of Computer Science, University of Birmingham, B15 2TT, Birmingham, United Kingdom</json:string><json:string>E-mail: G.Norman@cs.bham.ac.uk</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><abstract>Abstract: Randomization is of paramount importance in practical applications and randomized algorithms are used widely, for example in co-ordinating distributed computer networks, message routing and cache management. The appeal of randomized algorithms is their simplicity and elegance. However, this comes at a cost: the analysis of such systems become very complex, particularly in the context of distributed computation. This arises through the interplay between probability and nondeterminism. To prove a randomized distributed algorithm correct one usually involves two levels: classical, assertion-based reasoning, and a probabilistic analysis based on a suitable probability space on computations. In this paper we describe a number of approaches which allows us to verify the correctness of randomized distributed algorithms.</abstract><qualityIndicators><score>6.368</score><pdfVersion>1.3</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>834</abstractCharCount><pdfWordCount>14939</pdfWordCount><pdfCharCount>83054</pdfCharCount><pdfPageCount>35</pdfPageCount><abstractWordCount>114</abstractWordCount></qualityIndicators><title>Analysing Randomized Distributed Algorithms</title><genre.original><json:string>OriginalPaper</json:string></genre.original><chapterId><json:string>11</json:string><json:string>Chap11</json:string></chapterId><genre><json:string>conference [eBooks]</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>2004</copyrightDate></serie><host><editor><json:item><name>Christel Baier</name><affiliations><json:string>Institute for Theoretical Computer Science, Technical University Dresden, Germany</json:string><json:string>E-mail: baier@tcs.inf.tu-dresden.de</json:string></affiliations></json:item><json:item><name>Boudewijn R. Haverkort</name><affiliations><json:string>Centre for Telematics and Information Technology, Faculty for Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500, AE, Netherlands</json:string><json:string>E-mail: b.r.h.m.haverkort@utwente.nl</json:string></affiliations></json:item><json:item><name>Holger Hermanns</name><affiliations><json:string>VASY, INRIA, Grenoble Rhône-Alpes, France</json:string><json:string>E-mail: hermanns@cs.uni-sb.de</json:string></affiliations></json:item><json:item><name>Joost-Pieter Katoen</name><affiliations><json:string>Software Modeling and Verification, RWTH Aachen University, Germany</json:string><json:string>E-mail: katoen@cs.rwth-aachen.de</json:string></affiliations></json:item><json:item><name>Markus Siegle</name><affiliations><json:string>Institut für Technische Informatik, Universität der Bundeswehr München,</json:string><json:string>E-mail: markus.siegle@unibw.de</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Software Engineering</value></json:item><json:item><value>Operating Systems</value></json:item><json:item><value>Processor Architectures</value></json:item><json:item><value>Simulation and Modeling</value></json:item></subject><isbn><json:string>978-3-540-22265-1</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Validation of Stochastic Systems</title><genre.original><json:string>Proceedings</json:string></genre.original><bookId><json:string>978-3-540-24611-4</json:string></bookId><volume>2925</volume><pages><last>418</last><first>384</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>Book Series</json:string></genre><eisbn><json:string>978-3-540-24611-4</json:string></eisbn><copyrightDate>2004</copyrightDate><doi><json:string>10.1007/b98484</json:string></doi></host><publicationDate>2004</publicationDate><copyrightDate>2004</copyrightDate><doi><json:string>10.1007/978-3-540-24611-4_11</json:string></doi><id>F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4</id><score>1</score><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4/fulltext/pdf</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Analysing Randomized Distributed Algorithms</title><respStmt xml:id="ISTEX-API" resp="Références bibliographiques récupérées via GROBID" name="ISTEX-API (INIST-CNRS)"></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>SPRINGER</p></availability><date>2004</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Analysing Randomized Distributed Algorithms</title><author><persName><forename type="first">Gethin</forename><surname>Norman</surname></persName><email>G.Norman@cs.bham.ac.uk</email><affiliation>School of Computer Science, University of Birmingham, B15 2TT, Birmingham, United Kingdom</affiliation></author></analytic><monogr><title level="m">Validation of Stochastic Systems</title><title level="m" type="sub">A Guide to Current Research</title><idno type="pISBN">978-3-540-22265-1</idno><idno type="eISBN">978-3-540-24611-4</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/b98484</idno><idno type="BookID">978-3-540-24611-4</idno><idno type="BookTitleID">83139</idno><idno type="BookSequenceNumber">2925</idno><idno type="BookVolumeNumber">2925</idno><idno type="BookChapterCount">13</idno><editor><persName><forename type="first">Christel</forename><surname>Baier</surname></persName><email>baier@tcs.inf.tu-dresden.de</email><affiliation>Institute for Theoretical Computer Science, Technical University Dresden, Germany</affiliation></editor><editor><persName><forename type="first">Boudewijn</forename><forename type="first">R.</forename><surname>Haverkort</surname></persName><email>b.r.h.m.haverkort@utwente.nl</email><affiliation>Centre for Telematics and Information Technology, Faculty for Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500, AE, Netherlands</affiliation></editor><editor><persName><forename type="first">Holger</forename><surname>Hermanns</surname></persName><email>hermanns@cs.uni-sb.de</email><affiliation>VASY, INRIA, Grenoble Rhône-Alpes, France</affiliation></editor><editor><persName><forename type="first">Joost-Pieter</forename><surname>Katoen</surname></persName><email>katoen@cs.rwth-aachen.de</email><affiliation>Software Modeling and Verification, RWTH Aachen University, Germany</affiliation></editor><editor><persName><forename type="first">Markus</forename><surname>Siegle</surname></persName><email>markus.siegle@unibw.de</email><affiliation>Institut für Technische Informatik, Universität der Bundeswehr München,</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2004"></date><biblScope unit="volume">2925</biblScope><biblScope unit="page" from="384">384</biblScope><biblScope unit="page" to="418">418</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation>Karlsruhe University, Germany</affiliation></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation>Cornell University, NY, USA</affiliation></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName><affiliation>Utrecht University, The Netherlands</affiliation></editor><biblScope><date>2004</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesId">558</idno></series><idno type="istex">F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4</idno><idno type="DOI">10.1007/978-3-540-24611-4_11</idno><idno type="ChapterID">11</idno><idno type="ChapterID">Chap11</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2004</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: Randomization is of paramount importance in practical applications and randomized algorithms are used widely, for example in co-ordinating distributed computer networks, message routing and cache management. The appeal of randomized algorithms is their simplicity and elegance. However, this comes at a cost: the analysis of such systems become very complex, particularly in the context of distributed computation. This arises through the interplay between probability and nondeterminism. To prove a randomized distributed algorithm correct one usually involves two levels: classical, assertion-based reasoning, and a probabilistic analysis based on a suitable probability space on computations. In this paper we describe a number of approaches which allows us to verify the correctness of randomized distributed algorithms.</p></abstract><textClass><keywords scheme="Book Subject Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book Subject Group"><list><label>I</label><label>I16013</label><label>I1603X</label><label>I14029</label><label>I14045</label><label>I13014</label><label>I21025</label><item><term>Computer Science</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Logics and Meanings of Programs</term></item><item><term>Software Engineering</term></item><item><term>Operating Systems</term></item><item><term>Processor Architectures</term></item><item><term>Simulation and Modeling</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2004">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-3-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><original>false</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-540-24611-4</BookID><BookTitle>Validation of Stochastic Systems</BookTitle><BookSubTitle>A Guide to Current Research</BookSubTitle><BookVolumeNumber>2925</BookVolumeNumber><BookSequenceNumber>2925</BookSequenceNumber><BookDOI>10.1007/b98484</BookDOI><BookTitleID>83139</BookTitleID><BookPrintISBN>978-3-540-22265-1</BookPrintISBN><BookElectronicISBN>978-3-540-24611-4</BookElectronicISBN><BookChapterCount>13</BookChapterCount><BookCopyright><CopyrightHolderName>Springer Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2004</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16013" Priority="1" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I1603X" Priority="2" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I14029" Priority="3" Type="Secondary">Software Engineering</BookSubject><BookSubject Code="I14045" Priority="4" Type="Secondary">Operating Systems</BookSubject><BookSubject Code="I13014" Priority="5" Type="Secondary">Processor Architectures</BookSubject><BookSubject Code="I21025" Priority="6" Type="Secondary">Simulation and Modeling</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Christel</GivenName><FamilyName>Baier</FamilyName></EditorName><Contact><Email>baier@tcs.inf.tu-dresden.de</Email></Contact></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Boudewijn</GivenName><GivenName>R.</GivenName><FamilyName>Haverkort</FamilyName></EditorName><Contact><Email>b.r.h.m.haverkort@utwente.nl</Email></Contact></Editor><Editor AffiliationIDS="Aff6"><EditorName DisplayOrder="Western"><GivenName>Holger</GivenName><FamilyName>Hermanns</FamilyName></EditorName><Contact><Email>hermanns@cs.uni-sb.de</Email></Contact></Editor><Editor AffiliationIDS="Aff7"><EditorName DisplayOrder="Western"><GivenName>Joost-Pieter</GivenName><FamilyName>Katoen</FamilyName></EditorName><Contact><Email>katoen@cs.rwth-aachen.de</Email></Contact></Editor><Editor AffiliationIDS="Aff8"><EditorName DisplayOrder="Western"><GivenName>Markus</GivenName><FamilyName>Siegle</FamilyName></EditorName><Contact><Email>markus.siegle@unibw.de</Email></Contact></Editor><Affiliation ID="Aff4"><OrgDivision>Institute for Theoretical Computer Science</OrgDivision><OrgName>Technical University Dresden</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgDivision>Centre for Telematics and Information Technology, Faculty for Electrical Engineering, Mathematics and Computer Science</OrgDivision><OrgName>University of Twente</OrgName><OrgAddress><Postbox>P.O. Box 217</Postbox><Postcode>7500</Postcode><State>AE</State><Country>Netherlands</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgDivision>VASY</OrgDivision><OrgName>INRIA</OrgName><OrgAddress><City>Grenoble Rhône-Alpes</City><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgDivision>Software Modeling and Verification</OrgDivision><OrgName>RWTH Aachen University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgDivision>Institut für Technische Informatik</OrgDivision><OrgName>Universität der Bundeswehr München</OrgName><OrgAddress><Country> </Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part4"><PartInfo TocLevels="0"><PartID>4</PartID><PartSequenceNumber>4</PartSequenceNumber><PartTitle>Deductive Verification of Stochastic Systems</PartTitle><PartChapterCount>3</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Validation of Stochastic Systems</BookTitle></PartContext></PartInfo><Chapter ID="Chap11" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>11</ChapterID><ChapterDOI>10.1007/978-3-540-24611-4_11</ChapterDOI><ChapterSequenceNumber>11</ChapterSequenceNumber><ChapterTitle Language="En">Analysing Randomized Distributed Algorithms </ChapterTitle><ChapterFirstPage>384</ChapterFirstPage><ChapterLastPage>418</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2004</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>4</PartID><BookID>978-3-540-24611-4</BookID><BookTitle>Validation of Stochastic Systems</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff9"><AuthorName DisplayOrder="Western"><GivenName>Gethin</GivenName><FamilyName>Norman</FamilyName></AuthorName><Contact><Email>G.Norman@cs.bham.ac.uk</Email></Contact></Author><Affiliation ID="Aff9"><OrgDivision>School of Computer Science</OrgDivision><OrgName>University of Birmingham</OrgName><OrgAddress><City>Birmingham</City><Postcode>B15 2TT</Postcode><Country>United Kingdom</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>Randomization is of paramount importance in practical applications and randomized algorithms are used widely, for example in co-ordinating distributed computer networks, message routing and cache management. The appeal of randomized algorithms is their simplicity and elegance. However, this comes at a cost: the analysis of such systems become very complex, particularly in the context of distributed computation. This arises through the interplay between probability and nondeterminism. To prove a randomized distributed algorithm correct one usually involves two levels: classical, assertion-based reasoning, and a probabilistic analysis based on a suitable probability space on computations. In this paper we describe a number of approaches which allows us to verify the correctness of randomized distributed algorithms.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>Supported in part by the EPSRC grant GR/N22960.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Analysing Randomized Distributed Algorithms</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Analysing Randomized Distributed Algorithms</title></titleInfo><name type="personal"><namePart type="given">Gethin</namePart><namePart type="family">Norman</namePart><affiliation>School of Computer Science, University of Birmingham, B15 2TT, Birmingham, United Kingdom</affiliation><affiliation>E-mail: G.Norman@cs.bham.ac.uk</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference [eBooks]" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2004</dateIssued><copyrightDate encoding="w3cdtf">2004</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: Randomization is of paramount importance in practical applications and randomized algorithms are used widely, for example in co-ordinating distributed computer networks, message routing and cache management. The appeal of randomized algorithms is their simplicity and elegance. However, this comes at a cost: the analysis of such systems become very complex, particularly in the context of distributed computation. This arises through the interplay between probability and nondeterminism. To prove a randomized distributed algorithm correct one usually involves two levels: classical, assertion-based reasoning, and a probabilistic analysis based on a suitable probability space on computations. In this paper we describe a number of approaches which allows us to verify the correctness of randomized distributed algorithms.</abstract><relatedItem type="host"><titleInfo><title>Validation of Stochastic Systems</title><subTitle>A Guide to Current Research</subTitle></titleInfo><name type="personal"><namePart type="given">Christel</namePart><namePart type="family">Baier</namePart><affiliation>Institute for Theoretical Computer Science, Technical University Dresden, Germany</affiliation><affiliation>E-mail: baier@tcs.inf.tu-dresden.de</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Boudewijn</namePart><namePart type="given">R.</namePart><namePart type="family">Haverkort</namePart><affiliation>Centre for Telematics and Information Technology, Faculty for Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500, AE, Netherlands</affiliation><affiliation>E-mail: b.r.h.m.haverkort@utwente.nl</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Holger</namePart><namePart type="family">Hermanns</namePart><affiliation>VASY, INRIA, Grenoble Rhône-Alpes, France</affiliation><affiliation>E-mail: hermanns@cs.uni-sb.de</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Joost-Pieter</namePart><namePart type="family">Katoen</namePart><affiliation>Software Modeling and Verification, RWTH Aachen University, Germany</affiliation><affiliation>E-mail: katoen@cs.rwth-aachen.de</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Markus</namePart><namePart type="family">Siegle</namePart><affiliation>Institut für Technische Informatik, Universität der Bundeswehr München</affiliation><affiliation>E-mail: markus.siegle@unibw.de</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="Book Series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2004</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book Subject Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book Subject Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I14029">Software Engineering</topic><topic authority="SpringerSubjectCodes" authorityURI="I14045">Operating Systems</topic><topic authority="SpringerSubjectCodes" authorityURI="I13014">Processor Architectures</topic><topic authority="SpringerSubjectCodes" authorityURI="I21025">Simulation and Modeling</topic></subject><identifier type="DOI">10.1007/b98484</identifier><identifier type="ISBN">978-3-540-22265-1</identifier><identifier type="eISBN">978-3-540-24611-4</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">83139</identifier><identifier type="BookID">978-3-540-24611-4</identifier><identifier type="BookChapterCount">13</identifier><identifier type="BookVolumeNumber">2925</identifier><identifier type="BookSequenceNumber">2925</identifier><identifier type="PartChapterCount">3</identifier><part><date>2004</date><detail type="part"><title>Deductive Verification of Stochastic Systems</title></detail><detail type="volume"><number>2925</number><caption>vol.</caption></detail><extent unit="pages"><start>384</start><end>418</end></extent></part><recordInfo><recordOrigin>Springer Berlin Heidelberg, 2004</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2004</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer Berlin Heidelberg, 2004</recordOrigin></recordInfo></relatedItem><identifier type="istex">F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4</identifier><identifier type="DOI">10.1007/978-3-540-24611-4_11</identifier><identifier type="ChapterID">11</identifier><identifier type="ChapterID">Chap11</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer Berlin Heidelberg, 2004</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2004</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002216 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 002216 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= TelematiV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:F2CFF19BF4E33C55BF734FF85D6C77820CA7C9E4
|texte= Analysing Randomized Distributed Algorithms
}}
| This area was generated with Dilib version V0.6.31. |  |