oreilly.comSafari Books Online.Conferences.
Articles Radar Books  

P2P Memebag

Transitivity

Imagine a sequence of things A, B, and C where A and C have no direct relationship except through the intermediary B. The relationship between A and C is a combination of the relationships between A and B and between B and C.


Quantifying Indirect Relationships

Given that you can know about the relationships AB and BC, what can you infer about the relationship AC?

Mathematical thinking about transitivity is generally based in Aristotle's law of syllogism, or the transitivity property of implication: if A implies B and B implies C, then A implies C. (See Theorem 1.4.2 here). Direct relationships between pairs can be combined to make statements about indirect relationships.

However if the relationship is not "implies" -- equivalence -- then the rules for combining relationships become more complex. If A implies that B is 75% likely, and B implies that C is 50% likely, A does not imply that C is 50% likely. The relationship between C and B is not preserved verbatim in the relationship between A and C. Rather, the likelyhood of C given A is 75% of 50%.

If the relationship is about trust the details get gnarlier, because trust comes in levels and is context specific. I trust my plumber with the plumbing but not the electrical work. I trust some plumbers more than others. So the domain of a statement and the specific valuation has to be accounted for. Let's say that a friend recommends a plumber: your decision to hire the plumber is based both on your friend's recommendation and on your friend's ability to give recommendations.

Self, ontology, perspective, and worldview

For our purposes, there is no way to quantify the relationship between B and C without specifying the point of view. This is because, in a decentralized network, there is no party with perfect knowledge of the system. B may consider the relationship profitable but C considers the relationship unprofitable. A may not know about the relationship between B and C except through the lens of a relationship between itself and B or C. Every entity must consider its own perspective the final arbiter.

The horizon of A's worldview stops at B. Characteristics of C, including its existence, can be inferred from information provided by B, but that is not the same as direct contact. Is B a liar? Is B a good observer? Is B an articulate communicator?

Imagine a small car on the highway with large trucks on every side, so that the car can't see traffic aside from the trucks.

The driver of the car wishes to go as fast as possible, but no faster than average auto traffic in its immediate vicinity (to avoid being an obvious target for speeding tickets). Breaking out of the tight cluster of trucks surrounding it requires a risky squeeze through a small space between two of the trucks, a risk that is only worthwhile if the car can then go faster.

The car doesn't know the speed of traffic except by inference from the speed of the surrounding trucks. It may be that these trucks are moving far slower than other cars, because they are on a steep grade and trucks are less able to go fast up a hill. In that case the car should accept the risk, otherwise it should remain in the cluster.

The driver of the car has a speed relationship with other cars that is brokered by the intermediary trucks. The truck ahead may be matching its speed with a car ahead of it, but then again it may not. The relationship between the car in front of the truck and the car behind the truck is a combination of the relationship between the two pairs. Transitivity determines how the direct relationships are combined into an indirect relationship. SPKI is very much concerned with transitive relationships. See the thread "Trust and Transitivity" in the SPKI WG mail archives for a detailed discussion.

Back to Index


P2P Weblogs

Richard Koman Richard Koman's Weblog
Supreme Court Decides Unanimously Against Grokster
Updating as we go. Supremes have ruled 9-0 in favor of the studios in MGM v Grokster. But does the decision have wider import? Is it a death knell for tech? It's starting to look like the answer is no. (Jun 27, 2005)

> More from O'Reilly Developer Weblogs


More Weblogs
FolderShare remote computer search: better privacy than Google Desktop? [Sid Steward]

Data Condoms: Solutions for Private, Remote Search Indexes [Sid Steward]

Behold! Google the darknet/p2p search engine! [Sid Steward]

Open Source & The Fallacy Of Composition [Spencer Critchley]