Skip to content

Deadlock in streaming connected components #231

@ehein6

Description

@ehein6

Streaming connected components can deadlock when handling edge deletions. The function update_tree_for_delete_directed() applies a bitwise not to a value of the level array.

If the level value was zero, it will be flipped to -1. This is a reserved value for the full/empty bit functions that means "empty". Later, when bfs_rebuild_component() attempts a readff() on the same value, it hangs. This occurs even during serial execution.

Somehow we need to prevent a -1 from being ever being written to a level value, but it's not clear how to do this without breaking something else.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions