Distributed Algorithms: 11th International Workshop, WDAG '97, Saarbrücken, Germany, September 24-26, 1997, Proceedings (Lecture Notes in Computer Science, 1320)

This Book Constitutes The Refereed Proceedings Of The 11th International Workshop On Distributed Algorithms, Wdag '97, Held In Saarbrücken, Germany, In September 1997. The Volume Presents 20 Revised Full Papers Selected From 59 Submissions. Also Included Are Three Invited Papers By Leading Researchers. The Papers Address A Variety Of Current Issues In The Area Of Distributed Algorithms And, More Generally, Distributed Systems Such As Various Particular Algorithms, Randomized Computing, Routing, Networking, Load Balancing, Scheduling, Message-passing, Shared-memory Systems, Communication, Graph Algorithms, Etc. Towards Fault-tolerant And Secure Agentry / F.b. Schneider -- Workflow Management : An Exercise In Distributed Computing / A. Reuter -- In Memory Of Anya Pogosyants / N. Lynch -- Verification Of The Randomized Consensus Algorithm Of Aspnes And Herlihy : A Case Study / A. Pogosyants, R. Segala, N. Lynch -- A Simple Dfs-based Algorithm For Linear Interval Routing / T. Eilam, S. Moran, S. Zaks -- Atm Layouts With Bounded Hop Count And Congestion / M. Flammini, E. Nardelli, G. Proietti -- Scheduling In Synchronous Networks And The Greedy Algorithm / K.-s. Lui, S. Zaks -- Rapid Convergence Of A Local Load Balancing Algorithm For Aynchronous Rings / J.e. Gehrke, C.g. Plaxton, R. Rajaraman -- Performing Tasks On Restartable Message-passing Processors / B.s. Chlebus, R. De Prisco, A.a. Shvartsman -- Revisting The Paxos Algorithm / R. De Prisco, B. Lampson, N. Lynch -- Heartbeat : A Timeout-free Failure Detector For Quiescent Reliable Communication / M.k. Aguilera, W. Chen., S. Toueg --^ Genuine Atomic Multicast / R. Guerraoui, A. Schiper -- Low-overhead Time-triggered Group Membership / S. Katz, P. Lincoln, J. Rushby -- Virtual Precedence In Asynchronous Systems : Concept And Applications / J.-m. Hélary, A. Mostéfaoui, M. Raynal -- Detecting Global Predicates In Distributed Systems With Clocks / S.d. Stoller -- Fault Tolerance Bounds For Memory Consistency / J. James, A.k. Singh -- Precedence-based Memory Models / V. Luchangco -- Strong Interaction Fairness In A Fully Distributed System With Unbounded Speed Variability / Y.-j. Joung, J.-y. Liao -- Reliable Communication Over Partially Authenticated Networks / A. Beimel, M. Franklin -- Self-stabilizing Depth-first Token Passing On Rooted Networks / C. Johnen [and Others] -- Secure Distributed Storage And Retrieval / J.a. Garay [and Others] --^ Optimal Wait-free Clock Synchronization Protocol On A Shared-memory Multi-processor System / M. Inoue [and Others] --. Transparent Support For Wait-free Transactions / M. Moir -- On Power Of Multi-objects / P. Jayanti, S. Khanna. Marios Mavronicolas, Philippas Tsigas, Eds. Includes Bibliographical References And Index. Towards fault-tolerant and secure agentry....Pages 1-14 Workflow management — An exercise in distributed computing....Pages 15-19 In memory of Anya Pogosyants....Pages 20-21 Verification of the randomized consensus algorithm of Aspnes and Herlihy: A case study....Pages 22-36 A simple DFS-Based algorithm for linear interval routing....Pages 37-51 ATM layouts with bounded hop count and congestion....Pages 52-65 Scheduling in synchronous networks and the greedy algorithm....Pages 66-80 Rapid convergence of a local load balancing algorithm for asynchronous rings....Pages 81-95 Performing tasks on restartable message-passing processors....Pages 96-110 Revisiting the Paxos algorithm....Pages 111-125 Heartbeat: A timeout-free failure detector for quiescent reliable communication....Pages 126-140 Genuine atomic multicast....Pages 141-154 Low-overhead time-triggered group membership....Pages 155-169 Virtual precedence in asynchronous systems: Concept and applications....Pages 170-184 Detecting global predicates in distributed systems with clocks....Pages 185-199 Fault tolerance bounds for memory consistency....Pages 200-214 Precedence-based memory models....Pages 215-229 Strong interaction fairness in a fully distributed system with unbounded speed variability....Pages 230-244 Reliable communication over partially authenticated networks....Pages 245-259 Self-stabilizing depth-first token passing on rooted networks....Pages 260-274 Secure distributed storage and retrieval....Pages 275-289 Optimal wait-free clock synchronization protocol on a shared-memory multi-processor system....Pages 290-304 Transparent support for wait-free transactions....Pages 305-319 On the power of multi-objects....Pages 320-332 This book constitutes the refereed proceedings of the 11th International Workshop on Distributed Algorithms, WDAG '97, held in Saarbrucken, Germany, in September 1997.The volume presents 20 revised full papers selected from 59 submissions. Concurrent programs are traditionally described in terms of processes, an abstraction that hides the identity of the processor doing the actual execution.