Distributed and Parallel Systems (eBook)

Contents 6
Preface 10
I PARALLEL AND DISTRIBUTED ALGORITHMS 14
THE WANDERING TOKEN: CONGESTION AVOIDANCE OF A SHARED RESOURCE 16
1. Introduction 16
2. System model and the wandering token idea 19
3. Simulation results 22
4. Conclusions 25
References 25
A LOCALITY OPTIMIZING ALGORITHM FOR DEVELOPING STREAM PROGRAMS IN IMAGINE 26
1. INTRODUCTION 26
2. D& C MATRIX
3. PROGRAMMING OPTIMIZATION FOR LOCALITY ENHANCEMENT 28
4. EXPERIMENTAL RESULTS AND ANALYSIS 32
5. CONCLUSION AND FUTURE WORK 34
ACKNOWLEDGEMENTS. 35
REFERENCES 35
GRANULAR SSOR PRECONDITIONING PLACED ON DYNAMIC SMP CLUSTERS WITH COMMUNICATION ON THE FLY 36
1. Introduction 36
2. Numerical problem formulation 38
3. Message passing implementation 39
4. Implementation in shared memory dynamic clusters 41
5. Conclusions 43
6. References 44
BULK SYNCHRONOUS PARALLEL ML WITH EXCEPTIONS 45
1. Introduction 45
2. Functional Bulk Synchronous Parallel Programming 46
3. Exceptions and BSML 48
4. An Exception Mechanism for BSML 49
5. Implementation 51
6. Experiments 52
7. Conclusion and Future Work 53
II NETWORKING AND COMMUNICATION 56
A NEW APPROACH TO MPI COLLECTIVE COMMUNICATION IMPLEMENTATIONS 58
1. Introduction 58
2. Related Work 59
3. Framework Architecture 60
4. Selection Logic 63
5. Conclusion and Future Work 66
References 67
SUPPORTING MPI APPLICATIONS IN P-GRADE PORTAL 68
1. Introduction 69
2. Direct MPI job submission 70
3. MPI job submission using the LCG broker 73
4. Experimental results 75
5. Conclusion 76
TUNED: AN OPEN MPI COLLECTIVE COMMUNICATIONS COMPONENT 78
1. Introduction 78
2. Related Work 79
3. Open MPI collective framework and basic components 80
4. New tuned collectives and decision module 80
5. Conclusions 84
References 85
SELF-HEALING NETWORK FOR SCALABLE FAULT TOLERANT RUNTIME ENVIRONMENTS 86
1. Introduction 86
2. Previous and Related Work 87
3. Self-Healing Network (SHN) 88
4. Routing Algorithm in SHN 90
5. Conclusions and Future Work 92
References 92
SUPPORTING SEAMLESS REMOTE I/O USING A PARALLEL NETCDF INTERFACE 94
1. Introduction 94
2. Remote I/O with a PnetCDF Interface 95
3. Performance Evaluation 97
4. RelatedWork 101
5. Summary 102
Acknowledgments 102
References 102
III GRID AND WEB SERVICES 105
OF WEB AND GRID SERVICES GENERATINGSEMANTICDESCRIPTIONS 106
1. Introduction 106
2. Web Ontology of Services (OWL-S) 107
3. Adding Semantics to the Stateful Services 107
4. Application Scenario 111
5. Related work 112
References 114
ORIENTED PRODUCTION GRIDS LEGACY CODE SUPPORT FOR SERVICE- 116
1. Introduction 116
2. GEMLCA and the P-GRADE portal 118
3. Dynamic Account Management for Legacy Code Services 118
4. Dynamic Testing of Legacy Code Services 121
5. Summary 124
CLIENT-SIDE TASK SUPPORT IN MATLAB FOR CONCURRENT DISTRIBUTED EXECUTION 126
Introduction 126
1. Model 127
2. Client Design 130
3. Client Implementation 130
4. Example 1:APECS and the HiPerSAT Server 132
5. Example 2:Dense Array EEG and Signal Discrimination 133
6. Conclusions and FutureWork 133
References 135
MESSAGE LEVEL SECURITY FOR GRID SERVICES USING S/MIME 136
1. Introduction 136
2. Message Level Security 137
3. S/MIME 137
4. S/MIME and HTTP 138
5. Implementation of S/MIME based Message Level Security 139
6. Evaluation 140
7. Conclusion 143
8. Acknowledgments 143
References 143
IV GRID INFRASTRUCTURE 146
FAULT TOLERANT GRID REGISTRY 148
1. Introduction 148
2. Overview of existing solutions 149
3. Overview of the Grid Registry 149
4. Fault-Tolerance and Data Synchronization 150
5. Performance evaluation 153
6. Summary and Future work 156
References 157
HIERARCHICAL LOCAL DESKTOP GRID SECURE APPLICATION DEPLOYMENT IN THE 158
1. Introduction 158
2. Desktop Grids 159
3. Hierarchy 160
4. Challenges and solutions 161
5. Conclusion and future work 165
6. Acknowledgement 166
References 166
COMPONENT FORTHEC-GMAMONITORING ARCHITECTURE DESIGNINGADISTRIBUTEDMEDIATOR 168
1. Introduction 168
2. The C-GMA Architecture and Components 169
3. The Distributed Mediator 172
4. Content-based Publish/Subscribe Systems 173
5. P/S Based Distributed Mediator 174
6. Conclusions 176
References 176
USER ORIENTED GRID TESTING 178
1. Introduction 178
2. General Grid Testing Model 179
3. Description of the P-GRADE Portal 181
4. Offered testing services by the P-GRADE Portal 182
5. Summary 187
References 188
V ADVANCED GRID TECHNIQUES 190
APPLICATION AND MIDDLEWARE TRANSPARENT CHECKPOINTING WITH TCKPT ON CLUSTERGRID 192
1. INTRODUCTION 192
2. CHECKPOINTING IN CLUSTERGRID 194
3. RELATED WORK 195
4. NOVEL APPROACH IN CHECKPOINTING 197
5. THE TOTALCHECKPOINT TOOL 198
6. INTERFACING SINGLE PROCESS CHECKPOINTERS 200
7. ACKNOWLEDGEMENT 201
8. CONCLUSION 201
REFERENCES 202
UML BASED GRID WORKFLOW MODELING UNDER ASKALON 204
1. Introduction 204
2. Related Work 205
3. Background 206
4. Modeling Grid Workflows with UML Activ Diagram 207
5. Teuta 210
6. Modeling a Real World Hydrological Workflow with Teuta 211
7. Conclusions and Future Work 212
References 213
A TAXONOMY OF GRID RESOURCE BROKERS* 214
1. Introduction 215
2. Related work 215
3. Taxonomy of Resource Brokers 216
4. Survey of the Resource Brokers 220
5. Open issues and future work 221
6. Conclusions 222
7. References 222
SPECULATIVE SCHEDULING SERVICE TOWARDSANAGENTINTEGRATED 224
1. Introduction 224
2. Describing job behaviour 225
3. Scheduling strategies 227
4. Simulation results 232
5. Summary and related work 234
References 235
Author Index 236

