Discussion
OK, who are the experts on #DistributedSystems on the #Fediverse? There is a new #FEP for implementing a scalar #LogicalClock in #ActivityPub, #FEP4f18.
I'm especially interested in mitigations for Byzantine faults in the system; right now, it's kind of hand-wavy based on value and trust heuristics:
@evan In general, it seems important to note that the logical clock times can only be interpreted in the context of a causal event graph (rather than generally comparing the "times" like one would with a physical clock). I'm guessing this may lead to significant confusion. Put another way, there's no "network logical clock". There are numerous causal event timelines that define a partial ordering of the network events.
@Steve_Bate I think that as activities are received and objects are loaded, the logical clock value on the different servers will converge.
@Steve_Bate Yes, that's correct. Instead of using message send-receive, it uses activities as the unit of change.
@evan I'm not sure what you mean. Lamport doesn't use the term "unit of change" and send-receive are events that don't seem to be that. Lamport defines the clock as a function over events. I had been thinking generating, modifying, sending and receiving Activities were the events related to the FEP, but it seems like you had something different in mind. I'll wait to see how the proposal evolves before commenting further.
@Steve_Bate I mean that in the Lamport model, change in the system happens on message send or receive. I think we could do that in ActivityPub, probably using headers rather than properties of objects, since we don't usually reify a single delivery between servers. But I think the more interesting state-change mechanism is through activities. So, it's not an exact application of Lamport clocks. This is called out multiple times in the FEP.
@evan WRT Byzantine faults, it looks like, with the FEP algorithm, the logical clock will never recover if a node accidentally or intentionally sends a very high clock value (e.g., 2^64-1). What is the motivation for having a logical clock for the AP network?
@Steve_Bate hey, Steve. So, there is a security considerations section here:
https://fediverse.codeberg.page/fep/fep/4f18/#security-considerations
Like I mentioned, the best mitigations I have are heuristic: don't advance the clock more than the expected number of activities per day, say and/or don't advance the clock at all on activities from known defector servers.
@evan True, but there are "softer" attacks that will be difficult to detect. If all the server have different heuristics, that may lead to chaos too since large jumps are actually expected in some cases (newer servers, etc.). If nodes decide to "block" the networkTime from specific servers, the damage cannot be undone.
@Steve_Bate logical clocks let you track some kinds of causality in distributed systems.
https://en.wikipedia.org/wiki/Logical_clock
The scalar logical clock in #FEP4f18 is similar in intent and design to Lamport clocks:
@Steve_Bate Lamport's original paper is readable and gives some good motivations:
Install Fedizen
Get the full app experience
@evan A couple more comments... saying "time is represented by a 64-bit integer value shared between servers on the network" could be misleading. I'm guessing you don't mean all servers share the same time value (or that the clocks even converge to the same value). In Lamport's paper a send event time is strictly < a receive event time (receiver increments). In the FEP, they are <=. The equality means the send->receive causal relationship is lost (the events are "concurrent" in Lamport terms).