This book constitutes the refereed proceedings of the 15th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2008, held in Villars-sur-Ollon, Switzerland, in June 2008. The 22 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 52 submissions. The papers cover topics such as distributed algorithms, compact data structures, information dissemination, informative labeling schemes, combinatorial optimization, and others, with potential applications to large scale distributed systems including global...

Do-All Computing for Distributed Systems: Cooperation in the Presence of Adversity studies algorithmic issues associated with cooperative execution of multiple independent tasks by distributed computing agents including partitionable networks.

Recent results have shed light on the understanding of how adversity affects efficiency, by presenting failure-sensitive upper and lower bounds for Do-All in several models for computation. The ability to cooperatively perform a collection of tasks is key to solving a broad array of computation problems ranging from...