Alex A. Shvartsman Knihy

This collection explores various advanced topics in computer systems and distributed algorithms. It begins with discussions on lazy and speculative execution, and the quest for the most efficient failure detector for wait-free set agreement. The text delves into topological approaches to early-deciding set-agreement and presents an optimal algorithm for renaming using k-set-consensus. It examines the intersection of consensus and self-stabilization, alongside the costs associated with uniform protocols that adapt memory consumption based on interval contention. Further, the work addresses optimistic algorithms for partial database replication and revisits optimal clock synchronization, establishing upper and lower bounds in real-time systems. It highlights distributed priority inheritance for real-time and embedded systems and safe termination detection in asynchronous distributed environments, even when processes may crash and recover. The text also discusses lock-free dynamically resizable arrays and the construction of distributed spanners in doubling metric spaces. It compares mobile agent algorithms with message-passing algorithms and investigates incremental construction of k-dominating sets in wireless sensor networks. The efficiency of malicious interference in wireless networks is scrutinized, alongside self-stabilizing and self-organizing distributed algorithms. Additional topics include lightweight querying ser

The Colloquium on Structure, Information, Communication, and Complexity (SIROCCO) is an annual research meeting that explores the relationship between information and efficiency in decentralized computing. Celebrating its 15th anniversary this year, SIROCCO has established itself as a prominent forum for researchers interested in the principles governing the connection between local structural knowledge and global communication and computation complexity. Topics covered include distributed algorithms, compact data structures, information dissemination, labeling schemes, and combinatorial optimization, with applications in large-scale distributed systems like global computing platforms, peer-to-peer systems, social networks, and network protocols such as routing and broadcasting. SIROCCO 2008 took place in Villars-sur-Ollon, Switzerland, from June 17–20, featuring 52 submitted contributions. Each paper underwent a rigorous review process, with an average of 3.4 Program Committee members evaluating submissions. Ultimately, 22 high-quality contributions were selected for presentation and publication. The event also featured two invited speakers, Nicola Santoro and Boaz Patt-Shamir. Special thanks are extended to the SIROCCO Steering Committee, particularly Pierre Fraigniaud, for their enthusiasm and invaluable assistance in organizing the event.