Graph Theory & Dependency Management Insights

Raw notes and insights from discussions with Lucas Di Cioccio on graph algorithms, dependency tracking, and network topology for Amigos platform.

Core Graph Concepts

DAG (Directed Acyclic Graph)

• Fundamental Structure: Services and dependencies form a DAG
• Problem Scale: Large graphs create complex computational problems
• Key Property to Preserve: Reachability - can service A reach service B?

Graph Aggregation & Abstraction

Macro Nodes (Aggregation):

• Aggregate subsystems into single nodes
• Reduce complexity while preserving essential properties
• “Macro nodes that represent subsystems”

Mapping Between Graphs:

• Original atomic graph: “graph as it atomically exists”
• Abstracted graph: Higher-level view for human comprehension
• Preserve critical properties through transformations

Graph Operations & Composition

Complete vs. Parametric Objects

Function Composition:

f(a,b): f(a) -> f(b)

Graph Merging vs. Addition:

• graph A + graph B -> merge two graphs (not just adding nodes)
• graph A + graph B = graph C (creates new composite graph)
• Merging is not always commutative: f(a) + f(b) != f(a+b)

Convex vs. Non-Convex Functions

• Convex functions: Desirable mathematical properties
• Non-convex: More complex behavior, harder to optimize
• Relates to how graph operations combine and scale

Network Connection Patterns

Connection vs. Overlay

Two Distinct Operations:

1. Connect graphs: graph A connected to graph B
2. Overlay graphs: graph A + graph B

Algorithmic Graphs:

• “Grammar of graphs” - formal rules for graph construction
• Programmatic graph generation and manipulation

Human-Centric Graph Design

Proximity and Comprehension

• Graphs are for humans - need intuitive understanding
• Sense of “proximity” - related services should feel close
• Hyperbolic geometry - non-Euclidean space for representing relationships

Temporal Graph Dynamics

Exponential Moving Averages (EMA)

EWMA (Exponentially Weighted Moving Average):

alpha * new_value + (1 - alpha) * old_value

Alpha Parameter:

• alpha = 1 → Only new data (complete replacement)
• alpha = 0 → Only old data (no change)
• 0 < alpha < 1 → Balanced weighting

Applications:

• Budget for change - how much system can evolve
• Data availability vs. constraint - new vs. historical data
• Network topology evolution over time

Linear and Convex Combinations

• Linear combination: General weighted sum of components
• Convex combination: Weights sum to 1, preserve “averaging” property
• Useful for graph merging and service composition strategies

Technical Implementation Insights

Dependency Tracking (Lucas’s DepTrack Project)

• DAG-based logging: “Logs are more useful when shaped like a tree”
• Monad transformer for describing directed-acyclic graphs
• Type-safe infrastructure description and manipulation

Addressable Functions (Val Town Model)

• Services as addressable, composable functions
• Immediate deployment and execution
• “Zero config devops” for service composition

Contravariant Logging

• Map function on inputs instead of outputs
• Callback-based logging: log(callback) instead of log(message)
• Stacktrace nesting/decoration - hierarchical error context

Policy vs. Practice vs. Constraints

Decision-Making Framework

• Political choice: Strategic direction and vision
• Practical choice: Implementation and operational decisions
• Constraint: Technical or resource limitations

Formalization Process

1. Formalize the need - clear problem statement
2. Provide input data - concrete examples and requirements
3. Draw desired outcome - visual representation of goals
4. Consider grid layout with defragmentation strategies

Connections to Amigos Platform

Service Import Economy

• DAG of dependencies across networks (Web2, Web3, local)
• Reachability preservation during service composition
• Macro node aggregation for complex service clusters

Network Topology Management

• Hyperbolic proximity for service discovery
• EMA-based evolution of service relationships
• Convex combination of service capabilities

Development Tools

• Algorithmic graph grammar for service composition rules
• Contravariant logging for distributed debugging
• Addressable functions like Val Town for immediate deployment

Research Directions

Potential Collaboration with Lucas

• Grant applications for graph research
• Pandoc integration for documentation generation
• Formal methods for service composition verification

Open Questions

• How to efficiently compute reachability in large service graphs?
• What’s the optimal alpha for EMA in dynamic service networks?
• How to design intuitive proximity metrics for service relationships?
• Can we automate graph defragmentation for service optimization?

References

• DepTrack Project - DAG-based dependency tracking
• Salmon - Haskell system operations library
• Lucas Di Cioccio - Functional programming and system design
• Val Town - Addressable function deployment platform
• Linear Combination - Mathematical foundation
• Convex Combination - Constrained linear combination
• Pandoc - Universal document converter

See also

• p/amigos/technical-vision
• p/amigos/amigos
• p/amigos/plan-product