THE WANDERING TOKEN: CONGESTION AVOIDANCE OF A SHARED RESOURCE (p. 3-4)

Augusto Ciuffoletti
CoreGRID Institute of Grid Information, Resource and Workflow Monitoring Services
INFN/CNAF – Via Berti Pichat – 40127 Bologna

Abstract

In a distributed system where scalability is an issue, the problem of enforcing mutual exclusion often arises in a soft form: the infrequent failure of the mutual exclusion predicate is tolerated, without compromising the consistent operation of the overall system. For instance this occurs when the operation subject to mutual exclusion requires massive use of a shared resource.

We introduce a scalable soft mutual exclusion algorithm, based on token passing: one distinguished feature of our algorithm is that instead of introducing an overlay topology we adopt a random walk approach. The consistency of our proposal is evaluated by simulation, and we bone based network.

This algorithm is studied in the frame of the CoreGRID Institute of Grid Information, Resource and Workflow Monitoring Services, in cooperation with the FORTH Institute, in Greece.

Keywords: congestion avoidance, random walk, token circulation, self-stabilization, soft mutual exclusion.

1. Introduction

In an ideal distributed system all resources are equivalently able to play any role. However, in practical applications, it is often the case that the introduction of a centralized resource may be appropriate, in order to reduce the cost, or to improve the performance. The loss of scalability and fault tolerance, which is inherent to the introduction of a centralized resource, is accepted as a tradeoff.

In order to avoid congestion, an appropriate access control mechanism must be provided. It is a well known fact that locating such mechanism at resource-side exhibits several drawbacks: the resource must be designed to negotiate services, using an appropriate protocol which consumes a share of available resources, and clients should make appropriate use of such negotiation. Here we propose a client-side mechanism especially suited for environments where resource and networking infrastructure are legacy.

A congestion avoidance mechanism coordinates the access to the centralized resource. The basic requirement is that resource performance, as observed by the client, must be nominal as long as the overall load does not exceed resource capacity. When requests overtake the capacity of the resource, it should reproduce at client side the effect of an overload, but without stress for the resource. The mechanism must not introduce bounds on system size, other than those enforced by resource capacity: this excludes the adoption of centralized algorithms, that are not scalable, as well as distributed algorithms based on deterministic consensus, that have an heavy footprint.

As a case study, we consider a "Video on Demand" environment where video streams at 650Kbps (appropriate for low resolution movies) are delivered to a group of subscribers. The shared resource in a 200Mbps backbone, which saturates with 300 subscribers. We want that subscribers coordinate their access to the infrastructure in order to limit their access to the stream source, thus keeping the overall used bandwidth below 200Mbps. Only exceptionally such limit can be exceeded:

the Service Agreement states that bursts up to 400Mbps are delivered with an additional cost, and that packet delivery is not guaranteed over that further limit. This might justify a flexible control over the number of subscribers, that might go over the theoretical maximum of 300 subscribers.

Summarizing, unlike traditional mutual exclusion modeled by a concurrent write on a shared register, our problem statement includes the occasional occurrence of simultaneous access to the resource. This is due to the nature of the resource whose performance may degrade (in the case study, degradation is initially only financial) when many are executed simultaneously, but without damage for the consistency of the system. This is formally translated in the following definition: