Distributed Computing and Networking
12th International Conference, ICDCN 2011, Bangalore, India, January 2-5, 2011, Proceedings
Erschienen am 10. Januar 2011
XVII, 420 Seiten
978-3-642-17679-1 (ISBN)
Beschreibung
This book constitutes the refereed proceedings of the 12th International Conference on Distributed Computing and Networking, ICDCN 2011, held in Bangalore, India, during January 2-5, 2011.
The 31 revised full papers and 3 revised short papers presented together with 3 invited lectures were carefully reviewed and selected from 140 submissions. The papers address all current issues in the field of distributed computing and networking. Being a leading forum for researchers and practitioners to exchange ideas and share best practices, ICDCN also serves as a forum for PhD students to share their research ideas and get quality feedback from the well-renowned experts in the field.
Weitere Details
Weitere Ausgaben
Inhalt
- Title
- Organization
- Table of Contents
- Invited Paper: The Inherent Complexity of Transactional Memory and What to Do about It
- The TM Approach to Concurrent Programming
- Formalizing TM
- Safety: Consistency Properties of TM
- Progress: Termination Guarantees for TM
- Predicting Performance
- Some Lower Bound Results
- The Cost of Validation
- The Consensus Number of TM
- Achieving Disjoint-Access Parallelism
- Privatization
- Avoiding Aborts
- Interlude: How Well Does TM Work in Practice?
- Concurrent Programming in a Post-TM Era
- Optimizing Coarse-Grain Programming
- Programming with Mini-transactions
- Summary
- References
- Sustainable Ecosystems: Enabled by Supply and Demand Management
- Introduction
- Motivation
- Role of the IT Ecosystem
- Available Energy or Exergy as a Metric
- Exergy
- Exergy Chain in IT
- Supply Side and Demand Side Management
- Architectural Framework
- Quantifying Lifetime Exergy Consumption
- Synthesis of a Sustainable Data Center Using Lifetime Exergy Analysis
- Demand Side Management of Sustainable Data Centers
- Coefficient of Performance of the Ensemble
- Supply Side of a Sustainable Data Center Design
- Integrated Supply-Demand Management of Sustainable Data Centers
- Applying Supply-Demand Framework to Other Ecosystems
- Summary and Conclusions
- References
- Unclouded Vision
- Introduction
- User Incentives
- The Cloud vs. the Mist
- Droplets
- Deployment Model
- Trust Fountains
- Backwards Provenance
- Handling 15 Minutes of Fame
- Droplications
- Digital Yurts
- Dust Clouds
- Evaporating Droplets
- Conclusions and Future Work
- References
- Generating Fast Indulgent Algorithms
- Introduction
- Model
- Related Work
- Asynchrony Detectors
- Implementing an Asynchrony Detector
- Proof of Correctness
- Generating Indulgent Algorithms for Colorless Tasks
- Task Definition
- Transformation Description
- Proof of Correctness
- A Protocol for Strong Indulgent Renaming
- Protocol Description
- Proof of Correctness
- Conclusions and Future Work
- References
- An Efficient Decentralized Algorithm for the Distributed Trigger Counting Problem
- Introduction
- A Deterministic Algorithm
- LayeredRand Algorithm
- Analysis of the LayeredRand Algorithm
- Correctness of the Algorithm
- Bound on the Message Complexity
- Bound on the MaxRcvLoad
- Handling Concurrency
- Processing Triggers and Coins
- End-of-Round Procedure
- Correctness of Algorithm
- Conclusions
- References
- Deterministic Dominating Set Construction in Networks with Bounded Degree
- Introduction
- Related Work
- Model and Preliminaries
- Proof of Bounds
- Lower Bound
- Upper Bound
- Conclusions
- References
- PathFinder: Efficient Lookups and Efficient Search in Peer-to-Peer Networks
- Introduction
- PathFinder Design
- Challenges
- System Model and Preliminaries
- Storing Objects
- Key Lookup
- Searching with Complex Queries
- Comparison and Analysis
- Conclusions
- References
- Single-Version STMs Can Be Multi-version Permissive (Extended Abstract)
- Introduction
- Preliminaries
- STM Properties
- The Design of PermiSTM
- CAS-Based PermiSTM
- Discussion
- References
- Correctness of Concurrent Executions of Closed Nested Transactions in Transactional Memory Systems
- Introduction
- Background and System Model
- Schedules
- Function Definitions
- Writes for Read Operations and Well-Formedness
- Serial Schedules
- Conflict Preserving Closed Nested Opacity
- Closed Nested Opacity
- Conflict Notion: optConf
- Membership Verification Algorithm
- Abort-Shielded Consistency
- ASC Class Definition
- Conclusion
- References
- Locality-Conscious Lock-Free Linked Lists
- Introduction
- Preliminaries and Data Structure
- Using a Freeze to Retire a Chunk
- The List Operations: Search, Insert and Delete
- The Insert Operation
- The Freeze Procedure
- Conclusion
- References
- Specification and Constant RMR Algorithm for Phase-Fair Reader-Writer Lock
- Introduction
- Model and Specification of the Reader-Writer Problem
- Reader-Priority and Writer-Priority Formulations
- Phase-Fairness Properties
- Related Work
- Single Writer Algorithm Satisfying Phase-Fair Properties
- Shared Variables and Their Purpose
- Multi-Writer Multi-Reader Phase-Fair Algorithm
- Informal Description of the Algorithm in Figure 3
- Shared Variables and Their Purpose
- Line by Line Commentary
- References
- On the Performance of Distributed Lock-Based Synchronization
- Introduction
- Motivation and Objectives
- Experimental Framework and Performance Analysis
- Our Findings
- Distributed Mutual Exclusion Algorithms
- Suzuki-Kasami's Token-Based Algorithm
- Ricart-Agrawala's Permission-Based Algorithm
- Maekawa's Permission-Based Algorithm
- Distributed Data Structures
- The Experimental Framework
- Performance Analysis and Results
- Counters
- A Queue
- A Stack
- A Linked List
- Discussion
- References
- Distributed Generalized Dynamic Barrier Synchronization
- Introduction
- Phase Synchronization Problem
- Barrier Synchronization with Dynamic Set of Processes
- Abstract Language
- Distributed Barrier Synchronization Solution
- Correspondance between Protocol Steps and Clock Operations
- How the Protocol Works
- Correctness of the Solution
- Generalization: Multi-clock Phase Synchronization
- Comparing with Other Dynamic Barrier Schemes
- Conclusions
- References
- A High-Level Framework for Distributed Processing of Large-Scale Graphs
- Introduction
- The HipG Model and Programming Interface
- Distributed Computation
- Coordination of Distributed Computations
- Hierarchical Coordination of Distributed Computations
- Implementation
- Memory Utilization and Performance Evaluation
- Related Work
- Conclusions and Future Work
- References
- Affinity Driven Distributed Scheduling Algorithm for Parallel Computations
- Introduction
- Related Work
- System and Computation Model
- Distributed Scheduling Algorithm
- Time Complexity Analysis
- Results and Analysis
- Detailed Performance Analysis
- Conclusions and Future Work
- References
- Temporal Specifications for Services with Unboundedly Many Passive Clients
- Introduction
- The Client Server Model
- Passive Clients
- Loan Approval Service
- $\mathfrak{L}_{SPS}$
- Syntax and Semantics
- Specification Examples Using $\mathfrak{L}_{SPS}$
- Satisfiability and Model Checking for $\mathfrak{L}_{SPS}$
- Model Checking Problem for $\mathfrak{L}_{SPS}$
- Discussion
- References
- Relating $L$-Resilience and Wait-Freedomvia Hitting Sets
- Introduction
- Model
- Colorless Tasks
- Relating $L$-Resilience and Wait-Freedom: Definitions
- Resolver Agreement Protocol
- From Wait-Freedom to $L$-Resilience
- The Doorway Protocol
- Solving T through the Doorway
- From $L$-Resilience to Wait-Freedom
- Abstract Simulation
- Solving T$_L$ through AS
- Related Work
- Side Remarks and Open Questions
- References
- Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information
- Introduction
- Methodology
- Related Work
- Model
- Results
- Combinatorial Lemmas
- Using the Almost-Everywhere Agreement Protocol in SODA06,FOCS06
- Algorithm
- Description of the Algorithm
- Proof of Correctness
- Asynchronous Version
- References
- A Necessary and Sufficient Synchrony Condition for Solving Byzantine Consensus in Symmetric Networks
- Introduction
- Computation Model
- Definitions
- $(n,x)$-Synchrony Property and Ambiguity
- Algorithm and Runs Satisfying an $(n,x)$-Synchrony Property
- An Impossibility Result
- A Set of Specific Runs
- An Impossibility
- Relating the Size of Connected Components and Ambiguity
- A Necessary and Sufficient Condition
- Conclusion
- References
- GoDisco: Selective Gossip Based Dissemination of Information in Social Community Based Overlays
- Introduction
- Related Works
- Approach
- Concepts
- GoDisco
- Evaluation
- Results
- Conclusion and Future Work
- References
- Mining Frequent Subgraphs to Extract Communication Patterns in Data-Centres
- Introduction
- Related Work
- Problem Description
- Terms Used
- Problem Definition
- Proposed Bottom-Up Approach: Algorithm Approx-Apriori
- Proposed Top-Down Approach: Matrix-ANDing
- Application of Proposed Technique on a Real-Life Example
- Experimental Evaluation
- Comparative Study of Different Algorithms to Observe the Effect of Various System Properties
- Properties of Identified Frequent Subgraphs
- Conclusion
- References
- On the Hardness of Topology Inference
- Introduction
- Minimal Network Tracing
- Term Definitions
- The Minimal Network Tracing Problem
- The Hardness of Minimal Network Tracing
- Unsolvable, or NP-Complete?
- Conclusion
- References
- An Algorithm for Traffic Grooming in WDM Mesh Networks Using Dynamic Path Selection Strategy
- Introduction
- General Problem Statement
- Proposed Approach
- Alternate Path Selection Strategy
- Traffic Grooming Algorithm
- Experimental Results
- Conclusions
- References
- Analysis of a Simple Randomized Protocol to Establish Communication in Bounded Degree Sensor Networks
- Introduction
- First Phase - Establishing Pair-Wise Communication
- Line Topology
- Technical Lemmas
- Arbitrary Bounded Degree Topology
- Simulation and Practical Bounds for Grid Network
- Second Phase: Compression Protocol
- Conclusion
- References
- Reliable Networks with Unreliable Sensors
- Introduction
- Related Work
- System Model
- Higher Level Tilings: Polyhexes
- Level-z Polyhexes and Connectivity
- On Fault Tolerance of WSN Regions
- Discussion
- References
- Energy Aware Fault Tolerant Routing in Two-Tiered Sensor Networks
- Introduction
- Fault Tolerant Routing Design
- Network Model
- Notation Used
- ILP Formulation for Fault Tolerant Routing (ILP-FTR)
- Justification of the ILP Equations
- Experimental Results
- Conclusions
- References
- Scheduling Randomly-Deployed Heterogeneous Video Sensor Nodes for Reduced Intrusion Detection Time
- Introduction
- Video Sensor Model
- Determining Cover Sets
- The Case of Heterogeneous AoV
- The Case of Very Small AoV
- Accuracy of the Proposed Method
- Criticality-Based Scheduling of Randomly Deployed Nodes with Cover Sets
- Fast Event Detection with Criticality Management
- Static Criticality-Based Scheduling
- Dynamic Criticality-Based Scheduling
- Conclusions
- References
- An Integrated Routing and Medium Access Control Framework for Surveillance Networks of Mobile Devices
- Introduction
- Related Work
- Meshed Tree Clustering
- Burst Forwarding Medium Access Control Protocol
- Simulation and Performance
- Conclusion
- References
- Security in the Cache and Forward Architecture for the Next Generation Internet
- Introduction
- Cache and Forward Architecture
- Security Analysis
- Privacy and File Propagation
- Secure Routing over the CNF Architecture
- Key and Trust Management
- Conclusions
- References
- Characterization of Asymmetry in Low-Power Wireless Links: An Empirical Study
- Introduction
- Experimental Methodology
- Performance Evaluation
- Transmitter
- Antenna
- Receiver
- Transmit-Receive Mode
- Environmental Conditions
- Related Work
- Conclusion and Future Work
- References
- Model Based Bandwidth Scavenging for Device Coexistence in Wireless LANs
- Introduction
- Dynamic Spectrum Access in WLANs
- Bandwidth Scavenging Approach
- Related Work
- Whitespace Characterization
- Whitespace Measurement and Model
- Primary User Topology and Traffic Profile
- Whitespace Analysis
- Model Based Access Strategy
- MBAS Scavenge Algorithm
- Functional Overview of MBAS
- MBAS Algorithmic Analysis
- Access Strategy Evaluation
- Implemented Strategies
- Comparison with VX Scheme and Benchmark
- Impacts of the Channel Sensing Granularity
- Performance Under Dynamic PU Traffic
- Conclusions
- References
- Minimal Time Broadcasting in Cognitive Radio Networks
- Introduction
- Motivation
- Related Work
- Our Contributions
- System Model
- Node
- Medium
- Network Operation
- ILP Formulation
- Heuristic Algorithm
- Heuristic 1
- Heuristic 2
- Time Complexity Analysis - Heuristic 1
- Time Complexity Analysis - Heuristic 2
- Simulation and Results
- Simulation Setup
- Results
- Discussion
- Conclusion
- References
- Traffic Congestion Estimation in VANETs and Its Application to Information Dissemination
- Introduction
- Measures of Congestion
- Estimating Congestion Using Beacon Relevance
- Simulation Results
- Congestion-Based Information Dissemination
- References
- A Tiered Addressing Scheme Based on a Floating Cloud Internetworking Model
- Introduction
- Background and Related Work
- The Floating Cloud Tiered Internetwork Model
- Inter-cloud Communications
- The Nesting Concept
- Nested Tiered Address Inside an ISP POP
- Tiered Addresses in a Stub AS
- Evaluation of the Tiered Address Scheme
- Applying Tiered Addresses
- Tiered Address vs. IP Address
- HD Ratio Analysis
- Conclusions
- References
- DHCP Origin Traceback
- Introduction
- Background
- Related Work
- Current Techniques for DHCP Traceback
- Our Approach to Add a New DHCP Traceback Option
- Addressing Fragmentation Attacks
- Addressing Full Path Traceback
- Private Traceback Option
- Approach to Secure the Traceback Options
- Experiment
- Conclusion
- References
- A Realistic Framework for Delay-Tolerant Network Routing in Open Terrains with Continuous Churn
- Introduction
- Related Work
- A Framework for Studying Open Terrains with Continuous Churn
- Terrain Model
- Open Terrains as Queues
- Equalizing the Open and Closed Terrains
- Simulation Setup
- Routing Protocols
- Mobility of Nodes
- Handling Transients
- Handling the Source and the Destination
- Performance Metrics
- Simulation Results
- Conclusions
- Future Work
- References
- Author Index
