Distributed Computing: 13th International Symposium, DISC'99, Bratislava, Slovak Republic, September 27-29, 1999, Proceedings (Lecture Notes in Computer Science, 1693)

Lecture Notes in Computer Science
	Distributed Computing
	Preface
	External Reviewers
	Table of Contents
A Case for Message Oriented Middleware
	Introduction
	Examples
		Stock Trading
		Home Shopping
	A Flow-Graph Model for Message Oriented Middleware
	Research Issues
		Model
		Scalability
		Distributed Implementation
		Message Reliability
		Message Ordering
		Optimistic Delivery
		Topology Changes
		Security
	Alternative Approaches
		Remote Method Invocation (RMI) Systems
		Database Systems
		Group Communication Systems
		Workflow Systems
	Related Work in Content-based Publish-Subscribe Systems
Revisiting the Weakest Failure Detector for Uniform Reliable Broadcast*
	Introduction
	Model
		Failure Patterns and Environments
		Failure Detectors
		Runs of Algorithms
	Failure Detector Transformations
	Uniform Reliable Broadcast
	Failure Detector Theta
	Using Theta to Implement Uniform Reliable Broadcast
	The Weakest Failure Detector for Uniform Reliable Broadcast
	On the Nature and Power of Failure Detectors
	Relation between Gf and Θ
	Related Work
	Concluding Remarks
Efficient Algorithms to Implement Unreliable Failure Detectors in Partially Synchronous Systems*
	Introduction
		Partial Synchrony
		Unreliable Failure Detectors
		Our Results
	The Model
		System Model
		Implementation of Failure Detectors
	A Basic Algorithm that Provides Weak Completeness
	Extending the Basic Algorithm to Provide Eventual Weak Accuracy
	Extending the Basic Algorithm to Provide Eventual Strong Accuracy
	Extending the Previous Algorithms to Provide Strong Completeness
	Performance Analysis
	Conclusions and Future Work
Solving Consensus Using Chandra-Toueg’s Unreliable Failure Detectors: A General Quorum-Based Approach
	Introduction
	Asynchronous Distributed System Model
		Asynchronous Distributed System with Process Crash Failures
		Unreliable Failure Detectors
	The Consensus Problem
		Definition
		Solving Consensus with Unreliable Failure Detectors
	The General Consensus Protocol
		Underlying Principles
		The Protocol
	Correctness Proof
		Validity
		Termination
		Uniform Agreement
	Discussion
		Cost of the Protocol
		Related Work
	Conclusion
A Dynamic Primary Configuration Group Communication Service
	Introduction
	Mathematical Foundations and Notation
	The DC Specification
	An Implementation of DC
		The Implementation
		Proof
	Atomic Read/Write Shared Memory Algorithm
		The Algorithm
		Proof
	Conclusions
Asynchronous Group Membership with Oracles
	Introduction
	The Model
		Oracles
		Views
		Computations
	The Specification
		Safety Properties
		Liveness Properties
	The Algorithm
		View Consensus
		Group Membership Service
	Concluding Remarks
Generic Broadcast*
	Introduction
	Generic Broadcast
		Problem Definition
		Reliable and Atomic Broadcast as Instances of Generic Broadcast
		Strict Generic Broadcast Algorithm
	System Model and Definitions
		Processes, Failures and Failure Detectors
		Delivery Latency
	Solving Generic Broadcast
		Overview of the Algorithm
		The Generic Broadcast Algorithm
		Proof of Correctness
		Strictness and Cost of the Generic Broadcast Algorithm
	Related Work
	Conclusions
Non-blocking Asynch ronous Byzantin e Quorum Systems
	Introduction
	Related Work
	Contributions
	Definitions and System Model
		System Model
		Failure Model
		Quorum Systems
		Byzantine Quorums in Asynchronous Systems
		Cost of Access
		Strategies and Load
	Asynchronous Access Cost Examples
		Paths System
		Threshold System
	Non-blocking Quorum Systems
		Existence of Non-blocking Quorum Systems
	Non-blocking Quorum Systems Constructions
		Threshold Failure Pattern
		Disjoint Failure Pattern
	Conclusion
Byzantine Agreement Secure against General Adversaries in the Dual Failure Model*
	Introduction
		Player Corruption
		Byzantine Agreement and Broadcast
		Previous Work
		Contributions
		Definitions and Notation
	Necessary Condition
	Optimally Resilient Protocols
		Protocol Elements and Code Notation
		Value Unification
		Agreement Protocol
	Efficiency Improvements by Early Stopping
		Protocol Modifications
		Value Unification
		Unicast
		Agreement Protocol
		Optimizations
		Comparison with Previous Results
Randomness Recycling in Constant-Round Private Computations
	Introduction
	Preliminaries
	The Protocols
		A 2-Private O(n)-Phase 2-Round Protocol
		Improving Randomness Complexity for 2-Private Protocols
	A t-Private 2-Round Protocol
	Conclusion
Abuse-Free Multi-party Contract Signing
	Introduction
	Model and Definitions
	Cryptographic Tools
		Discrete Logs
		Private Contract Signatures
	The Multi-party Contract-Signing Protocol
		Alternating Contract-Signing Protocols
		Protocol Description
	Protocol Correctness
	Efficiency
	Conclusions
Fair and Efficient Mutual Exclusion Algorithms (Extended Abstract)*
	Introduction
	Peterson\'s Algorithm and Bounding its Unfairness Index
	Reducing Unfairness Index and Overtake Index
	Improving Space Efficiency
	Improving Time Efficiency
	Algorithms for l-exclusion Problem
	Concluding Remarks
Fast and Scalable Mutual Exclusion*
	Introduction
	Fast-Path Algorithm
	Correctness Proof
		Mutual Exclusion
		Fast Path is Always Open in the Absence of Contention
	Concluding Remarks
The Congenial Talking Philosophers Problem in Computer Networks*
	Introduction
	Complexity Measures
	A Straightforward Decentralized Solution
	A Highly Concurrent Solution
	Conclusions and Future Work
Software Fault Tolerance of Concurrent Programs Using Controlled Re-execution*
	Introduction
	Model and Problem Statement
	Solving the Off-Line Predicate Control Problem
		Off-Line Mutual Exclusion
		Off-Line Readers Writers Problem
		Off-Line Independent Mutual Exclusion
		Off-Line Independent Read-Write Mutual Exclusion
		Algorithm
	Application to Software Fault Tolerance
	Concluding Remarks
DUALITY: An Architecture Independent Design Model for Parallel Systems Based on Partial Order Semantics
	Introduction
	Extending UNITY with Partial Order Based Structures
	DUALITY Design Model
	Example of Formal Transformation and Design Reuse
	Summary and Future Work
A New Rewrite Method for Proving Convergence of Self-Stabilizing Systems
	Introduction
	An Illustrating Example: Ghosh\'s 4-State Algorithm
	Self-Stabilizing Systems as String Rewrite Systems
	A First-Order Characterization of Cycles
	A Practical Proof Method
		Basic Procedure and phi-Refinement
		Beauquier-Debas Algorithm
	Compositionality
	Conclusion and Perspectives
Stabilization-Preserving Atomicity Refinement
	Introduction
	Model, Syntax, and Semantics
	Dining Philosophers Program
		Description
		Proof of Correctness of DP
	The Refinement
		High-Atomicity Program
		Composing DP and H
		Correctness of the Refinement
	Extensions and Concluding Remarks
		Semantics Refinement
		Generalization to Drinking Philosophers Problem
		Extension to Message-Passing Systems
Self-Testing/Correcting Protocols (Extended Abstract)
	Introduction
	Model and Definitions
	Self-Testing/Correcting under Environmental Malfunction
		The Agreement Function
		Self-Tester for Agreement: Reset Mode
		Self-Corrector for Agreement: Reset Mode
		Self-Tester/Corrector for Agreement: Parallel Mode
	Privacy-Preserving Self-Correctors
	Conclusions
Randomization Helps to Perform Tasks on Processors Prone to Failures*
	Introduction
	Model and Algorithmic Preliminaries
	Randomized Algorithm
		Algorithm RA
		Correctness of RA
		Analysis of RA
	Deterministic Computations
	Discussion
A New Scheduling Algorithm for General Strict Multithreaded Computations*
	Introduction
	The Model
	A Randomized Distributed Scheduling Algorithm
		Description
		Properties
		Complexity
	Conclusion
Consensus Numbers of Transactional Objects
	Introduction
		Related Results
		New Results
	Readable Base Objects
	Consensus Base Objects
	Read-Modify-Write Base Types
	A General Bound
	Open Questions
Linearizability in the Presence of Drifting Clocks and Under Different Delay Assumptions
	Introduction
	Framework
	Writes
		A Non-Linearizable, if Admissible, Execution
		Results for Specific Models of Delays
	Reads
		A Non-Linearizable, if Admissible, Execution
		Results for Specific Models of Delays
Maintenance of a Spanning Tree in Dynamic Networks
	Introduction
		Motivation and Existing Solutions
		Our Solution
	The Problem
		The Model
		Problem Definition
	Background
		The Tree Maintenance Algorithm of [ACK90]
		The Maintenance-of-Common Data Algorithm of [AS91]
	Our Algorithm
		Phase 1: Trees Approval
		Phase 2: Trees Merge
	Analysis
		Correctness
		Amortized Communication Complexity
		Quiescence Time
	Acknowledgments
Author Index