Supporting Distributed, Concurrent, One-Way Constraints in User Interface Applications

Krishna A. Bharat and Scott E. Hudson
Graphics, Visualization & Usability Center
Georgia Institute of Technology,
Atlanta GA 30332-0280

E-mail: {kb, hudson}@cc.gatech.edu

This paper describes Doppler a new, fast algorithm for supporting concurrent, one-way constraints between objects situated in multiple address spaces. Because of their declarative nature, convenience, low amortized cost, and good match to interface tasks, constraints have been used to support a variety of user-interface activities. Unfortunately, nearly all existing constraint maintenance algorithms are sequential in nature, and cannot function effectively in a concurrent or distributed setting. The Doppler algorithm overcomes these limitations. It is a highly efficient distributed and concurrent algorithm (based on an efficient sequential algorithm for incremental, lazy updates). Doppler relies solely on asynchronous message passing, and does not require shared memory, synchronized clocks, or a global synchronization mechanism. It supports a high degree of concurrency by efficiently tracking potential cause and effect relationships between reads and writes, and allowing all causally independent operations to execute in parallel. This makes it scalable, and optimizes reads and writes by minimizing their blocking time.

KEYWORDS: Constraint Maintenance, Incremental Update, Concurrency, CSCW, Distributed Asynchronous Algorithms, Causal Consistency, Partially Ordered Time.

---

Back to the advance program
Back to UIST '95 home page