[jira] [Created] (GIRAPH-1136) Giraph no longer checkpoints loading input

2017-03-16 Thread Nic Eggert (JIRA)
Nic Eggert created GIRAPH-1136:
--

 Summary: Giraph no longer checkpoints loading input
 Key: GIRAPH-1136
 URL: https://issues.apache.org/jira/browse/GIRAPH-1136
 Project: Giraph
  Issue Type: Bug
  Components: bsp
Affects Versions: 1.2.0
Reporter: Nic Eggert


>From Practical Analytics with Apache Giraph:
{quote}
If checkpoints are enabled, you are guaranteed to have the initial graph data 
safely stored in HDFS.
{quote}

Looking at the current code in 
{{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is no 
longer the case. After a little bit of digging, it looks like this change was 
introduced here: 
https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
 (GIRAPH-993)

Was this change intentional? It seems like an initial checkpoint would be 
desirable (I have a job where 1/3 of the runtime is spent loading input splits).

The simplest fix would be to just add a special case for Superstep 0. If that's 
acceptable, I'd be happy to submit a PR.



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)


[jira] [Updated] (GIRAPH-1136) Giraph no longer checkpoints after loading input

2017-03-16 Thread Nic Eggert (JIRA)

 [ 
https://issues.apache.org/jira/browse/GIRAPH-1136?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Nic Eggert updated GIRAPH-1136:
---
Summary: Giraph no longer checkpoints after loading input  (was: Giraph no 
longer checkpoints loading input)

> Giraph no longer checkpoints after loading input
> 
>
> Key: GIRAPH-1136
> URL: https://issues.apache.org/jira/browse/GIRAPH-1136
> Project: Giraph
>  Issue Type: Bug
>  Components: bsp
>Affects Versions: 1.2.0
>Reporter: Nic Eggert
>
> From Practical Analytics with Apache Giraph:
> {quote}
> If checkpoints are enabled, you are guaranteed to have the initial graph data 
> safely stored in HDFS.
> {quote}
> Looking at the current code in 
> {{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is 
> no longer the case. After a little bit of digging, it looks like this change 
> was introduced here: 
> https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
>  (GIRAPH-993)
> Was this change intentional? It seems like an initial checkpoint would be 
> desirable (I have a job where 1/3 of the runtime is spent loading input 
> splits).
> The simplest fix would be to just add a special case for Superstep 0. If 
> that's acceptable, I'd be happy to submit a PR.



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)


[jira] [Updated] (GIRAPH-1136) Giraph no longer checkpoints after loading input

2017-03-16 Thread Nic Eggert (JIRA)

 [ 
https://issues.apache.org/jira/browse/GIRAPH-1136?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Nic Eggert updated GIRAPH-1136:
---
Description: 
>From the Worker Failure section in Chapter 6 of Practical Analytics with 
>Apache Giraph:
{quote}
If checkpoints are enabled, you are guaranteed to have the initial graph data 
safely stored in HDFS.
{quote}

Looking at the current code in 
{{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is no 
longer the case. After a little bit of digging, it looks like this change was 
introduced here: 
https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
 (GIRAPH-993)

Was this change intentional? It seems like an initial checkpoint would be 
desirable (I have a job where 1/3 of the runtime is spent loading input splits).

The simplest fix would be to just add a special case for Superstep 0. If that's 
acceptable, I'd be happy to submit a PR.

  was:
>From Practical Analytics with Apache Giraph:
{quote}
If checkpoints are enabled, you are guaranteed to have the initial graph data 
safely stored in HDFS.
{quote}

Looking at the current code in 
{{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is no 
longer the case. After a little bit of digging, it looks like this change was 
introduced here: 
https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
 (GIRAPH-993)

Was this change intentional? It seems like an initial checkpoint would be 
desirable (I have a job where 1/3 of the runtime is spent loading input splits).

The simplest fix would be to just add a special case for Superstep 0. If that's 
acceptable, I'd be happy to submit a PR.


> Giraph no longer checkpoints after loading input
> 
>
> Key: GIRAPH-1136
> URL: https://issues.apache.org/jira/browse/GIRAPH-1136
> Project: Giraph
>  Issue Type: Bug
>  Components: bsp
>Affects Versions: 1.2.0
>Reporter: Nic Eggert
>
> From the Worker Failure section in Chapter 6 of Practical Analytics with 
> Apache Giraph:
> {quote}
> If checkpoints are enabled, you are guaranteed to have the initial graph data 
> safely stored in HDFS.
> {quote}
> Looking at the current code in 
> {{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is 
> no longer the case. After a little bit of digging, it looks like this change 
> was introduced here: 
> https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
>  (GIRAPH-993)
> Was this change intentional? It seems like an initial checkpoint would be 
> desirable (I have a job where 1/3 of the runtime is spent loading input 
> splits).
> The simplest fix would be to just add a special case for Superstep 0. If 
> that's acceptable, I'd be happy to submit a PR.



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)


[jira] [Updated] (GIRAPH-1136) Giraph no longer checkpoints after loading input

2017-03-16 Thread Nic Eggert (JIRA)

 [ 
https://issues.apache.org/jira/browse/GIRAPH-1136?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Nic Eggert updated GIRAPH-1136:
---
Description: 
>From the Worker Failure section in Chapter 6 of Practical Analytics with 
>Apache Giraph:
{quote}
If checkpoints are enabled, you are guaranteed to have the initial graph data 
safely stored in HDFS.
{quote}

Looking at the current code in 
{{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is no 
longer the case. After a little bit of digging, it looks like this change was 
introduced here: 
https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
 (GIRAPH-933)

Was this change intentional? It seems like an initial checkpoint would be 
desirable (I have a job where 1/3 of the runtime is spent loading input splits).

The simplest fix would be to just add a special case for Superstep 0. If that's 
acceptable, I'd be happy to submit a PR.

  was:
>From the Worker Failure section in Chapter 6 of Practical Analytics with 
>Apache Giraph:
{quote}
If checkpoints are enabled, you are guaranteed to have the initial graph data 
safely stored in HDFS.
{quote}

Looking at the current code in 
{{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is no 
longer the case. After a little bit of digging, it looks like this change was 
introduced here: 
https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
 (GIRAPH-993)

Was this change intentional? It seems like an initial checkpoint would be 
desirable (I have a job where 1/3 of the runtime is spent loading input splits).

The simplest fix would be to just add a special case for Superstep 0. If that's 
acceptable, I'd be happy to submit a PR.


> Giraph no longer checkpoints after loading input
> 
>
> Key: GIRAPH-1136
> URL: https://issues.apache.org/jira/browse/GIRAPH-1136
> Project: Giraph
>  Issue Type: Bug
>  Components: bsp
>Affects Versions: 1.2.0
>Reporter: Nic Eggert
>
> From the Worker Failure section in Chapter 6 of Practical Analytics with 
> Apache Giraph:
> {quote}
> If checkpoints are enabled, you are guaranteed to have the initial graph data 
> safely stored in HDFS.
> {quote}
> Looking at the current code in 
> {{o.a.g.master.BspServiceMaster:getCheckpointStatus}}, it looks like this is 
> no longer the case. After a little bit of digging, it looks like this change 
> was introduced here: 
> https://github.com/apache/giraph/commit/5adca63deca25d84f4fdea053c35a85efc8bbb3d#diff-e16fdec9e3f573eba64cfe6eab512e19L657
>  (GIRAPH-933)
> Was this change intentional? It seems like an initial checkpoint would be 
> desirable (I have a job where 1/3 of the runtime is spent loading input 
> splits).
> The simplest fix would be to just add a special case for Superstep 0. If 
> that's acceptable, I'd be happy to submit a PR.



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)


[jira] [Created] (GIRAPH-1137) Remove channel probing from Netty worker thread for credit-based flow-control

2017-03-16 Thread Hassan Eslami (JIRA)
Hassan Eslami created GIRAPH-1137:
-

 Summary: Remove channel probing from Netty worker thread for 
credit-based flow-control
 Key: GIRAPH-1137
 URL: https://issues.apache.org/jira/browse/GIRAPH-1137
 Project: Giraph
  Issue Type: Bug
Reporter: Hassan Eslami
Assignee: Hassan Eslami


In credit-based flow-control, sometimes, client threads (one type of Netty 
worker threads used in Giraph) try to send requests to other workers. This is 
bad practice for Netty and can cause Netty to mark the execution as 
deadlock-prone (an example exception shown below). Client threads should only 
be responsible for sending ACK/NACK messages in response to requests, and they 
should do so by reuseing the channel from which they received the request. In 
the current implementation, client threads may try to send unsent/cached 
requests in credit-based flow control. Sending such requests should be 
delegated to other threads.

WARN 2017-03-08 06:06:22,104 [netty-client-worker-3] 
io.netty.util.concurrent.BlockingOperationException: 
DefaultChannelPromise@2c455378(incomplete)
at 
io.netty.util.concurrent.DefaultPromise.checkDeadLock(DefaultPromise.java:383)
at 
io.netty.channel.DefaultChannelPromise.checkDeadLock(DefaultChannelPromise.java:157)
at io.netty.util.concurrent.DefaultPromise.await0(DefaultPromise.java:343)
at io.netty.util.concurrent.DefaultPromise.await(DefaultPromise.java:259)
at 
org.apache.giraph.utils.ProgressableUtils$ChannelFutureWaitable.waitFor(ProgressableUtils.java:461)
at org.apache.giraph.utils.ProgressableUtils.waitFor(ProgressableUtils.java:214)
at 
org.apache.giraph.utils.ProgressableUtils.waitForever(ProgressableUtils.java:180)
at 
org.apache.giraph.utils.ProgressableUtils.waitForever(ProgressableUtils.java:165)
at 
org.apache.giraph.utils.ProgressableUtils.awaitChannelFuture(ProgressableUtils.java:132)
at org.apache.giraph.comm.netty.NettyClient.getNextChannel(NettyClient.java:715)
at 
org.apache.giraph.comm.netty.NettyClient.writeRequestToChannel(NettyClient.java:799)
at org.apache.giraph.comm.netty.NettyClient.doSend(NettyClient.java:789)
at 
org.apache.giraph.comm.flow_control.CreditBasedFlowControl.trySendCachedRequests(CreditBasedFlowControl.java:515)
at 
org.apache.giraph.comm.flow_control.CreditBasedFlowControl.messageAckReceived(CreditBasedFlowControl.java:485)
at 
org.apache.giraph.comm.netty.NettyClient.messageReceived(NettyClient.java:840)
at 
org.apache.giraph.comm.netty.handler.ResponseClientHandler.channelRead(ResponseClientHandler.java:87)
at 
io.netty.channel.DefaultChannelHandlerContext.invokeChannelRead(DefaultChannelHandlerContext.java:338)
at 
io.netty.channel.DefaultChannelHandlerContext.fireChannelRead(DefaultChannelHandlerContext.java:324)
at 
io.netty.handler.codec.ByteToMessageDecoder.channelRead(ByteToMessageDecoder.java:153)
at 
io.netty.channel.DefaultChannelHandlerContext.invokeChannelRead(DefaultChannelHandlerContext.java:338)
at 
io.netty.channel.DefaultChannelHandlerContext.fireChannelRead(DefaultChannelHandlerContext.java:324)
at 
org.apache.giraph.comm.netty.InboundByteCounter.channelRead(InboundByteCounter.java:89)
at 
io.netty.channel.DefaultChannelHandlerContext.invokeChannelRead(DefaultChannelHandlerContext.java:338)
at 
io.netty.channel.DefaultChannelHandlerContext.fireChannelRead(DefaultChannelHandlerContext.java:324)
at 
io.netty.channel.DefaultChannelPipeline.fireChannelRead(DefaultChannelPipeline.java:785)
at 
io.netty.channel.nio.AbstractNioByteChannel$NioByteUnsafe.read(AbstractNioByteChannel.java:126)
at io.netty.channel.nio.NioEventLoop.processSelectedKey(NioEventLoop.java:485)
at 
io.netty.channel.nio.NioEventLoop.processSelectedKeysOptimized(NioEventLoop.java:452)
at io.netty.channel.nio.NioEventLoop.run(NioEventLoop.java:346)
at 
io.netty.util.concurrent.SingleThreadEventExecutor$2.run(SingleThreadEventExecutor.java:101)
at java.lang.Thread.run(Thread.java:745)




--
This message was sent by Atlassian JIRA
(v6.3.15#6346)


[jira] [Commented] (GIRAPH-1137) Remove channel probing from Netty worker thread for credit-based flow-control

2017-03-16 Thread ASF GitHub Bot (JIRA)

[ 
https://issues.apache.org/jira/browse/GIRAPH-1137?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15928741#comment-15928741
 ] 

ASF GitHub Bot commented on GIRAPH-1137:


GitHub user heslami opened a pull request:

https://github.com/apache/giraph/pull/26

[GIRAPH-1137] Remove channel probing from Netty worker thread for 
credit-based flow…

In credit-based flow-control, sometimes, client threads (one type of Netty 
worker threads used in Giraph) try to send requests to other workers. This is 
bad practice for Netty and can cause Netty to mark the execution as 
deadlock-prone (an example exception shown below). Client threads should only 
be responsible for sending ACK/NACK messages in response to requests, and they 
should do so by reuseing the channel from which they received the request. In 
the current implementation, client threads may try to send unsent/cached 
requests in credit-based flow control. Sending such requests should be 
delegated to other threads.

WARN 2017-03-08 06:06:22,104 [netty-client-worker-3] 
io.netty.util.concurrent.BlockingOperationException: 
DefaultChannelPromise@2c455378(incomplete)
at 
io.netty.util.concurrent.DefaultPromise.checkDeadLock(DefaultPromise.java:383)
at 
io.netty.channel.DefaultChannelPromise.checkDeadLock(DefaultChannelPromise.java:157)
at io.netty.util.concurrent.DefaultPromise.await0(DefaultPromise.java:343)
at io.netty.util.concurrent.DefaultPromise.await(DefaultPromise.java:259)
at 
org.apache.giraph.utils.ProgressableUtils$ChannelFutureWaitable.waitFor(ProgressableUtils.java:461)
at 
org.apache.giraph.utils.ProgressableUtils.waitFor(ProgressableUtils.java:214)
at 
org.apache.giraph.utils.ProgressableUtils.waitForever(ProgressableUtils.java:180)
at 
org.apache.giraph.utils.ProgressableUtils.waitForever(ProgressableUtils.java:165)
at 
org.apache.giraph.utils.ProgressableUtils.awaitChannelFuture(ProgressableUtils.java:132)
at 
org.apache.giraph.comm.netty.NettyClient.getNextChannel(NettyClient.java:715)
at 
org.apache.giraph.comm.netty.NettyClient.writeRequestToChannel(NettyClient.java:799)
at org.apache.giraph.comm.netty.NettyClient.doSend(NettyClient.java:789)
at 
org.apache.giraph.comm.flow_control.CreditBasedFlowControl.trySendCachedRequests(CreditBasedFlowControl.java:515)
at 
org.apache.giraph.comm.flow_control.CreditBasedFlowControl.messageAckReceived(CreditBasedFlowControl.java:485)
at 
org.apache.giraph.comm.netty.NettyClient.messageReceived(NettyClient.java:840)
at 
org.apache.giraph.comm.netty.handler.ResponseClientHandler.channelRead(ResponseClientHandler.java:87)
at 
io.netty.channel.DefaultChannelHandlerContext.invokeChannelRead(DefaultChannelHandlerContext.java:338)
at 
io.netty.channel.DefaultChannelHandlerContext.fireChannelRead(DefaultChannelHandlerContext.java:324)
at 
io.netty.handler.codec.ByteToMessageDecoder.channelRead(ByteToMessageDecoder.java:153)
at 
io.netty.channel.DefaultChannelHandlerContext.invokeChannelRead(DefaultChannelHandlerContext.java:338)
at 
io.netty.channel.DefaultChannelHandlerContext.fireChannelRead(DefaultChannelHandlerContext.java:324)
at 
org.apache.giraph.comm.netty.InboundByteCounter.channelRead(InboundByteCounter.java:89)
at 
io.netty.channel.DefaultChannelHandlerContext.invokeChannelRead(DefaultChannelHandlerContext.java:338)
at 
io.netty.channel.DefaultChannelHandlerContext.fireChannelRead(DefaultChannelHandlerContext.java:324)
at 
io.netty.channel.DefaultChannelPipeline.fireChannelRead(DefaultChannelPipeline.java:785)
at 
io.netty.channel.nio.AbstractNioByteChannel$NioByteUnsafe.read(AbstractNioByteChannel.java:126)
at 
io.netty.channel.nio.NioEventLoop.processSelectedKey(NioEventLoop.java:485)
at 
io.netty.channel.nio.NioEventLoop.processSelectedKeysOptimized(NioEventLoop.java:452)
at io.netty.channel.nio.NioEventLoop.run(NioEventLoop.java:346)
at 
io.netty.util.concurrent.SingleThreadEventExecutor$2.run(SingleThreadEventExecutor.java:101)
at java.lang.Thread.run(Thread.java:745)


You can merge this pull request into a Git repository by running:

$ git pull https://github.com/heslami/giraph fix-credit-based

Alternatively you can review and apply these changes as the patch at:

https://github.com/apache/giraph/pull/26.patch

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

This closes #26


commit 4c8186cc8097877d5af20ef054630a629caaa026
Author: Hassan Eslami 
Date:   2017-03-16T19:52:12Z

Remove channel probing from Netty worker thread for credit-based 
flow-control

Closes GIRAPH-1137




> Remove channel probing from Netty worker thread for credit-based flow-control
> -
>
> 

[jira] [Commented] (GIRAPH-1135) Implementing Minimum Spanning Tree in vertex-centric model

2017-03-16 Thread Lahiru (JIRA)

[ 
https://issues.apache.org/jira/browse/GIRAPH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15929499#comment-15929499
 ] 

Lahiru commented on GIRAPH-1135:


Hi I'm Lahiru and I am a Computer Engineering student at University of 
Peradeniya, Sri Lanka. I have good knowledge in following fields Data 
structures and algorithms, Python, C, C++, java,...  I am interested in this 
gsoc project and I would like to contribute for the project. my linked in 
profile https://www.linkedin.com/in/lahiruls

> Implementing Minimum Spanning Tree in vertex-centric model
> --
>
> Key: GIRAPH-1135
> URL: https://issues.apache.org/jira/browse/GIRAPH-1135
> Project: Giraph
>  Issue Type: Improvement
>  Components: examples
>Reporter: Claudio Martella
>Assignee: Alessio Arleo
>  Labels: gsoc2017
>
> A Minimum Spanning Tree is a tree that spans all the vertices of a connected 
> graph such that the sum of the weights is minimum among all possible such 
> trees. Finding Minimum Spanning Tree on a large graph has many applications. 
> MST algorithm is one of the basic graph algorithms.  Currently, Giraph has an 
> implementation of Page Rank algorithm as part of its source code. An 
> implementation of MST algorithm will strengthen our use cases.
> Recently Mohsen Ghaffari et al. have shown that MST can be calculated in 
> O(log* n) rounds of communications in Congested Clique model [1]. Congested 
> Clique have been shown to be the impromptu distributed algorithmic model 
> which has direct relations with Pregel. We can try to implement the paradigm 
> in Giraph.
> [1] MST in Log-Star Rounds of Congested Clique :- 
> http://dl.acm.org/citation.cfm?id=2933103



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)


[jira] [Comment Edited] (GIRAPH-1135) Implementing Minimum Spanning Tree in vertex-centric model

2017-03-16 Thread Lahiru (JIRA)

[ 
https://issues.apache.org/jira/browse/GIRAPH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15929499#comment-15929499
 ] 

Lahiru edited comment on GIRAPH-1135 at 3/17/17 6:50 AM:
-

Hi I'm Lahiru and I am a Computer Engineering student at University of 
Peradeniya, Sri Lanka. I have good knowledge in following fields Data 
structures and algorithms, Python, C, C++, java,...  I am interested in this 
gsoc project and I would like to contribute for the project. my linked in 
profile https://www.linkedin.com/in/lahiruls
Can you please provide more additional details about this project


was (Author: asamala):
Hi I'm Lahiru and I am a Computer Engineering student at University of 
Peradeniya, Sri Lanka. I have good knowledge in following fields Data 
structures and algorithms, Python, C, C++, java,...  I am interested in this 
gsoc project and I would like to contribute for the project. my linked in 
profile https://www.linkedin.com/in/lahiruls

> Implementing Minimum Spanning Tree in vertex-centric model
> --
>
> Key: GIRAPH-1135
> URL: https://issues.apache.org/jira/browse/GIRAPH-1135
> Project: Giraph
>  Issue Type: Improvement
>  Components: examples
>Reporter: Claudio Martella
>Assignee: Alessio Arleo
>  Labels: gsoc2017
>
> A Minimum Spanning Tree is a tree that spans all the vertices of a connected 
> graph such that the sum of the weights is minimum among all possible such 
> trees. Finding Minimum Spanning Tree on a large graph has many applications. 
> MST algorithm is one of the basic graph algorithms.  Currently, Giraph has an 
> implementation of Page Rank algorithm as part of its source code. An 
> implementation of MST algorithm will strengthen our use cases.
> Recently Mohsen Ghaffari et al. have shown that MST can be calculated in 
> O(log* n) rounds of communications in Congested Clique model [1]. Congested 
> Clique have been shown to be the impromptu distributed algorithmic model 
> which has direct relations with Pregel. We can try to implement the paradigm 
> in Giraph.
> [1] MST in Log-Star Rounds of Congested Clique :- 
> http://dl.acm.org/citation.cfm?id=2933103



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)


[jira] [Comment Edited] (GIRAPH-1135) Implementing Minimum Spanning Tree in vertex-centric model

2017-03-16 Thread Lahiru (JIRA)

[ 
https://issues.apache.org/jira/browse/GIRAPH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15929499#comment-15929499
 ] 

Lahiru edited comment on GIRAPH-1135 at 3/17/17 6:50 AM:
-

Hi I'm Lahiru and I am a Computer Engineering student at University of 
Peradeniya, Sri Lanka. I have good knowledge in following fields Data 
structures and algorithms, Python, C, C++, java,...  I am interested in this 
gsoc project and I would like to contribute for the project. my linked in 
profile https://www.linkedin.com/in/lahiruls

Can you please provide more additional details about this project???



was (Author: asamala):
Hi I'm Lahiru and I am a Computer Engineering student at University of 
Peradeniya, Sri Lanka. I have good knowledge in following fields Data 
structures and algorithms, Python, C, C++, java,...  I am interested in this 
gsoc project and I would like to contribute for the project. my linked in 
profile https://www.linkedin.com/in/lahiruls
Can you please provide more additional details about this project

> Implementing Minimum Spanning Tree in vertex-centric model
> --
>
> Key: GIRAPH-1135
> URL: https://issues.apache.org/jira/browse/GIRAPH-1135
> Project: Giraph
>  Issue Type: Improvement
>  Components: examples
>Reporter: Claudio Martella
>Assignee: Alessio Arleo
>  Labels: gsoc2017
>
> A Minimum Spanning Tree is a tree that spans all the vertices of a connected 
> graph such that the sum of the weights is minimum among all possible such 
> trees. Finding Minimum Spanning Tree on a large graph has many applications. 
> MST algorithm is one of the basic graph algorithms.  Currently, Giraph has an 
> implementation of Page Rank algorithm as part of its source code. An 
> implementation of MST algorithm will strengthen our use cases.
> Recently Mohsen Ghaffari et al. have shown that MST can be calculated in 
> O(log* n) rounds of communications in Congested Clique model [1]. Congested 
> Clique have been shown to be the impromptu distributed algorithmic model 
> which has direct relations with Pregel. We can try to implement the paradigm 
> in Giraph.
> [1] MST in Log-Star Rounds of Congested Clique :- 
> http://dl.acm.org/citation.cfm?id=2933103



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)