org.apache.giraph.examples

Class BrachaTouegDeadlockComputation

java.lang.Object

org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable<I,V,E>

org.apache.giraph.worker.WorkerAggregatorDelegator<I,V,E>

org.apache.giraph.graph.AbstractComputation<I,V,E,M,M>

org.apache.giraph.graph.BasicComputation<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockMessage>

org.apache.giraph.examples.BrachaTouegDeadlockComputation

All Implemented Interfaces:

AggregatorUsage, GiraphConfigurationSettable<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable>, ImmutableClassesGiraphConfigurable<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable>, TypesHolder<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockMessage,BrachaTouegDeadlockMessage>, Computation<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockMessage,BrachaTouegDeadlockMessage>, WorkerAggregatorUsage, WorkerBroadcastUsage, WorkerGlobalCommUsage, WorkerIndexUsage<org.apache.hadoop.io.LongWritable>, WorkerReduceUsage

public class BrachaTouegDeadlockComputation
extends BasicComputation<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockMessage>

This code demonstrates the Bracha Toueg deadlock detection algorithm. The Bracha Toueg algorithm is a distributed, asynchronous, centralized algorithm for deadlock detection. The algorithm is executed on a snapshot of a undirected graph which depicts the corresponding wait-for-graph. Consequently the algorithm works on directed graphs but assumes the possibility to communicate in both ways on all the edges. This is an adaptation of the standard algorithm for Giraph/Pregel system. Since the value of the vertex is dumped during checkpointing, the algorithm keeps all the state of the vertex in the value.

Field Summary

Fields

Modifier and Type	Field and Description
static LongConfOption	BRACHA_TOUEG_DL_INITIATOR_ID The deadlock detection initiator id

Constructor Summary

Constructors

Constructor and Description
BrachaTouegDeadlockComputation()

Method Summary

Modifier and Type	Method and Description
void	compute(Vertex<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable> vertex, Iterable<BrachaTouegDeadlockMessage> messages) Must be defined by user to do computation on a single Vertex.

Methods inherited from class org.apache.giraph.graph.AbstractComputation

addEdgeRequest, addVertexRequest, addVertexRequest, getContext, getMyWorkerIndex, getSuperstep, getTotalNumEdges, getTotalNumVertices, getWorkerContext, getWorkerCount, getWorkerForVertex, initialize, postSuperstep, preSuperstep, removeEdgesRequest, removeVertexRequest, sendMessage, sendMessageToAllEdges, sendMessageToMultipleEdges

Methods inherited from class org.apache.giraph.worker.WorkerAggregatorDelegator

aggregate, getAggregatedValue, getBroadcast, reduce, reduceMerge, setWorkerGlobalCommUsage

Methods inherited from class org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable

getConf, setConf

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.apache.giraph.conf.ImmutableClassesGiraphConfigurable

getConf

Methods inherited from interface org.apache.giraph.conf.GiraphConfigurationSettable

setConf

Methods inherited from interface org.apache.giraph.worker.WorkerBroadcastUsage

getBroadcast

Methods inherited from interface org.apache.giraph.worker.WorkerReduceUsage

reduce, reduceMerge

Methods inherited from interface org.apache.giraph.worker.WorkerAggregatorUsage

aggregate

Methods inherited from interface org.apache.giraph.aggregators.AggregatorUsage

getAggregatedValue

Field Detail

BRACHA_TOUEG_DL_INITIATOR_ID

public static final LongConfOption BRACHA_TOUEG_DL_INITIATOR_ID

The deadlock detection initiator id

Constructor Detail

BrachaTouegDeadlockComputation

public BrachaTouegDeadlockComputation()

Method Detail

compute

public void compute(Vertex<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable> vertex,
                    Iterable<BrachaTouegDeadlockMessage> messages)
             throws IOException

Description copied from class: AbstractComputation

Must be defined by user to do computation on a single Vertex.

Specified by:

compute in interface Computation<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockMessage,BrachaTouegDeadlockMessage>

Specified by:

compute in class AbstractComputation<org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockVertexValue,org.apache.hadoop.io.LongWritable,BrachaTouegDeadlockMessage,BrachaTouegDeadlockMessage>

Parameters:

vertex - Vertex

messages - Messages that were sent to this vertex in the previous superstep. Each message is only guaranteed to have a life expectancy as long as next() is not called.

Throws:

IOException